</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

Grid and Position DP

What is this?

Each of these indexes by a position and needs exactly one extra coordinate to close the recurrence. A grid cell needs nothing more, because the strictly-increasing rule makes the graph acyclic on its own. Typing needs to know where the other finger is. Shelving needs to know where the current row started. Scheduling needs to know the last job that finished in time, which is a binary search rather than a loop.

Grid and Position: state = position plus one extra coordinate (flowchart)

Fun fact: Minimum Distance to Type a Word Using Two Fingers looks like it needs a state of (index, finger1, finger2): 27 × 27 finger placements at every index (26 letters plus a "not placed yet" slot). It does not. After typing word[i−1], one of the fingers is necessarily on word[i−1], which is already known from the index. So only the other finger's position needs storing, and the state collapses to (index, other). Recognising that part of a state is implied by the rest is one of the most reliable ways to turn a DP that will not fit into one that does.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.


Rule of thumb: write down the smallest thing you must remember besides the position. Anything the index already implies is not state, and removing it is usually the difference between passing and timing out.


1. When the rule makes it acyclic

@lru_cache(None)
def go(r, c):
    best = 1
    for nr, nc in neighbours(r, c):
        if mat[nr][nc] > mat[r][c]:            # strictly greater → no cycles possible
            best = max(best, 1 + go(nr, nc))
    return best
return max(go(r, c) for r in range(m) for c in range(n))

No visited set is needed, and that is the point worth saying aloud: because every step strictly increases, a path can never return to a cell it has left. The memo makes each cell computed once, giving O(mn).

The catch is recursion depth. On a 200 by 200 grid that climbs in a snake, the DFS goes about 40,000 frames deep, and Python's default limit is 1000. The lesson's third approach avoids recursion: count each cell's larger neighbours (its out-degree), peel off the cells with out-degree 0 as layer 1, then repeat. The number of layers is the answer, still O(mn).

2. When part of the state is implied

@lru_cache(None)
def go(i, other):                              # other = the finger NOT on word[i-1]
    if i == len(word): return 0
    prev = word[i-1] if i else None
    return min(dist(prev,  word[i]) + go(i+1, other),   # same finger continues
               dist(other, word[i]) + go(i+1, prev))    # the other finger moves

Two choices per character, and None (no finger placed yet) costs zero to move from, which handles the first two characters without a special case. Distance is Manhattan on the 6-wide keyboard grid: divmod(ord(ch) - ord('A'), 6). The word has 2 to 300 letters, and since each row of the table depends only on the next, the bottom-up version needs just O(27) space.

3. When the choice is where the group begins

for i in range(1, n + 1):
    w = h = 0
    for j in range(i, 0, -1):                  # books j..i share the last shelf
        w += books[j-1][0]
        if w > shelf_width: break              # cannot widen further
        h = max(h, books[j-1][1])
        dp[i] = min(dp[i], dp[j-1] + h)

Walking backwards from i is what lets the width accumulate incrementally and the break fire as soon as the shelf is full. Books must stay in order, which is why "which books share the last shelf" is always a contiguous suffix, and that is the fact that makes the whole DP work.

Greedy (fill each shelf as full as possible) loses. With books [[1,1],[1,2],[2,2]] and shelfWidth = 3, greedy puts books 1 and 2 together and book 3 alone for a height of 4. Book 1 alone and books 2 and 3 together gives 3.

4. When the transition is a binary search

jobs = sorted(zip(end, start, profit))         # sorted by end time
ends = [j[0] for j in jobs]
dp = [0] * (n + 1)                             # dp[i] = best using the first i jobs
for i in range(1, n + 1):
    e, s, p = jobs[i - 1]
    k = bisect_right(ends, s, 0, i - 1)        # jobs finishing at or before s
    dp[i] = max(dp[i - 1], p + dp[k])          # skip it, or take it
return dp[n]

Sorting by end time is what makes ends increasing and therefore searchable, and it makes the compatible jobs a prefix of the sorted list. dp[i] never decreases, so dp[n] is the answer. This is the weighted version of interval scheduling. It is not the unweighted LeetCode 1353 problem, which is a different task.


5. A 30-second worked example (two fingers)

word = "CAKE" on a 6-wide keyboard: A is (0,0), C is (0,2), E is (0,4), K is (1,4).
Distances: C→A = 2, C→K = 3, A→K = 5, K→E = 1.

