Triangle (Min Path Sum)

🎯

Triangle (Min Path Sum)

mediumDPAmazonMicrosoft

Imagine you are climbing down a triangular mountain path where each step has a cost. You want to find the path from the top to the bottom with the minimum total cost.

💡 This problem is a classic example of grid-based dynamic programming where you must find an optimal path with minimum sum. Beginners often struggle because the triangle shape means each row has a different length, and the path choices depend on previous decisions, making brute force inefficient.

📋

Problem Statement

Given a triangle array, return the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. Formally, if you are on index i on the current row, you may move to either index i or i+1 on the next row.

1 ≤ number of rows ≤ 200Triangle elements are integers in the range [-10^4, 10^4]

💡

Example

Input"[[2],[3,4],[6,5,7],[4,1,8,3]]"

Output11

The minimum path is 2 → 3 → 5 → 1, which sums to 11.

• Triangle with only one row → output is that single element
• Triangle with negative numbers → path sum can be negative
• Triangle where all elements are equal → output is that element times number of rows
• Triangle with large values → test for integer overflow or performance

🔁

Why DP?

Why greedy fails:

A greedy approach that picks the minimum adjacent number at each step can fail because a locally minimal choice may lead to a suboptimal overall path. For example, choosing the smaller number at the second row might force a larger sum later.

DP state:

dp[i][j] represents the minimum path sum to reach element j in row i from the top.

Recurrence:dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j])

The minimum path sum to position j in row i is the value at that position plus the minimum of the two possible positions above it.

⚠️

Common Mistakes

Not handling base case correctly in recursion

Stack overflow or incorrect results

✅ Add explicit base case when reaching last row to return value directly

Forgetting to memoize results in top-down DP

Solution still runs exponentially slow

✅ Use a cache to store and reuse computed results

Index out of bounds when accessing dp or triangle arrays

Runtime errors or crashes

✅ Ensure loops and recursive calls respect triangle row lengths

Updating dp array in wrong order in bottom-up approach

Incorrect results due to overwritten values

✅ Iterate from bottom row upwards and update dp carefully

Using extra space unnecessarily in bottom-up approach

Higher memory usage than needed

✅ Use a single 1D dp array updated in place

🧠

Brute Force (Pure Recursion)

💡 This approach helps understand the problem's recursive structure and why naive recursion is inefficient due to repeated calculations.

Intuition

At each position, recursively explore both possible moves down the triangle and choose the minimum path sum.

Algorithm

1. Start at the top of the triangle (row 0, index 0).
2. Recursively compute the minimum path sum for the two adjacent positions in the next row.
3. Return the current value plus the minimum of the two recursive calls.
4. The base case is when we reach the last row, where we return the value itself.

💡 The recursion tree grows exponentially because each call branches into two, making it hard to track without memoization.

Recurrence:minPath(i,j) = triangle[i][j] + min(minPath(i+1,j), minPath(i+1,j+1))

</>

Code

from typing import List

def minimumTotal(triangle: List[List[int]]) -> int:
    def dfs(i, j):
        if i == len(triangle) - 1:
            return triangle[i][j]
        left = dfs(i + 1, j)
        right = dfs(i + 1, j + 1)
        return triangle[i][j] + min(left, right)

    return dfs(0, 0)

# Example usage
if __name__ == "__main__":
    tri = [[2],[3,4],[6,5,7],[4,1,8,3]]
    print(minimumTotal(tri))  # Output: 11

Line Notes

def dfs(i, j):Defines recursive helper to compute min path sum from position (i,j)

if i == len(triangle) - 1:Base case: last row reached, return value directly

left = dfs(i + 1, j)Recurse to the adjacent number directly below

right = dfs(i + 1, j + 1)Recurse to the adjacent number diagonally below

return triangle[i][j] + min(left, right)Add current value to minimum of two recursive paths

