These are the notes for DSA episode 90, the last episode of the course: a full mock coding interview. Two hard problems, each solved with the method from episode 89: clarify → examples → brute force → its complexity → find the waste → the insight → code → test → complexity. Candy (LeetCode 135): give everyone one toffee and fix broken rules until nothing changes; it is correct but times out with 200,000 students in falling order (O(n²)). The rule has two sides, so one left-to-right pass settles the left rule, one right-to-left pass settles the right rule, and the answer takes the max: O(n). Longest increasing path in a matrix (LeetCode 329): trying every climb from every cell (DFS) is correct but exponential; a 100 × 100 slope times out. Because moves only go to a strictly higher cell, there are no cycles (a DAG), so the longest climb from each cell can be stored in a memo table and every cell is solved once: O(m·n). Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).
The problems, in real life
| Real life | In code |
|---|---|
| A teacher hands toffees to students standing in a line after a test | ratings[i] = marks of student i, in line order |
| Everyone gets at least one toffee | candies[i] >= 1 |
| Scored more than the student next to you? You get more than them | ratings[i] > ratings[i ± 1] ⇒ candies[i] > candies[i ± 1] |
| She buys as few toffees as possible | return the minimum total |
| A hiker's map of a hill: a grid of heights | int[][] g, m rows, n columns |
| He only ever walks to a strictly higher spot, never diagonally | move up/down/left/right to g[x][y] > g[i][j] |
| The longest climb he can make | the length of the longest increasing path, in cells |
Every word, from zero
- Mock interview: a practice interview: one person asks the question and plays the interviewer, the other solves it out loud.
- Clarifying question: a question you ask the interviewer before coding, to make the problem exact (equal values? size of the input?).
- Constraint: a limit given with the problem, like "up to 200,000 students". It tells you which complexity is fast enough (episode 1).
- Brute force: the most direct correct method, usually trying everything; slow but a safe first answer.
- Greedy: building the answer by making the locally best choice at each step, here "the smallest number that obeys this side".
- Pass: one walk over the whole array, from one end to the other.
- Neighbour: in an array, the element just before or just after; in a grid, the cell above, below, left or right.
- Grid / matrix: a table of numbers with rows and columns; cell
(i, j)is rowi, columnj, counted from 0. - Path: a sequence of cells where each one is a neighbour of the one before.
- Strictly higher: greater than, not equal (
>, not>=). - DFS (depth-first search): explore by going as deep as possible along one route before backing up (episode 47); here, done with recursion.
- Recursion: a function that calls itself on a smaller version of the problem.
- Call stack: the memory where Java keeps one frame for every function call that has not returned yet.
- StackOverflowError: Java's error when the call stack runs out, usually because recursion never stops.
- Cycle: a route that comes back to where it started.
- DAG (directed acyclic graph): one-way arrows between nodes with no cycles; here, an arrow goes from each cell to every higher neighbour.
- Memoization (memo): storing the answer to each subproblem the first time it is computed, and reading it on every later call.
- Dynamic programming (DP): solving each subproblem once and reusing the stored answers.
- Time Limit Exceeded (TLE): the judge stopped the program because it ran longer than allowed.
- Overflow: a number too big for its type;
intstops at 2,147,483,647, so a bigger total needslong.
The interview method (episode 89, in practice)
| Step | What you say or do | Candy | Hill |
|---|---|---|---|
| 1. Clarify | Ask until the rules are exact | equal neighbours: no rule; n ≤ 200,000 | start anywhere; strictly higher; 200 × 200 |
| 2. Examples | Solve them by hand | [1,0,2] → 5, [1,2,2] → 4 |
→ 4 (1 2 6 9), → 4 (3 4 5 6) |
| 3. Brute force | Say it, code it if asked | fix until stable | DFS from every cell |
| 4. Its complexity | Compare with the constraint | O(n²): 4·10¹⁰, too slow | exponential |
| 5. The waste | What is repeated? | a fix travels one step per pass | the same climbs walked again |
| 6. Insight | Remove the waste | two passes + max | memo on a DAG |
| 7. Code | Explain while typing | 10 lines | 20 lines |
| 8. Test, complexity | Examples, edge cases, big input | O(n) | O(m·n) |
Problem 1: candy (LeetCode 135)
n children stand in a line; ratings[i] is child i's rating. Give candies so that every child gets at least one, and a child with a higher rating than a neighbour gets more candies than that neighbour. Return the minimum total.
| Input | Candies | Output |
|---|---|---|
[1, 0, 2] |
2 1 2 |
5 |
[1, 2, 2] |
1 2 1 |
4 (equal neighbours have no rule) |
[1, 0, 2, 3, 2, 1] |
2 1 2 3 2 1 |
11 |
[5] |
1 |
1 |
[2, 2, 2] |
1 1 1 |
3 |
[1, 3, 4, 5, 2] |
1 2 3 4 1 |
11 |
Clarify: equal neighbours have no rule between them; only the left and right neighbour matter; n is up to 200,000, so O(n²) = 4·10¹⁰ steps is far too slow: aim for O(n) or O(n log n).
Brute force: fix until stable
Give everyone 1. Walk the line; whenever a rule is broken, give that child one more than the neighbour they beat. A fix can break another rule, so repeat until a pass changes nothing.
import java.util.*;
public class Main {
static long candy(int[] r) {
int n = r.length;
long[] c = new long[n];
Arrays.fill(c, 1);
boolean changed = true;
while (changed) {
changed = false;
for (int i = 0; i < n; i++) {
if (i > 0 && r[i] > r[i - 1] && c[i] <= c[i - 1]) {
c[i] = c[i - 1] + 1; changed = true;
}
if (i + 1 < n && r[i] > r[i + 1] && c[i] <= c[i + 1]) {
c[i] = c[i + 1] + 1; changed = true;
}
}
}
long sum = 0;
for (long x : c) sum += x;
return sum;
}
public static void main(String[] args) {
System.out.println(candy(new int[]{1, 0, 2}));
System.out.println(candy(new int[]{1, 2, 2}));
System.out.println(candy(new int[]{1, 0, 2, 3, 2, 1}));
System.out.println(candy(new int[]{5}));
System.out.println(candy(new int[]{2, 2, 2}));
System.out.println(candy(new int[]{1, 3, 4, 5, 2}));
}
}
Output (real):
5
4
11
1
3
11
Correct. Now 200,000 children in falling order (r[i] = n - i):
int n = 200_000;
int[] r = new int[n];
for (int i = 0; i < n; i++) r[i] = n - i;
long t0 = System.nanoTime();
long total = candy(r);
System.out.println(total + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
Result (real): Time Limit Exceeded (stopped after 25 seconds, no output).
Why it is slow
Scores 5 4 3 2 1, everyone starts with 1:
| 5 | 4 | 3 | 2 | 1 | |
|---|---|---|---|---|---|
| pass 1 | 2 | 2 | 2 | 2 | 1 |
| pass 2 | 3 | 3 | 3 | 2 | 1 |
| pass 3 | 4 | 4 | 3 | 2 | 1 |
| pass 4 | 5 | 4 | 3 | 2 | 1 |
Walking left to right, each child only sees the neighbour's old number, so a correction moves one step per pass. n children need about n passes of n steps: O(n²), 4·10¹⁰ steps for 200,000.
The key insight: two sides, two passes, take the max
The rule has two independent sides:
- Left rule (beat your left neighbour ⇒ more than them): walk left to right. When you reach child
i, childi − 1's number is already final, soleft[i] = left[i − 1] + 1ifr[i] > r[i − 1], else 1. One pass. - Right rule: the mirror image, one pass right to left.
- A child must satisfy both, so give max(left[i], right[i]). It is also the minimum:
left[i]is the smallest number that obeys the left rule (it is the length of the rising run ending ati),right[i]the smallest for the right rule, so nobody can get less than the larger of the two.
By hand, [1, 0, 2, 3, 2, 1]:
| index | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| score | 1 | 0 | 2 | 3 | 2 | 1 |
| left pass | 1 | 1 | 2 | 3 | 1 | 1 |
| right pass | 2 | 1 | 1 | 3 | 2 | 1 |
| max | 2 | 1 | 2 | 3 | 2 | 1 |
Total 11.
Solution in Java
One array is enough: the left pass fills it, and the right pass takes the max with what is already there.
import java.util.*;
public class Main {
static long candy(int[] r) {
int n = r.length;
long[] c = new long[n];
Arrays.fill(c, 1);
for (int i = 1; i < n; i++)
if (r[i] > r[i - 1]) c[i] = c[i - 1] + 1;
for (int i = n - 2; i >= 0; i--)
if (r[i] > r[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1);
long sum = 0;
for (long x : c) sum += x;
return sum;
}
public static void main(String[] args) {
System.out.println(candy(new int[]{1, 0, 2}));
System.out.println(candy(new int[]{1, 2, 2}));
System.out.println(candy(new int[]{1, 0, 2, 3, 2, 1}));
System.out.println(candy(new int[]{5}));
System.out.println(candy(new int[]{2, 2, 2}));
System.out.println(candy(new int[]{1, 3, 4, 5, 2}));
}
}
Output (real):
5
4
11
1
3
11
The 200,000 children that timed out (same main as above):
20000100000, 17 ms
That is 200,000 × 200,001 / 2: the first child needs 200,000 toffees. The total is above 2,147,483,647, which is why it is a long.
A real bug: the right pass overwrites instead of taking the max
if (r[i] > r[i + 1]) c[i] = c[i + 1] + 1; // BUG: no Math.max
On [1, 3, 4, 5, 2]:
9
The answer is 11. The left pass gave 1 2 3 4 1; the right pass overwrote the student with 5 marks from 4 to 2, so now she has fewer than the student with 4 marks (3). Math.max keeps the left rule.
Problem 2: longest increasing path in a matrix (LeetCode 329)
Given an m × n grid of integers, return the length (in cells) of the longest path where every step goes up, down, left or right (no diagonals, not off the grid) to a strictly larger value.
| Input | Output |
|---|---|
[[9,9,4],[6,6,8],[2,1,1]] |
4 (1 → 2 → 6 → 9) |
[[3,4,5],[3,2,6],[2,2,1]] |
4 (3 → 4 → 5 → 6) |
[[1]] |
1 |
[[7,7],[7,7]] |
1 (equal is not higher) |
[[1,2,3,4,5]] |
5 |
Clarify: the path may start at any cell; equal heights are not allowed; the grid is up to 200 × 200 = 40,000 cells, so aim for about O(m·n).
Brute force: try every climb (DFS)
climb(i, j) = longest climb starting at (i, j): 1, plus the best climb from any strictly higher neighbour. Try it from every cell.
import java.util.*;
public class Main {
static int[][] D = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static int longest(int[][] g) {
int best = 0;
for (int i = 0; i < g.length; i++)
for (int j = 0; j < g[0].length; j++)
best = Math.max(best, climb(g, i, j));
return best;
}
static int climb(int[][] g, int i, int j) {
int len = 1;
for (int[] d : D) {
int x = i + d[0], y = j + d[1];
if (x >= 0 && y >= 0 && x < g.length && y < g[0].length
&& g[x][y] > g[i][j])
len = Math.max(len, 1 + climb(g, x, y));
}
return len;
}
public static void main(String[] args) {
System.out.println(longest(new int[][]{{9, 9, 4}, {6, 6, 8}, {2, 1, 1}}));
System.out.println(longest(new int[][]{{3, 4, 5}, {3, 2, 6}, {2, 2, 1}}));
System.out.println(longest(new int[][]{{1}}));
System.out.println(longest(new int[][]{{7, 7}, {7, 7}}));
System.out.println(longest(new int[][]{{1, 2, 3, 4, 5}}));
}
}
Output (real):
4
4
1
1
5
Correct. Now a 100 × 100 slope where g[i][j] = i + j:
int n = 100;
int[][] g = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) g[i][j] = i + j;
long t0 = System.nanoTime();
int best = longest(g);
System.out.println(best + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
Result (real): Time Limit Exceeded (stopped after 25 seconds, no output).
Why it is slow, and the key insight
From the corner every step can go right or down, and both are higher, so the number of different climbs is the number of monotone routes across the grid: about C(198, 99) ≈ 10⁵⁸. And the same climbs are walked again and again: starting at 1 walks 2 → 6 → 9, starting at 2 walks 6 → 9 again.
climb(i, j)depends only on the cell, not on how we reached it.- Moves go strictly up, so a climb can never return to a cell it came from: the "higher neighbour" arrows form a DAG (no cycles). So
climb(i, j)is a fixed number that never changes while we compute it. - So store it:
memo[i][j]. The first call computes it, every later call reads it. Each cell is solved once and looks at 4 neighbours.
By hand on the first grid (longest climb from each cell):
| col 0 | col 1 | col 2 | |
|---|---|---|---|
| row 0 (9 9 4) | 1 | 1 | 2 |
| row 1 (6 6 8) | 2 | 2 | 1 |
| row 2 (2 1 1) | 3 | 4 | 2 |
Peaks (the 9s and the 8) are 1; one step from a peak is 2; the 2 climbs to a 6 that already says 2, so 3; the bottom-middle 1 climbs to that 2 (3), so 4.
Solution in Java (memoised DFS)
import java.util.*;
public class Main {
static int[][] D = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static int longest(int[][] g) {
int[][] memo = new int[g.length][g[0].length];
int best = 0;
for (int i = 0; i < g.length; i++)
for (int j = 0; j < g[0].length; j++)
best = Math.max(best, climb(g, i, j, memo));
return best;
}
static int climb(int[][] g, int i, int j, int[][] memo) {
if (memo[i][j] != 0) return memo[i][j];
int len = 1;
for (int[] d : D) {
int x = i + d[0], y = j + d[1];
if (x >= 0 && y >= 0 && x < g.length && y < g[0].length
&& g[x][y] > g[i][j])
len = Math.max(len, 1 + climb(g, x, y, memo));
}
return memo[i][j] = len;
}
public static void main(String[] args) {
System.out.println(longest(new int[][]{{9, 9, 4}, {6, 6, 8}, {2, 1, 1}}));
System.out.println(longest(new int[][]{{3, 4, 5}, {3, 2, 6}, {2, 2, 1}}));
System.out.println(longest(new int[][]{{1}}));
System.out.println(longest(new int[][]{{7, 7}, {7, 7}}));
System.out.println(longest(new int[][]{{1, 2, 3, 4, 5}}));
}
}
Output (real):
4
4
1
1
5
0 in memo means "not solved yet"; every real answer is at least 1, so 0 can never be confused with an answer. return memo[i][j] = len; stores and returns in one line.
The 100 × 100 slope that timed out:
199, 1 ms
From height 0 in one corner to height 198 in the other: 199 cells.
A real bug: >= instead of >
&& g[x][y] >= g[i][j]) // BUG: equal is allowed
On [[7, 7], [7, 7]] (real, the first lines of 1,000+):
Exception in thread "main" java.lang.StackOverflowError
at Main.climb(Main.java:20)
at Main.climb(Main.java:20)
Cell (0, 0) steps to its equal neighbour (1, 0), which steps straight back. Neither memo is filled yet, so they call each other forever until the call stack runs out. Equal steps create cycles, and memoization is only valid on a graph without cycles: strictly greater is what makes it a DAG.
The same solutions in C++
#include <bits/stdc++.h>
using namespace std;
long long candy(const vector<int>& r) {
int n = r.size();
vector<long long> c(n, 1);
for (int i = 1; i < n; i++)
if (r[i] > r[i - 1]) c[i] = c[i - 1] + 1;
for (int i = n - 2; i >= 0; i--)
if (r[i] > r[i + 1]) c[i] = max(c[i], c[i + 1] + 1);
return accumulate(c.begin(), c.end(), 0LL);
}
const int D[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int climb(const vector<vector<int>>& g, int i, int j, vector<vector<int>>& memo) {
if (memo[i][j]) return memo[i][j];
int len = 1;
for (auto& d : D) {
int x = i + d[0], y = j + d[1];
if (x >= 0 && y >= 0 && x < (int)g.size() && y < (int)g[0].size() && g[x][y] > g[i][j])
len = max(len, 1 + climb(g, x, y, memo));
}
return memo[i][j] = len;
}
int longest(const vector<vector<int>>& g) {
vector<vector<int>> memo(g.size(), vector<int>(g[0].size(), 0));
int best = 0;
for (int i = 0; i < (int)g.size(); i++)
for (int j = 0; j < (int)g[0].size(); j++)
best = max(best, climb(g, i, j, memo));
return best;
}
int main() {
cout << candy({1, 0, 2}) << " " << candy({1, 2, 2}) << " " << candy({1, 0, 2, 3, 2, 1}) << "\n";
cout << candy({5}) << " " << candy({2, 2, 2}) << " " << candy({1, 3, 4, 5, 2}) << "\n";
vector<int> r(200000);
for (int i = 0; i < 200000; i++) r[i] = 200000 - i;
cout << candy(r) << "\n";
cout << longest({{9, 9, 4}, {6, 6, 8}, {2, 1, 1}}) << " " << longest({{3, 4, 5}, {3, 2, 6}, {2, 2, 1}}) << "\n";
cout << longest({{1}}) << " " << longest({{7, 7}, {7, 7}}) << " " << longest({{1, 2, 3, 4, 5}}) << "\n";
vector<vector<int>> g(100, vector<int>(100));
for (int i = 0; i < 100; i++)
for (int j = 0; j < 100; j++) g[i][j] = i + j;
cout << longest(g) << "\n";
}
Output (real, g++ -O2 -std=c++17):
5 4 11
1 3 11
20000100000
4 4
1 1 5
199
The same solutions in Python
import sys
from functools import lru_cache
def candy(r):
n = len(r)
c = [1] * n
for i in range(1, n):
if r[i] > r[i - 1]:
c[i] = c[i - 1] + 1
for i in range(n - 2, -1, -1):
if r[i] > r[i + 1]:
c[i] = max(c[i], c[i + 1] + 1)
return sum(c)
def longest(g):
m, n = len(g), len(g[0])
sys.setrecursionlimit(max(1000, m * n + 100))
@lru_cache(maxsize=None)
def climb(i, j):
best = 1
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
x, y = i + dx, j + dy
if 0 <= x < m and 0 <= y < n and g[x][y] > g[i][j]:
best = max(best, 1 + climb(x, y))
return best
return max(climb(i, j) for i in range(m) for j in range(n))
print(candy([1, 0, 2]), candy([1, 2, 2]), candy([1, 0, 2, 3, 2, 1]))
print(candy([5]), candy([2, 2, 2]), candy([1, 3, 4, 5, 2]))
print(candy([200000 - i for i in range(200000)]))
print(longest([[9, 9, 4], [6, 6, 8], [2, 1, 1]]), longest([[3, 4, 5], [3, 2, 6], [2, 2, 1]]))
print(longest([[1]]), longest([[7, 7], [7, 7]]), longest([[1, 2, 3, 4, 5]]))
print(longest([[i + j for j in range(100)] for i in range(100)]))
Output (real):
5 4 11
1 3 11
20000100000
4 4
1 1 5
199
@lru_cache is Python's built-in memo: it stores climb(i, j) the first time and returns the stored value afterwards. Python's default recursion limit is 1,000, so a long climb (a 200 × 200 snake can be 40,000 cells) needs sys.setrecursionlimit, or an iterative version (see interview question 5).
Complexity
n = number of students, m × n = grid size.
| Problem | Approach | Time | Extra memory | Big test |
|---|---|---|---|---|
| Candy | fix until stable | O(n²) | O(n) | 200,000 falling: Time Limit Exceeded |
| Candy | two passes + max | O(n) | O(n) | 17 ms |
| Hill | DFS from every cell | exponential | O(m·n) stack | 100 × 100 slope: Time Limit Exceeded |
| Hill | memoised DFS (DAG) | O(m·n) | O(m·n) memo + stack | 1 ms |
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| Coding before clarifying | a solution to a different problem | equal ratings / equal heights rules unknown | ask, then work the examples |
| Right pass overwrites | 9, not 11 on [1,3,4,5,2] |
the left rule's number is lost | c[i] = Math.max(c[i], c[i + 1] + 1) |
| Only one pass | [1, 0, 2] with only the left pass gives 4, not 5 |
the right rule is never checked | do both passes |
int for the total |
a negative or wrong total for 200,000 falling ratings | 20,000,100,000 > 2,147,483,647 | long |
>= instead of > |
java.lang.StackOverflowError |
equal neighbours form a cycle | strictly greater |
| DFS without memo | Time Limit Exceeded | the same climbs are walked again and again | memo[i][j] |
visited array instead of memo |
correct but still slow, or wrong when reset badly | "seen" is not "solved" | store the answer, not a flag |
Bounds check after reading g[x][y] |
ArrayIndexOutOfBoundsException |
g[-1][0] is read first |
check x, y before g[x][y] (&& stops early) |
Mini project: the toffee slip
The class teacher's helper: print how many toffees each student gets, the total to buy, and check every rule.
import java.util.*;
public class Main {
public static void main(String[] args) {
String[] names = {"Asha", "Ravi", "Priya", "Neha", "Kabir", "Dev"};
int[] marks = {72, 58, 81, 90, 66, 66};
long[] c = toffees(marks);
long total = 0;
for (int i = 0; i < names.length; i++) {
System.out.printf("%-6s %3d marks %d toffees%n", names[i], marks[i], c[i]);
total += c[i];
}
System.out.println("buy " + total + " toffees, rules ok: " + check(marks, c));
}
static long[] toffees(int[] r) {
int n = r.length;
long[] c = new long[n];
Arrays.fill(c, 1);
for (int i = 1; i < n; i++)
if (r[i] > r[i - 1]) c[i] = c[i - 1] + 1;
for (int i = n - 2; i >= 0; i--)
if (r[i] > r[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1);
return c;
}
static boolean check(int[] r, long[] c) {
for (int i = 0; i < r.length; i++) {
if (c[i] < 1) return false;
if (i > 0 && r[i] > r[i - 1] && c[i] <= c[i - 1]) return false;
if (i + 1 < r.length && r[i] > r[i + 1] && c[i] <= c[i + 1]) return false;
}
return true;
}
}
Output (real):
Asha 72 marks 2 toffees
Ravi 58 marks 1 toffees
Priya 81 marks 2 toffees
Neha 90 marks 3 toffees
Kabir 66 marks 1 toffees
Dev 66 marks 1 toffees
buy 10 toffees, rules ok: true
Kabir and Dev both scored 66, so there is no rule between them. Extend it: read the names and marks from input, and print "toffee" for 1.
Practice
1. Trapping Rain Water (LeetCode 42): the same two-pass idea: the tallest bar to the left of each position (left pass), the tallest to the right (right pass); the water above i is min(left[i], right[i]) − h[i]. (Episode 8 solved it with two pointers.)
2. Number of Increasing Paths in a Grid (LeetCode 2328): count every strictly increasing path (any length, including single cells), modulo 1,000,000,007. The same memo, but add instead of taking the max.
3. Print the longest climb itself, not just its length: after the memo is filled, start at the best cell and keep stepping to a higher neighbour whose memo is exactly one less.
Solutions
import java.util.*;
public class Main {
// Practice 1: Trapping Rain Water (LeetCode 42), two passes like candy
static int trap(int[] h) {
int n = h.length, water = 0;
int[] left = new int[n], right = new int[n];
for (int i = 0; i < n; i++) left[i] = Math.max(i > 0 ? left[i - 1] : 0, h[i]);
for (int i = n - 1; i >= 0; i--) right[i] = Math.max(i + 1 < n ? right[i + 1] : 0, h[i]);
for (int i = 0; i < n; i++) water += Math.min(left[i], right[i]) - h[i];
return water;
}
// Practice 2: Number of Increasing Paths in a Grid (LeetCode 2328), memo with counting
static final int MOD = 1_000_000_007;
static int[][] D = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static long ways(int[][] g, int i, int j, long[][] memo) {
if (memo[i][j] != 0) return memo[i][j];
long w = 1;
for (int[] d : D) {
int x = i + d[0], y = j + d[1];
if (x >= 0 && y >= 0 && x < g.length && y < g[0].length && g[x][y] > g[i][j])
w = (w + ways(g, x, y, memo)) % MOD;
}
return memo[i][j] = w;
}
static long countPaths(int[][] g) {
long[][] memo = new long[g.length][g[0].length];
long total = 0;
for (int i = 0; i < g.length; i++)
for (int j = 0; j < g[0].length; j++) total = (total + ways(g, i, j, memo)) % MOD;
return total;
}
// Practice 3: print the longest climb itself, not just its length
static int[][] memo;
static int climb(int[][] g, int i, int j) {
if (memo[i][j] != 0) return memo[i][j];
int len = 1;
for (int[] d : D) {
int x = i + d[0], y = j + d[1];
if (x >= 0 && y >= 0 && x < g.length && y < g[0].length && g[x][y] > g[i][j])
len = Math.max(len, 1 + climb(g, x, y));
}
return memo[i][j] = len;
}
static List<Integer> bestClimb(int[][] g) {
memo = new int[g.length][g[0].length];
int bi = 0, bj = 0;
for (int i = 0; i < g.length; i++)
for (int j = 0; j < g[0].length; j++)
if (climb(g, i, j) > climb(g, bi, bj)) { bi = i; bj = j; }
List<Integer> path = new ArrayList<>();
int i = bi, j = bj;
while (true) {
path.add(g[i][j]);
int ni = -1, nj = -1;
for (int[] d : D) {
int x = i + d[0], y = j + d[1];
if (x >= 0 && y >= 0 && x < g.length && y < g[0].length && g[x][y] > g[i][j]
&& memo[x][y] == memo[i][j] - 1) { ni = x; nj = y; break; }
}
if (ni < 0) break;
i = ni; j = nj;
}
return path;
}
public static void main(String[] args) {
System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
System.out.println(trap(new int[]{4, 2, 0, 3, 2, 5}));
System.out.println(countPaths(new int[][]{{1, 1}, {3, 4}}));
System.out.println(countPaths(new int[][]{{1}, {2}}));
System.out.println(bestClimb(new int[][]{{9, 9, 4}, {6, 6, 8}, {2, 1, 1}}));
System.out.println(bestClimb(new int[][]{{3, 4, 5}, {3, 2, 6}, {2, 2, 1}}));
}
}
Output (real):
6
9
8
3
[1, 2, 6, 9]
[3, 4, 5, 6]
Quick quiz
How many toffees does candy([1, 2, 3, 2, 1]) need? A) 5 B) 7 C) 9 D) 11
Answer
C) 9. Left pass 1 2 3 1 1, right pass 1 1 3 2 1, max 1 2 3 2 1, total 9.
Interview questions
- Why is the two-pass answer the minimum, not just valid?
left[i]is the length of the rising run ending atifrom the left: any valid answer needs at least that many fori. The same holds forright[i]. So every valid answer gives at leastmax(left[i], right[i]), and that assignment is itself valid. - Can candy be solved in O(1) extra memory? Yes: walk once, counting the lengths of the current rising and falling slopes and adding
1 + 2 + … + kfor each slope; the peak takes the longer of its two slopes. Harder to get right in an interview; the two-pass version is the expected answer. - Why is memoization safe in the hill problem? Moves are strictly increasing, so the graph of moves has no cycles (a DAG); the value of
climb(i, j)can't depend on itself. - What would break with
>=? Equal neighbours form a cycle; the recursion bounces between them forever:StackOverflowError. - How do you avoid deep recursion? Topological order by height: count each cell's number of lower neighbours, run Kahn's algorithm (episode 51) layer by layer from the lowest cells, or simply process cells sorted by height from highest to lowest and set
dp = 1 + max(dp of higher neighbours). The number of layers is the answer. - Time and space? Candy O(n) time, O(n) memory. Hill O(m·n) time (4 neighbours per cell), O(m·n) memo plus the recursion stack.
- In a real interview, what if you only find the brute force? Code it cleanly, give its complexity, and explain where the repeated work is. A correct, well-explained brute force is worth far more than a broken optimal one.
Glossary
| Term | Meaning |
|---|---|
| Mock interview | A practice interview: one person plays the interviewer |
| Clarifying question | A question asked before coding to make the problem exact |
| Constraint | A limit on the input that tells you which complexity is fast enough |
| Brute force | The direct, try-everything correct method |
| Greedy | Take the locally best choice at every step |
| Pass | One walk over the whole array |
| Neighbour | The element next to another (array) or the cell above/below/left/right (grid) |
| Grid / matrix | A table of numbers in rows and columns |
| Path | A sequence of cells, each a neighbour of the one before |
| Strictly higher | Greater than, not equal (>) |
| DFS | Depth-first search: go as deep as possible, then back up |
| Recursion | A function calling itself on a smaller problem |
| Call stack | Memory holding one frame per unfinished function call |
| StackOverflowError | Java's error when the call stack runs out |
| Cycle | A route that returns to its start |
| DAG | Directed acyclic graph: one-way arrows, no cycles |
| Memoization | Store each subproblem's answer the first time, reuse it later |
| Dynamic programming | Solve each subproblem once and reuse the stored answers |
| Overflow | A value too large for its type (int max 2,147,483,647) |
| Time Limit Exceeded | The program ran longer than the judge allows |
Summary
- Run every interview problem the same way: clarify, examples, brute force and its cost, find the waste, the insight, code out loud, test, complexity.
- Candy: a rule with two sides becomes two passes (left to right, right to left) and a
max: O(n). Overwriting instead ofmaxgives 9 instead of 11; the total needs along. - Longest increasing path: moving only to strictly higher cells makes a DAG, so the longest climb from each cell is fixed and can be memoised: O(m·n).
>=creates cycles and aStackOverflowError; DFS without the memo is exponential.- That's the whole DSA course, 90 episodes. Next on SyntaxPilot: the Competitive Programming course, where these patterns meet real contest problems in C++.