1289. Minimum Falling Path Sum II

T: O(m*n*nlogn), log200 = constant time => O(mn)
S: O(mn)

class Solution {
    public int minFallingPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < n; i++) {
            dp[0][i] = grid[0][i];
        }

        for (int i = 1; i < m; i++) {
            Queue<Integer> pq = new PriorityQueue();
            for (int j = 0; j < n; j++) {
                pq.offer(dp[i-1][j]);
            }

            int smallest = pq.poll();
            int secondSmallest = pq.poll();
            for (int j = 0; j < n; j++) {
                int min = smallest;
                if (dp[i-1][j] == smallest) {
                    min = secondSmallest; 
                    // if there are the number 1, 1 -> smallest and secondSmallest
                    // if we can't use smallest (the same), there is still another is the same small 1
                }
                dp[i][j] = grid[i][j] + min;
            }
        }
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            result = Math.min(result, dp[m-1][i]);
        }
        return result;
    }
}

/**
T: O(m*n*nlogn), log200 = constant time => O(mn)
S: O(mn)

 */

actually no need to check each col in prev row again (if (k != j)

just check smallest and second smallest value are the same or not (really smart!

T: O(m*n*n)
S: O(mn)

class Solution {
    public int minFallingPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < n; i++) {
            dp[0][i] = grid[0][i];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = 0; k < n; k++) {
                    if (k != j) {
                        min = Math.min(min, dp[i-1][k]);
                    }
                }
                dp[i][j] = grid[i][j] + min;
            }
        }
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            result = Math.min(result, dp[m-1][i]);
        }
        return result;
    }
}

/**
T: O(m*n*n)
S: O(mn)

 */

 */