import java.util.*;

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        return dfs(triangle, 0, 0);
    }

    private int dfs(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size() - 1) {
            return triangle.get(i).get(j);
        }
        int left = dfs(triangle, i + 1, j);
        int right = dfs(triangle, i + 1, j + 1);
        return triangle.get(i).get(j) + Math.min(left, right);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        List<List<Integer>> tri = new ArrayList<>();
        tri.add(Arrays.asList(2));
        tri.add(Arrays.asList(3,4));
        tri.add(Arrays.asList(6,5,7));
        tri.add(Arrays.asList(4,1,8,3));
        System.out.println(sol.minimumTotal(tri)); // 11
    }
}

Line Notes

public int minimumTotal(List<List<Integer>> triangle)Entry point calling recursive helper

if (i == triangle.size() - 1)Base case: last row reached

int left = dfs(triangle, i + 1, j);Recurse down to left adjacent

int right = dfs(triangle, i + 1, j + 1);Recurse down to right adjacent

return triangle.get(i).get(j) + Math.min(left, right);Add current value to min of recursive results

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int dfs(const vector<vector<int>>& triangle, int i, int j) {
        if (i == triangle.size() - 1) return triangle[i][j];
        int left = dfs(triangle, i + 1, j);
        int right = dfs(triangle, i + 1, j + 1);
        return triangle[i][j] + min(left, right);
    }

    int minimumTotal(vector<vector<int>>& triangle) {
        return dfs(triangle, 0, 0);
    }
};

int main() {
    Solution sol;
    vector<vector<int>> tri = {{2},{3,4},{6,5,7},{4,1,8,3}};
    cout << sol.minimumTotal(tri) << endl; // 11
    return 0;
}

Line Notes

int dfs(const vector<vector<int>>& triangle, int i, int j)Recursive helper to compute min path sum

if (i == triangle.size() - 1) return triangle[i][j];Base case: last row reached

int left = dfs(triangle, i + 1, j);Recurse to left adjacent below

int right = dfs(triangle, i + 1, j + 1);Recurse to right adjacent below

return triangle[i][j] + min(left, right);Add current value to minimum of recursive calls

function minimumTotal(triangle) {
    function dfs(i, j) {
        if (i === triangle.length - 1) return triangle[i][j];
        const left = dfs(i + 1, j);
        const right = dfs(i + 1, j + 1);
        return triangle[i][j] + Math.min(left, right);
    }
    return dfs(0, 0);
}

// Example usage
const tri = [[2],[3,4],[6,5,7],[4,1,8,3]];
console.log(minimumTotal(tri)); // 11

Line Notes

function dfs(i, j)Recursive helper function for min path sum

if (i === triangle.length - 1) return triangle[i][j];Base case: last row reached

const left = dfs(i + 1, j);Recurse down left adjacent

const right = dfs(i + 1, j + 1);Recurse down right adjacent

return triangle[i][j] + Math.min(left, right);Add current value to min of recursive calls

⏱

Complexity

TimeO(2^n)

SpaceO(n) recursion stack

Each step branches into two recursive calls, leading to exponential growth in calls.

💡 For n=15 rows, this means over 32,000 calls, which is too slow for interviews.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem structure.

🧠

Top-Down DP with Memoization

💡 Memoization avoids recomputing the same subproblems by caching results, drastically improving efficiency.

Intuition

Store results of recursive calls in a cache so that repeated calls return instantly instead of recomputing.

Algorithm

1. Initialize a cache (2D array) to store minimum path sums for each position.
2. Modify the recursive function to check the cache before computing.
3. If cached, return the stored value; otherwise compute and store it.
4. Return the cached result for the top position.

💡 Memoization transforms exponential recursion into polynomial time by eliminating duplicate work.

Recurrence:dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])

</>

Code

from typing import List

def minimumTotal(triangle: List[List[int]]) -> int:
    n = len(triangle)
    memo = [[None]*len(row) for row in triangle]

    def dfs(i, j):
        if i == n - 1:
            return triangle[i][j]
        if memo[i][j] is not None:
            return memo[i][j]
        left = dfs(i + 1, j)
        right = dfs(i + 1, j + 1)
        memo[i][j] = triangle[i][j] + min(left, right)
        return memo[i][j]

    return dfs(0, 0)

