Oracle SDE 2 Interview Question: Longest Increasing Path

In this blog we'll be discussing a popular algorithmic problem that was asked for SDE 2 role at Oracle.

The problem is called Longest Increasing Path in a Matrix.

It tests your skills in algorithms, dynamic programming, and depth-first search (DFS) or breadth-first search (BFS) techniques.

Let's dive in.

Problem Statement

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]

Output: 4

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

Example 2:

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]

Output: 4

Explanation:The longest increasing path is[3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3:

Input: matrix = [[1]]

Output: 1

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 231 - 1

Solution

Approach:

1. Use depth-first search (DFS) to explore each cell in the matrix.
2. From each cell, try to move in all four possible directions (left, right, up, down).
3. Use memoization to store the length of the longest increasing path starting from each cell to avoid recomputation.
4. Ensure that the move is within the matrix boundaries and to a cell with a higher value.
5. The base case for the DFS will be when there is no adjacent cell with a higher value.
6. The length of the longest increasing path is the maximum value obtained from the DFS exploration starting from each cell.

Constraints:

• We cannot move diagonally.
• We cannot move outside the matrix boundaries.
• We must move to a strictly higher value cell to continue the path.

Let's implement the solution:

def longest_increasing_path(matrix):
    if not matrix or not matrix[0]:
        return 0

    def dfs(i, j):
        if memo[i][j]:
            return memo[i][j]
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        longest = 1
        for d in directions:
            ni, nj = i + d[0], j + d[1]
            if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] > matrix[i][j]:
                longest = max(longest, 1 + dfs(ni, nj))
        memo[i][j] = longest
        return longest

    m, n = len(matrix), len(matrix[0])
    memo = [[0] * n for _ in range(m)]
    return max(dfs(i, j) for i in range(m) for j in range(n))

# Example usage:
matrix1 = [[9,9,4],[6,6,8],[2,1,1]]
print(longest_increasing_path(matrix1))  # Output: 4

matrix2 = [[3,4,5],[3,2,6],[2,2,1]]
print(longest_increasing_path(matrix2))  # Output: 4

matrix3 = [[1]]
print(longest_increasing_path(matrix3))  # Output: 1

This function longest_increasing_path will return the length of the longest increasing path in the given matrix.

The dfs function is a helper function that uses depth-first search and memoization to find the longest path starting from a particular cell.

*****

If you found this problem interesting and want to practice more such algorithmic questions, particularly for roles like SDE 2 at companies like Oracle, feel free to connect with me for a 1:1 free call.

I'd be happy to discuss more problem-solving strategies, provide guidance, and share additional resources to help you prepare effectively for coding interviews. ✅

Mastering these types of problems can greatly boost your confidence and improve your chances of success in the interview process.