Longest Increasing Path in a Matrix

📋

Longest Increasing Path in a Matrix

Edge cases:

</>

IDE

def longestIncreasingPath(matrix: List[List[int]]) -> int:public int longestIncreasingPath(int[][] matrix)int longestIncreasingPath(vector<vector<int>>& matrix)function longestIncreasingPath(matrix)

def longestIncreasingPath(matrix: List[List[int]]) -> int:
    # Write your solution here
    pass

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int longestIncreasingPath(vector<vector<int>>& matrix) {
    // Write your solution here
    return 0;
}

function longestIncreasingPath(matrix) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Not handling empty matrix or empty rows, returning default 0 incorrectly.✅ Add check: if not matrix or not matrix[0]: return 0.

Wrong: 1Returning 1 for all inputs due to missing DFS or memoization logic.✅ Implement DFS with memoization to explore all increasing paths and find max length.

Wrong: Incorrect max length less than actualGreedy approach picking only immediate max neighbor, missing longer paths.✅ Use DFS with memoization exploring all neighbors, not greedy choice.

Wrong: Off-by-one length (e.g. 4 instead of 5)Not counting current cell as length 1 or incorrect initialization of max length.✅ Initialize max_len=1 at each cell and add 1 to neighbor's dfs result.

Wrong: Counting equal neighbors as increasingUsing >= instead of > in neighbor comparison.✅ Change condition to matrix[x][y] > matrix[i][j].

✓

Test Cases

Focus on handling base cases like empty matrix and single cell correctly.

Watch out for greedy traps and off-by-one errors in path length counting.

Optimize your solution with memoization to handle large inputs efficiently.

t1_01basic

Input{"matrix":[[9,9,4],[6,6,8],[2,1,1]]}

Expected4

⏱ Performance - must finish in 2000ms

The longest increasing path is [1, 2, 6, 9].

💡 Consider exploring all cells and using DFS to find increasing paths.

💡 Use memoization to store longest path starting from each cell to avoid recomputation.

💡 Implement DFS with memo to return max length from each cell and take global max.

Why it failed: Returned value incorrect - likely missing memoization causing repeated DFS and wrong max length. Fix by caching results per cell.

✓ Correctly computes longest increasing path using DFS with memoization.

t1_02basic

Input{"matrix":[[3,4,5],[3,2,6],[2,2,1]]}

Expected4

⏱ Performance - must finish in 2000ms

Longest path is [3,4,5,6] or [2,3,4,5], length 4.

💡 Check neighbors with strictly greater values to continue path.

💡 Memoize results to avoid recomputing paths from same cells.

💡 Return max length found among all cells after DFS with memo.

Why it failed: Incorrect output due to not enforcing strictly increasing condition or missing memoization. Fix by checking matrix[x][y] > matrix[i][j] and caching results.

✓ Correctly finds longest strictly increasing path length.

t2_01edge