# Example usage
if __name__ == "__main__":
    tri = [[2],[3,4],[6,5,7],[4,1,8,3]]
    print(minimumTotal(tri))  # Output: 11

Line Notes

memo = [[None]*len(row) for row in triangle]Initialize cache with None to mark uncomputed states

if memo[i][j] is not None:Return cached result if available to avoid recomputation

memo[i][j] = triangle[i][j] + min(left, right)Store computed minimum path sum in cache

return memo[i][j]Return cached or newly computed result

import java.util.*;

public class Solution {
    private Integer[][] memo;

    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        memo = new Integer[n][];
        for (int i = 0; i < n; i++) {
            memo[i] = new Integer[triangle.get(i).size()];
        }
        return dfs(triangle, 0, 0);
    }

    private int dfs(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size() - 1) {
            return triangle.get(i).get(j);
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        int left = dfs(triangle, i + 1, j);
        int right = dfs(triangle, i + 1, j + 1);
        memo[i][j] = triangle.get(i).get(j) + Math.min(left, right);
        return memo[i][j];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        List<List<Integer>> tri = new ArrayList<>();
        tri.add(Arrays.asList(2));
        tri.add(Arrays.asList(3,4));
        tri.add(Arrays.asList(6,5,7));
        tri.add(Arrays.asList(4,1,8,3));
        System.out.println(sol.minimumTotal(tri)); // 11
    }
}

Line Notes

memo = new Integer[n][];Initialize memo array with nulls to mark uncomputed states

if (memo[i][j] != null)Return cached result if available

memo[i][j] = triangle.get(i).get(j) + Math.min(left, right);Store computed minimum path sum

return memo[i][j];Return cached or computed result

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
    vector<vector<int>> memo;
public:
    int dfs(const vector<vector<int>>& triangle, int i, int j) {
        if (i == triangle.size() - 1) return triangle[i][j];
        if (memo[i][j] != INT_MAX) return memo[i][j];
        int left = dfs(triangle, i + 1, j);
        int right = dfs(triangle, i + 1, j + 1);
        memo[i][j] = triangle[i][j] + min(left, right);
        return memo[i][j];
    }

    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        memo.assign(n, vector<int>(n, INT_MAX));
        return dfs(triangle, 0, 0);
    }
};

int main() {
    Solution sol;
    vector<vector<int>> tri = {{2},{3,4},{6,5,7},{4,1,8,3}};
    cout << sol.minimumTotal(tri) << endl; // 11
    return 0;
}

Line Notes

memo.assign(n, vector<int>(n, INT_MAX));Initialize memo with sentinel INT_MAX to mark uncomputed

if (memo[i][j] != INT_MAX) return memo[i][j];Return cached result if computed

memo[i][j] = triangle[i][j] + min(left, right);Store computed minimum path sum

return memo[i][j];Return cached or computed result

function minimumTotal(triangle) {
    const n = triangle.length;
    const memo = Array.from({length: n}, (v, i) => Array(triangle[i].length).fill(null));

    function dfs(i, j) {
        if (i === n - 1) return triangle[i][j];
        if (memo[i][j] !== null) return memo[i][j];
        const left = dfs(i + 1, j);
        const right = dfs(i + 1, j + 1);
        memo[i][j] = triangle[i][j] + Math.min(left, right);
        return memo[i][j];
    }

    return dfs(0, 0);
}

// Example usage
const tri = [[2],[3,4],[6,5,7],[4,1,8,3]];
console.log(minimumTotal(tri)); // 11

Line Notes

const memo = Array.from({length: n}, (v, i) => Array(triangle[i].length).fill(null));Initialize memo array with nulls

if (memo[i][j] !== null) return memo[i][j];Return cached result if available

memo[i][j] = triangle[i][j] + Math.min(left, right);Store computed minimum path sum