Two Fingers worked example: greedy 4 vs optimum 3

The greedy's free move at step 2 is what costs it. Placing the second finger on A looks like a saving of 2 and leaves both fingers stranded on the left of the keyboard, while K and E are both on the right. Paying the 2 to keep a finger free is worth it, and no rule about the current character can see that, which is exactly why the problem is a DP.


6. Where you'll actually meet this

  • Text layout. Filling shelves is the same recurrence as breaking a paragraph into lines under a width limit, where each line costs its tallest item.
  • Revenue management. Weighted job scheduling underlies ad slots, meeting rooms and rental bookings.
  • Terrain. Longest increasing path is the longest uphill walk over a height map.
  • Keyboard layout. Finger travel distance is a common way to compare layouts.
  • Resource planning. "Group consecutive items under a capacity limit" appears in shipping, batching and pagination.

7. Problems in this chapter

Longest Increasing Path in a Matrix

Longest strictly increasing path. Memoized DFS: the increase rule makes cycles impossible, so no visited set is needed. A snake grid recurses about 40,000 deep, so know the iterative peeling version too.
Pattern: memoized DFS on an implicit DAG. Target: O(mn) time and space.

Minimum Distance to Type a Word Using Two Fingers

Least total finger travel (Manhattan distance, word length 2 to 300). State is (index, other finger) because one finger is always on the previous character.
Pattern: DP with an implied state component. Target: O(n · 27) time, O(27) space bottom-up.

Filling Bookcase Shelves

Least total height with books kept in order. For each prefix, try every contiguous suffix as the last shelf. Greedy filling is wrong.
Pattern: prefix DP over contiguous groups. Target: O(n²) time, O(n) space.

Maximum Profit in Job Scheduling

Maximum profit from non-overlapping jobs. Sort by end time and binary-search the last compatible job.
Pattern: DP + binary search. Target: O(n log n) time, O(n) space.


8. Common pitfalls

  • Adding a visited set to the increasing path. Strict increase already forbids revisiting, and the set breaks the memo.
  • Storing both finger positions. One of them is implied by the index, so the state is 27 values per index, not 27 × 27.
  • Walking shelves forward. Backwards accumulation is what lets the width check break early.
  • Forgetting books must stay in order, which is what makes the last shelf a contiguous suffix.
  • Sorting jobs by start time. End time is what makes the binary search possible.
  • Using bisect_left on the ends array. A job that ends exactly when the next begins is compatible, so you need bisect_right (the count of ends at or below the start).
  • Greedy shelf filling. Packing each shelf as full as possible can lose, as the [[1,1],[1,2],[2,2]] example shows.
  • Recursive longest path on a big grid in Python. A snake overflows the default recursion limit.
  • Memoising on mutable state. Keys must be the position and the small extra coordinate, nothing else.

9. Key takeaways

  1. State = position + the smallest thing you must remember. Anything implied is not state.
  2. A strict-increase rule gives you a DAG for free: no visited set, no cycle handling.
  3. Contiguity is a gift. "Books stay in order" is what makes the shelf a suffix.
  4. Sort to make a transition searchable. By end time, then bisect.
  5. Keeping a DP array monotonic means the answer is always its last element.
  6. None as an initial position removes the special case for the first move.
  7. Why interviewers like it: the naive state is always writable and always too big, so collapsing it is the visible skill.

Order: Longest Increasing Path in a Matrix → Minimum Distance to Type a Word Using Two Fingers → Filling Bookcase Shelves → Maximum Profit in Job Scheduling.

Maximum Profit in Job Scheduling

Core idea: Each job is an interval [start, end] worth some profit, and you may only run jobs that don't overlap in time. Sort all jobs by end time. Then build a DP table where dp[i] is the best profit achievable using only the first i jobs (in end-sorted order). For job i, you face a clean binary choice: skip it and keep dp[i-1], or take it and earn profit_i plus the best you could have made from jobs that finish at or before this job's start. That last quantity is dp[p(i)], where p(i) is the index of the last job whose end ≤ start_i, found by binary search because the jobs are sorted by end. So dp[i] = max(dp[i-1], profit_i + dp[p(i)]). Sorting is O(n log n), and each of the n jobs does one O(log n) binary search, giving O(n log n) overall. This is the textbook weighted interval scheduling algorithm.


Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.