Input{"matrix":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty matrix has no cells, so longest path length is 0.

💡 Check for empty matrix or empty rows before processing.

💡 Return 0 immediately if matrix or matrix[0] is empty.

💡 Add guard clause at start to handle empty input.

Why it failed: Code crashes or returns non-zero on empty input. Fix by adding check: if not matrix or not matrix[0]: return 0.

✓ Handles empty matrix input correctly by returning 0.

t2_02edge

Input{"matrix":[[42]]}

Expected1

⏱ Performance - must finish in 2000ms

Single cell matrix has longest path length 1 (the cell itself).

💡 Single cell means no neighbors to move to.

💡 Longest path is just the cell itself, length 1.

💡 Ensure base case returns 1 for any cell with no increasing neighbors.

Why it failed: Returns 0 or wrong length for single cell. Fix by returning 1 when no valid moves from cell.

✓ Correctly returns 1 for single cell matrix.

t2_03edge

Input{"matrix":[[5,4,3],[4,3,2],[3,2,1]]}

Expected1

⏱ Performance - must finish in 2000ms

Matrix strictly decreasing, no increasing moves possible, so longest path length is 1.

💡 Check neighbors strictly greater than current cell to continue path.

💡 If no neighbors are greater, path length is 1 for that cell.

💡 Ensure strict inequality in comparisons.

Why it failed: Incorrectly counts non-increasing neighbors or uses >= instead of >. Fix by enforcing matrix[x][y] > matrix[i][j].

✓ Correctly returns 1 when no increasing neighbors exist.

t2_04edge

Input{"matrix":[[7,7,7],[7,7,7],[7,7,7]]}

Expected1

⏱ Performance - must finish in 2000ms

All elements equal, so longest strictly increasing path length is 1.

💡 Strictly increasing means equal neighbors do not extend path.

💡 Check that neighbors are strictly greater, not equal or less.

💡 Return 1 if no strictly greater neighbors.

Why it failed: Counting equal neighbors as increasing leads to wrong longer path. Fix by using > comparison only.

✓ Correctly returns 1 for matrix with all equal elements.

t3_01corner

Input{"matrix":[[1,2,3],[6,5,4],[7,8,9]]}

Expected5

⏱ Performance - must finish in 2000ms

Longest path is [1,2,3,4,5] or [5,6,7,8,9] length 5, testing greedy trap.

💡 Greedy approach picking local max neighbors may fail.

💡 Use DFS with memoization to explore all paths fully.

💡 Memoize longest path from each cell to avoid greedy mistakes.

Why it failed: Greedy approach fails by choosing immediate max neighbor only. Fix by exploring all neighbors with DFS + memo.

✓ Correctly handles non-greedy longest path calculation.

t3_02corner

Input{"matrix":[[1,2,3],[2,3,4],[3,4,5]]}

Expected5

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in path length calculation; longest path length is 5.

💡 Count current cell as length 1 plus max of neighbors.

💡 Avoid off-by-one by initializing max length to 1 at each cell.

💡 Return dp[i][j] = 1 + max of neighbors' dp values.

Why it failed: Off-by-one error returns length 4 instead of 5. Fix by initializing max_len=1 and adding 1 to neighbor's dfs result.

✓ Correctly computes path length including current cell.

t3_03corner

Input{"matrix":[[1,1,1],[1,1,1],[1,1,1]]}

Expected1

⏱ Performance - must finish in 2000ms

Tests handling of all equal elements; longest path length is 1.

💡 Strictly increasing means equal neighbors do not extend path.

💡 Check that neighbors are strictly greater, not >=.

💡 Return 1 if no strictly greater neighbors.

Why it failed: Incorrectly counts equal neighbors as increasing. Fix by using > comparison, not >=.

✓ Correctly returns 1 for all equal elements matrix.

t4_01performance

Input{"matrix":[[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99],[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101],[3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102],[4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103],[5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104],[6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105],[7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106],[8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107],[9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108]]}

Expectednull

⏱ Performance - must finish in 2000ms

100x100 matrix with increasing rows and columns; O(m*n) DFS+memo must complete within 2s.

💡 Brute force DFS without memoization will TLE due to exponential calls.

💡 Use DFS with memoization to achieve O(m*n) time complexity.

💡 Cache results per cell to avoid recomputation and pass performance.

Why it failed: TLE due to exponential DFS calls without memoization. Fix by adding memoization to DFS.

✓ Efficient O(m*n) DFS with memoization passes performance test.

Practice

1. You have n people and a list of caps each person can wear. You want to count the number of ways to assign unique caps so that each person gets exactly one cap and no two people share the same cap. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Sorting caps and assigning them in ascending order to people

B. Greedy algorithm that assigns the most popular cap first to maximize assignments

C. Simple recursion without memoization, trying all possible assignments

D. Bitmask dynamic programming that uses masks to track assigned caps and iterates over caps

Solution

1. Step 1: Understand the problem constraints

   The problem requires counting all unique assignments where each person gets a unique cap, which involves combinatorial enumeration with uniqueness constraints.

2. Step 2: Identify the suitable approach

   Bitmask DP efficiently tracks which caps are assigned using bitmasks, allowing counting without double counting or missing cases. Greedy or sorting approaches fail to guarantee all unique assignments are counted correctly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask DP is the standard for unique assignment counting problems [OK]

Hint: Use bitmask DP to track assigned caps uniquely [OK]

Common Mistakes:

• Thinking greedy or sorting can count all unique assignments correctly

2. Consider the following Python code implementing the optimized LIS algorithm. What is the value of the variable tails after processing the input [3, 1, 2]?

easy

A. [1, 2, 3]

B. [1, 2]

C. [1, 3]

D. [3, 1, 2]

Solution

1. Step 1: Process num=3

   tails is empty, bisect_left returns 0, append 3 -> tails = [3]

2. Step 2: Process num=1

   bisect_left(tails,1) returns 0, replace tails[0] with 1 -> tails = [1]

3. Step 3: Process num=2

   bisect_left(tails,2) returns 1 (end of tails), append 2 -> tails = [1, 2]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   tails always sorted and minimal last elements [OK]

Hint: tails stores smallest possible ends of subsequences [OK]

Common Mistakes:

• Appending instead of replacing in tails
• Misunderstanding bisect_left index
• Confusing tails with actual subsequence

3. You are given an integer array and need to find how many distinct longest strictly increasing subsequences it contains. Which approach guarantees an optimal solution that efficiently counts all such subsequences without enumerating them explicitly?

easy

A. A greedy algorithm that picks the first increasing subsequence found and counts its length

B. A pure recursive backtracking approach that tries all subsequences to count the longest ones

C. Sorting the array and counting increasing subsequences using combinatorial formulas

D. Dynamic programming that tracks length and count of LIS ending at each index with O(n²) time complexity

Solution

1. Step 1: Understand problem requirements

   The problem requires counting all longest increasing subsequences, not just finding one or their length.

2. Step 2: Evaluate approaches

   Greedy fails because it finds only one LIS, recursion is exponential and inefficient, sorting loses original order, but DP with length and count arrays correctly tracks LIS counts in O(n²).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP with length and count arrays is standard for counting LIS [OK]

Hint: DP with length and count arrays counts LIS correctly [OK]

Common Mistakes:

• Assuming greedy finds all LIS
• Thinking sorting helps count LIS
• Using pure recursion without pruning

4. Consider the following buggy code snippet for counting ways to assign unique caps. Which line contains the subtle bug that causes incorrect counting?

medium

A. Line with 'for mask in range(0, (1 << n)):' iterating masks forward

B. Line with 'dp[0] = 1' initializing base case

C. Line with 'cap_to_persons[c].append(i)' building cap-person mapping

D. Line with modulo operation after addition

Solution

1. Step 1: Identify iteration order over masks

   The code iterates masks forward (0 to 2^n-1), which causes dp states updated in the same iteration to be reused, leading to overcounting.

2. Step 2: Correct iteration order

   Iterating masks backward (from 2^n-1 down to 0) prevents using updated states in the same iteration, ensuring correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Forward iteration over masks is a known subtle bug causing overcounting [OK]

Hint: Iterate masks backward to avoid overcounting [OK]

Common Mistakes:

• Forward iteration over masks
• Missing modulo after addition

5. Suppose the problem is modified so that caps can be assigned to multiple people (i.e., caps are no longer unique). Which of the following algorithmic changes correctly adapts the solution to count the number of ways to assign caps without uniqueness constraints?

hard

A. Remove bitmask tracking and use simple multiplication of counts per person

B. Keep bitmask DP but allow assigning the same cap multiple times by not checking mask bits

C. Use a DP over persons only, multiplying the number of caps each person can wear

D. Use a nested loop over persons and caps without bitmask, summing ways for each person independently

Solution

1. Step 1: Understand the uniqueness constraint removal

   Without uniqueness, caps can be reused freely, so no need to track assigned caps with bitmasks.

2. Step 2: Simplify counting approach

   Counting ways reduces to multiplying the number of caps each person can wear, as assignments are independent.

3. Step 3: Why other options fail

   Bitmask DP is unnecessary and incorrect if caps can be reused; summing independently without multiplication misses combinations.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Removing bitmask and multiplying counts per person matches problem relaxation [OK]

Hint: No uniqueness -> no bitmask needed, multiply counts [OK]

Common Mistakes:

• Trying to keep bitmask DP unnecessarily
• Summing instead of multiplying counts