return memo[i][j];Return cached or computed result

⏱

Complexity

TimeO(n^2)

SpaceO(n^2) for memo and recursion stack

Each subproblem is computed once and stored, reducing exponential calls to polynomial.

💡 For n=200 rows, this means about 40,000 computations, which is efficient enough.

Interview Verdict: Accepted

Memoization makes the solution efficient and acceptable for interviews.

🧠

Bottom-Up DP (Tabulation)

💡 This approach builds the solution from the bottom row up, avoiding recursion and making the process iterative and clear.

Intuition

Start from the last row and iteratively compute minimum path sums for each upper row by adding the current value to the minimum of the two adjacent values below.

Algorithm

1. Initialize a dp array as a copy of the last row of the triangle.
2. Iterate from the second last row up to the top row.
3. For each element, update dp[j] as triangle[i][j] plus min(dp[j], dp[j+1]).
4. After processing the top row, dp[0] contains the minimum path sum.

💡 This approach uses a single dp array updated in place, making it space efficient and easy to understand.

Recurrence:dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])

</>

Code

from typing import List

def minimumTotal(triangle: List[List[int]]) -> int:
    dp = triangle[-1][:]
    for i in range(len(triangle) - 2, -1, -1):
        for j in range(len(triangle[i])):
            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
    return dp[0]

# Example usage
if __name__ == "__main__":
    tri = [[2],[3,4],[6,5,7],[4,1,8,3]]
    print(minimumTotal(tri))  # Output: 11

Line Notes

dp = triangle[-1][:]Initialize dp with last row values as base case

for i in range(len(triangle) - 2, -1, -1):Iterate from second last row up to top

for j in range(len(triangle[i])):Iterate over elements in current row

dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])Update dp[j] with current value plus min of two below

import java.util.*;

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = triangle.get(n - 1).get(i);
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        List<List<Integer>> tri = new ArrayList<>();
        tri.add(Arrays.asList(2));
        tri.add(Arrays.asList(3,4));
        tri.add(Arrays.asList(6,5,7));
        tri.add(Arrays.asList(4,1,8,3));
        System.out.println(sol.minimumTotal(tri)); // 11
    }
}

Line Notes

int[] dp = new int[n];Create dp array to store min path sums for last row

dp[i] = triangle.get(n - 1).get(i);Initialize dp with last row values

for (int i = n - 2; i >= 0; i--)Iterate from second last row up to top

dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);Update dp[j] with current value plus min of two below

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> dp = triangle.back();
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
            }
        }
        return dp[0];
    }
};

int main() {
    Solution sol;
    vector<vector<int>> tri = {{2},{3,4},{6,5,7},{4,1,8,3}};
    cout << sol.minimumTotal(tri) << endl; // 11
    return 0;
}

Line Notes

vector<int> dp = triangle.back();Initialize dp with last row values

for (int i = n - 2; i >= 0; i--)Iterate from second last row up to top

for (int j = 0; j <= i; j++)Iterate over elements in current row

dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);Update dp[j] with current value plus min of two below

function minimumTotal(triangle) {
    let dp = triangle[triangle.length - 1].slice();
    for (let i = triangle.length - 2; i >= 0; i--) {
        for (let j = 0; j < triangle[i].length; j++) {
            dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]);
        }
    }
    return dp[0];
}

// Example usage
const tri = [[2],[3,4],[6,5,7],[4,1,8,3]];
console.log(minimumTotal(tri)); // 11

Line Notes

let dp = triangle[triangle.length - 1].slice();Copy last row into dp array

for (let i = triangle.length - 2; i >= 0; i--)Iterate from second last row up to top

for (let j = 0; j < triangle[i].length; j++)Iterate over elements in current row

dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]);Update dp[j] with current value plus min of two below

⏱

Complexity

TimeO(n^2)

SpaceO(n)

We process each element once and use a single dp array of size n.

💡 For n=200 rows, this means about 40,000 operations and only 200 space used.

Interview Verdict: Accepted

