Algorithm to generate mountain ranges with upstrokes and down-strokes java

Java

Algorithm Design

Mountain Range Generation

Programming

Software Development

Algorithm to generate mountain ranges with upstrokes and down-strokes java

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Algorithms Java

Introduction

Generating mountain ranges with upstrokes (/) and down-strokes (\) is a classic combinatorics problem equivalent to generating valid parentheses or Catalan number sequences. Given n pairs, the goal is to produce all strings of n upstrokes and n down-strokes where at no prefix do down-strokes exceed upstrokes (the "mountain" never goes below ground level). The number of valid mountain ranges of n pairs is the nth Catalan number. Backtracking recursion is the standard approach.

The Problem

For n = 3, the valid mountain ranges are:

1/\/\/\
2/\/\  /\
3/\    /\/\
4/\  /\/\
5/\/\  /\

Represented as strings: ///\\\, //\/\\, //\\/\, /\/\/\, /\//\\

Each string has exactly n forward slashes and n backslashes, and at every position, the count of / characters is greater than or equal to the count of \ characters.

Recursive Backtracking Solution

java

1import java.util.ArrayList;
2import java.util.List;
3
4public class MountainRanges {
5
6    public static List<String> generateMountains(int n) {
7        List<String> results = new ArrayList<>();
8        backtrack(results, new StringBuilder(), 0, 0, n);
9        return results;
10    }
11
12    private static void backtrack(List<String> results, StringBuilder current,
13                                   int up, int down, int n) {
14        if (current.length() == 2 * n) {
15            results.add(current.toString());
16            return;
17        }
18
19        // Can always go up if we haven't used all upstrokes
20        if (up < n) {
21            current.append('/');
22            backtrack(results, current, up + 1, down, n);
23            current.deleteCharAt(current.length() - 1);
24        }
25
26        // Can go down only if it won't go below ground level
27        if (down < up) {
28            current.append('\\');
29            backtrack(results, current, up, down + 1, n);
30            current.deleteCharAt(current.length() - 1);
31        }
32    }
33
34    public static void main(String[] args) {
35        List<String> mountains = generateMountains(3);
36        for (String m : mountains) {
37            System.out.println(m);
38        }
39        // Output:
40        // ///\\\
41        // //\/\\
42        // //\\/\
43        // /\/\/\
44        // /\//\\
45        System.out.println("Total: " + mountains.size()); // 5 (Catalan number C3)
46    }
47}

The key constraint is down < up — you can only add a down-stroke if the current height (upstrokes minus down-strokes) is above zero.

Visual ASCII Rendering

java

1public class MountainRenderer {
2
3    public static String render(String mountain) {
4        int height = 0;
5        int maxHeight = 0;
6
7        // Find maximum height
8        for (char c : mountain.toCharArray()) {
9            height += (c == '/') ? 1 : -1;
10            maxHeight = Math.max(maxHeight, height);
11        }
12
13        // Build the 2D grid
14        char[][] grid = new char[maxHeight][mountain.length()];
15        for (char[] row : grid) {
16            java.util.Arrays.fill(row, ' ');
17        }
18
19        height = 0;
20        for (int col = 0; col < mountain.length(); col++) {
21            if (mountain.charAt(col) == '/') {
22                grid[maxHeight - height - 1][col] = '/';
23                height++;
24            } else {
25                height--;
26                grid[maxHeight - height - 1][col] = '\\';
27            }
28        }
29
30        // Convert to string
31        StringBuilder sb = new StringBuilder();
32        for (char[] row : grid) {
33            sb.append(new String(row)).append('\n');
34        }
35        return sb.toString();
36    }
37
38    public static void main(String[] args) {
39        System.out.println(render("///\\\\\\"));
40        //   /\
41        //  /  \
42        // /    \
43
44        System.out.println(render("/\\/\\/\\"));
45        // /\/\/\
46    }
47}

Iterative Approach with Stack

java

1import java.util.*;
2
3public class MountainRangesIterative {
4
5    public static List<String> generateMountains(int n) {
6        List<String> results = new ArrayList<>();
7        // State: (current string, upstrokes used, downstrokes used)
8        Deque<int[]> stack = new ArrayDeque<>();
9        List<StringBuilder> builders = new ArrayList<>();
10
11        stack.push(new int[]{0, 0});
12        builders.add(new StringBuilder());
13
14        while (!stack.isEmpty()) {
15            int[] state = stack.pop();
16            StringBuilder sb = builders.remove(builders.size() - 1);
17            int up = state[0], down = state[1];
18
19            if (sb.length() == 2 * n) {
20                results.add(sb.toString());
21                continue;
22            }
23
24            if (down < up) {
25                StringBuilder downSb = new StringBuilder(sb).append('\\');
26                stack.push(new int[]{up, down + 1});
27                builders.add(downSb);
28            }
29
30            if (up < n) {
31                StringBuilder upSb = new StringBuilder(sb).append('/');
32                stack.push(new int[]{up + 1, down});
33                builders.add(upSb);
34            }
35        }
36
37        return results;
38    }
39}

The iterative version replaces recursion with an explicit stack, avoiding StackOverflowError for large n.

Counting with Catalan Numbers

java

1public class CatalanNumber {
2
3    // The number of valid mountain ranges of n pairs
4    public static long catalan(int n) {
5        if (n <= 1) return 1;
6
7        long[] dp = new long[n + 1];
8        dp[0] = 1;
9        dp[1] = 1;
10
11        for (int i = 2; i <= n; i++) {
12            for (int j = 0; j < i; j++) {
13                dp[i] += dp[j] * dp[i - 1 - j];
14            }
15        }
16        return dp[n];
17    }
18
19    public static void main(String[] args) {
20        for (int i = 0; i <= 10; i++) {
21            System.out.println("C(" + i + ") = " + catalan(i));
22        }
23        // C(0)=1, C(1)=1, C(2)=2, C(3)=5, C(4)=14, C(5)=42, ...
24    }
25}

The nth Catalan number C(n) = (2n)! / ((n+1)! * n!) gives the count without generating all sequences.

Common Pitfalls

Allowing down-strokes below ground level: The constraint is down < up, not down < n. Without this check, invalid sequences like \/ (going negative) are produced.
String concatenation in recursion: Creating new String objects at each recursive call is O(n) per call. Use StringBuilder with append/delete for O(1) per step.
Stack overflow for large n: Recursive solutions hit Java's default stack limit (~512-1024 frames) around n=500. Use the iterative approach or increase stack size with -Xss.
Confusing mountain ranges with balanced parentheses: They are mathematically identical — / maps to ( and \ maps to ). The same algorithm generates both.
Not escaping backslash in output: In Java strings, backslash must be escaped as \\. When printing mountain ranges, System.out.println("\\") outputs a single \.

Summary

Mountain ranges with / and \ are equivalent to balanced parentheses (Catalan numbers)
Use recursive backtracking with the constraint down < up to ensure validity
Use StringBuilder for efficient string building in recursion
The count of valid ranges for n pairs is the nth Catalan number: C(n) = (2n)! / ((n+1)! * n!)
Use iterative approach with explicit stack for large n to avoid stack overflow
ASCII rendering maps strokes to a 2D grid based on current height

DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course

Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Algorithm to generate mountain ranges with upstrokes and down-strokes java

Data Structures & Algorithms practice on Codemia

Introduction

The Problem

Recursive Backtracking Solution

Visual ASCII Rendering

Iterative Approach with Stack

Counting with Catalan Numbers

Common Pitfalls

Summary

Related reading

DSA Fundamentals

Track what you have practised

Data Structures & Algorithms practice on Codemia