Minimum Points To Reach Destination

Problem Statement

Given a m*n grid with each cell consisting of positive, negative, or zero point. We can move across a cell only if we have positive points. Whenever we pass through a cell, points in that cell are added to our overall points, the task is to find minimum initial points to reach cell (m-1, n-1) from (0, 0) by following these certain set of rules :

From a cell (i, j) we can move to (i + 1, j) or (i, j + 1).
We cannot move from (i, j) if your overall points at (i, j) are < = 0.
We have to reach at (n-1, m-1) with minimum positive points i.e., > 0.

Solution

class Solution{
    public:
    int minPoints(int m, int n, vector<vector<int>>& points) {
        // Initialize a 2D vector dp with dimensions m x n, filled with zeros
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        // Set the bottom-right element of dp grid
        // If points[m - 1][n - 1] is greater than 0, set dp[m - 1][n - 1] to 1
        // Otherwise, set dp[m - 1][n - 1] to the absolute value of points[m - 1][n - 1] plus 1
        dp[m - 1][n - 1] = points[m - 1][n - 1] > 0 ? 1 : abs(points[m - 1][n - 1]) + 1;
        
        // Fill the last column of dp grid
        for (int i = m - 2; i >= 0; --i) {
            // Set dp[i][n - 1] to the maximum of 1 and dp[i + 1][n - 1] minus points[i][n - 1]
            dp[i][n - 1] = max(1, dp[i + 1][n - 1] - points[i][n - 1]);
        }
        
        // Fill the last row of dp grid
        for (int j = n - 2; j >= 0; --j) {
            // Set dp[m - 1][j] to the maximum of 1 and dp[m - 1][j + 1] minus points[m - 1][j]
            dp[m - 1][j] = max(1, dp[m - 1][j + 1] - points[m - 1][j]);
        }
        
        // Fill the rest of the dp grid
        for (int i = m - 2; i >= 0; --i) {
            for (int j = n - 2; j >= 0; --j) {
                // Calculate min_points_on_exit as the minimum of dp[i + 1][j] and dp[i][j + 1]
                int min_points_on_exit = min(dp[i + 1][j], dp[i][j + 1]);
                // Set dp[i][j] to the maximum of 1 and min_points_on_exit minus points[i][j]
                dp[i][j] = max(1, min_points_on_exit - points[i][j]);
            }
        }
        
        // Return the top-left element of dp grid
        return dp[0][0];
    }
};

Algorithm Steps:

Initialize a 2D vector dp with dimensions m x n, filled with zeros.
Set the bottom-right element of dp grid based on the value of points[m - 1][n - 1].
Fill the last column of dp grid.
Fill the last row of dp grid.
Fill the rest of the dp grid by iterating over each cell and calculating the minimum points needed to exit from that cell.
Return the minimum points required to reach the top-left cell of the dp grid.

Time Complexity: O(m * n) Space Complexity: O(m * n)

To optimize the space complexity, we can use only a single row instead of a 2D grid. Since we are accessing cells row by row and the calculations for each cell only depend on the previous row's cells, we can reuse the same row. This reduces the space complexity to O(n).

Optimized Code

class Solution {
public:
    // Function to find the minimum points needed to reach the bottom-right cell from the top-left cell
    int minPoints(int m, int n, vector<vector<int>>& points) {
        // Initialize a vector dp of size n, filled with zeros to represent the dynamic programming grid
        vector<int> dp(n, 0);

        // Set the value of the bottom-right element of dp based on the points at that cell
        dp[n - 1] = points[m - 1][n - 1] > 0 ? 1 : abs(points[m - 1][n - 1]) + 1;

        // Loop through each row from second-last to first
        for (int i = m - 2; i >= 0; --i) {
            // Update the value of dp for the last column based on the points and previous dp value
            dp[n - 1] = max(1, dp[n - 1] - points[i][n - 1]);
            
            // Loop through each column from second-last to first
            for (int j = n - 2; j >= 0; --j) {
                // Calculate the minimum points needed to exit from the current cell
                int min_points_on_exit = min(dp[j], dp[j + 1]);
                
                // Update the value of dp for the current cell based on points and minimum points needed to exit
                dp[j] = max(1, min_points_on_exit - points[i][j]);
            }
        }

        // Return the minimum points required to reach the top-left cell of the dp grid
        return dp[0];
    }
};

Time Complexity: O(m * n) Space Complexity: O(n)