This is the preferred approach in interviews due to clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 Bottom-up DP with space optimization is the best choice for interviews due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down DP with Memoization	O(n^2)	O(n^2) memo + O(n) recursion stack	Possible but less likely	Yes	Good to mention and code if comfortable
3. Bottom-Up DP (Tabulation)	O(n^2)	O(n)	No	Yes	Preferred approach to code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force recursive approach to show understanding of the problem structure.Introduce memoization to optimize recursion and avoid repeated work.Present the bottom-up DP approach for iterative clarity and space optimization.Write clean code and test with sample and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of recursion, dynamic programming concepts, optimization techniques, and ability to write clean, bug-free code.

Common Follow-ups

• Can you optimize space usage further? → Use 1D dp array as shown in bottom-up approach.
• What if the triangle is very large? → Discuss time and space complexity and possible pruning.

💡 Follow-ups often test your ability to optimize space and handle large inputs efficiently.

🔍

Pattern Recognition

When to Use

1) Problem involves grid or triangle structure; 2) Need to find min/max path sum; 3) Choices depend on adjacent positions; 4) Overlapping subproblems exist.

Signature Phrases

'minimum path sum from top to bottom''move to adjacent numbers on the row below'

NOT This Pattern When

Problems that require global path sums without adjacency constraints or that use greedy approaches exclusively.

Similar Problems

Minimum Path Sum - similar grid DP with fixed directionsUnique Paths II - grid DP with obstacles

Practice

1. Consider the following Python code implementing the Cherry Pickup problem using bottom-up DP. Given the input grid below, what is the final returned value?

grid = [
  [0, 1, -1],
  [1, 0, -1],
  [1, 1,  1]
]

from typing import List

def cherryPickup(grid: List[List[int]]) -> int:
    n = len(grid)
    dp = [[[-float('inf')] * n for _ in range(n)] for __ in range(n)]
    dp[0][0][0] = grid[0][0]
    for step in range(1, 2 * (n - 1) + 1):
        for r1 in range(max(0, step - (n - 1)), min(n, step + 1)):
            c1 = step - r1
            if c1 < 0 or c1 >= n:
                continue
            for r2 in range(max(0, step - (n - 1)), min(n, step + 1)):
                c2 = step - r2
                if c2 < 0 or c2 >= n:
                    continue
                if grid[r1][c1] == -1 or grid[r2][c2] == -1:
                    continue
                candidates = []
                if r1 > 0 and r2 > 0:
                    candidates.append(dp[r1 - 1][c1][r2 - 1])
                if r1 > 0 and c2 > 0:
                    candidates.append(dp[r1 - 1][c1][r2])
                if c1 > 0 and r2 > 0:
                    candidates.append(dp[r1][c1 - 1][r2 - 1])
                if c1 > 0 and c2 > 0:
                    candidates.append(dp[r1][c1 - 1][r2])
                best_prev = max(candidates) if candidates else -float('inf')
                if best_prev == -float('inf'):
                    continue
                val = best_prev + grid[r1][c1]
                if r1 != r2:
                    val += grid[r2][c2]
                dp[r1][c1][r2] = max(dp[r1][c1][r2], val)
    return max(0, dp[n - 1][n - 1][n - 1])

print(cherryPickup(grid))

easy

A. 6

B. 5

C. 4

D. 3

Solution

1. Step 1: Trace dp states for step=4 (final step for 3x3 grid)

   At step=4, both players reach bottom-right (2,2). The dp value dp[2][2][2] accumulates max cherries collected along valid paths avoiding thorns (-1).

2. Step 2: Calculate max cherries collected

   By tracing paths, max cherries collected is 6, considering both players' paths and avoiding double counting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Manual path tracing confirms max cherries = 6 [OK]

Hint: Trace dp at final step for both players [OK]

Common Mistakes:

• Off-by-one errors in step or indices
• Double counting cherries when players overlap
• Ignoring thorn cells leading to invalid paths

