CODEWITHSUNDEEP
algorithmsortingdata-structuresdynamic-programming
Dilwar Singh
Dilwar Singh

Reputation: 51

Interview Question "An Optimized Solution for the given Problem"

Recently I was going through an interview and interviewer asked me very interesting question.

we are given a integer matrix for "N x M" we can jump to any number which is strictly greater than current number in the same row or column. we need to find what is the maximum number of cells we can visit. we can start from any point within the matrix.

Example :-

 {1, 0, 10}, 
 {3, 9, 7}, 
 {2, 6, 5}

Answer :- 6

Explanation :- In this case we have multiple correct paths one of the path is given below.

0 => 1 => 2 => 3 => 7 => 10

I write my solution for the given problem in Java

Time Complexity :- N * M * (N + M)

Space Complexity :- N * M

enter image description here

static void longestIncreasingPath(int[][] matrix) {
    int n = matrix.length;
    int m = matrix[0].length;

    int[][] dp = new int[n][m];
    for (int i = 0; i < n; i++)
        Arrays.fill(dp[i], -1);

    int answer = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int length = findSolution(i, j, n, m, matrix, dp);
            answer = Math.max(answer, length);
        }
    }

    System.out.println("Longest increasing path length: " + answer);
}

static int findSolution(int i, int j, int n, int m, int[][] matrix, int[][] dp) {
    if (dp[i][j] != -1) return dp[i][j];

    int res = 1;
    int cur = matrix[i][j];

    for (int newI = 0; newI < n; newI++) {
        int newValue = matrix[newI][j];
        if (newValue > cur) {
            int newRes = 1 + findSolution(newI, j, n, m, matrix, dp);
            res = Math.max(res, newRes);
        }
    }

    for (int newJ = 0; newJ < m; newJ++) {
        int newValue = matrix[i][newJ];
        if (newValue > cur) {
            int newRes = 1 + findSolution(i, newJ, n, m, matrix, dp);
            res = Math.max(res, newRes);
        }
    }

    return dp[i][j] = res;
}

and after this interviewer said Solution is Correct and asked me to more optimize it terms of Time-Complexity. That I couldn't able to do.

Can someone help me finding optimized solution for this problem?

When I was searching for optimized solution interviewer gave a hint of "sorting".

If anyone want to play with my code http://tpcg.io/_ERHJNY

Few more test cases

[[0, 0, 0], [0, 0, 0], [0, 0, 0]] Output should be 1 in this case. Explanation: 0

[[0, 0, 0], [0, 0, 0], [0, 0, -1]] Output should be 2 in this case. Explanation: -1 => 0

[[0, 0, 0], [0, 0, 0], [0, 0, 1]] Output should be 2 in this case. Explanation: 0 => 1

Upvotes: 5

Views: 221

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65427

This problem boils down to finding a longest path in a directed acyclic graph. The classical algorithm for that problem is, for each vertex v in topological order, the length of the longest path ending at v is one plus the max over predecessors of v. Then return the overall max.

By making (matrix[i][j], i, j) triples and sorting them, we get a topological order. Then the trick is to pre-aggregate the row and column maxima so that we can perform the inner loop in O(1) time instead of O(m + n).

In Python (assumes for simplicity that the matrix elements are pairwise distinct, but it's not difficult to remove this assumption):

def longest_path(matrix):
    ending_in_row = [0] * len(matrix)
    ending_in_column = [0] * max(map(len, matrix))
    for value, i, j in sorted(
        (value, i, j) for (i, row) in enumerate(matrix) for (j, value) in enumerate(row)
    ):
        length = max(ending_in_row[i], ending_in_column[j]) + 1
        ending_in_row[i] = max(ending_in_row[i], length)
        ending_in_column[j] = max(ending_in_column[j], length)
    return max(ending_in_row)


print(longest_path([[1, 0, 10], [3, 9, 7], [2, 6, 5]]))

Upvotes: 5

Related Questions