2. You are given a grid of non-negative integers representing costs. Starting from the top-left corner, you want to reach the bottom-right corner by moving only down or right, minimizing the total cost along the path. Which algorithmic approach guarantees finding the minimum total cost efficiently?

easy

A. A greedy algorithm that always moves to the adjacent cell with the smallest cost

B. Dynamic programming that builds up solutions from smaller subproblems using a grid-based state

C. Pure brute force recursion exploring all possible paths without memoization

D. Divide and conquer by splitting the grid into halves and solving independently

Solution

1. Step 1: Understand problem constraints

   The problem requires minimizing path cost with only down or right moves, which naturally forms overlapping subproblems.

2. Step 2: Identify suitable algorithmic pattern

   Dynamic programming efficiently solves overlapping subproblems by storing intermediate results, unlike greedy which can fail on some grids, brute force which is exponential, or divide and conquer which doesn't handle dependencies well.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP uses subproblem solutions to build the answer bottom-up [OK]

Hint: DP handles overlapping subproblems and optimal substructure [OK]

Common Mistakes:

• Assuming greedy always works for grid path problems
• Thinking brute force is efficient enough
• Believing divide and conquer applies without overlapping subproblems

3. Consider the following bottom-up DP code for the Strange Printer problem. What is the final returned value when the input string is "aba"?

easy

A. 3

B. 4

C. 1

D. 2

Solution

1. Step 1: Compress input string "aba"

   Compression does not change string since no consecutive duplicates: s = "aba", n=3.

2. Step 2: Trace dp table filling

   Base cases: dp[0][0]=1, dp[1][1]=1, dp[2][2]=1. For length=2: - dp[0][1]: dp[0][0]+1=2, s[0]!=s[1], so dp[0][1]=2 - dp[1][2]: dp[1][1]+1=2, s[1]!=s[2], so dp[1][2]=2 For length=3: - dp[0][2]: dp[0][1]+1=3 Check k=0: s[0]==s[2] ('a'=='a'), dp[0][0]+dp[1][1]=1+1=2 < 3, so dp[0][2]=2

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches known minimal turns for "aba" [OK]

Hint: Check dp merging when s[k] == s[j] reduces turns [OK]

Common Mistakes:

• Forgetting to merge intervals when characters match

4. What is the time complexity of the bottom-up dynamic programming solution for the minimum falling path sum problem on an n x n matrix?

medium

A. O(n^2) because each cell is processed once with constant neighbor checks

B. O(n) as only one row is stored at a time

C. O(3^n) since each step has three choices recursively

D. O(n^3) due to nested loops and checking three neighbors

Solution

1. Step 1: Identify loops in the bottom-up DP

   There are two nested loops: outer over rows (n), inner over columns (n).

2. Step 2: Analyze work per cell

   Each cell checks up to three neighbors in O(1) time, so total work is O(n * n) = O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP processes each cell once with constant neighbor checks [OK]

Hint: Two nested loops over n rows and n columns [OK]

Common Mistakes:

• Confusing recursive exponential with DP complexity
• Assuming neighbor checks multiply complexity

5. The following code attempts to solve the Strange Printer problem using bottom-up DP. Which line contains a subtle bug that can cause incorrect results on inputs like "aba"?

medium

A. Line 18: dp[i][j] = dp[i][j - 1] + 1 assignment

B. Line 13: dp[i][i] = 1 initialization

C. Line 4: compressed.append(c) without checking for duplicates

D. Line 21: if s[k] == s[j] condition

Solution

1. Step 1: Identify compression step

   Line 4 appends every character without checking if it equals the last compressed character, so no compression occurs.

2. Step 2: Understand impact of missing compression

   Without compression, the DP runs on the full string length, causing inefficiency and possibly incorrect merges, especially on inputs like "aba" where compression reduces complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Compression step must skip duplicates to optimize DP [OK]

Hint: Compression must skip consecutive duplicates to avoid TLE and errors [OK]

Common Mistakes:

• Forgetting to compress string before DP