Maximum Difference Score in a Grid 🚦 Optimal Dynamic Programming Approach
\n## Intuition\nThe goal is to find the maximum difference between the value of a cell and the minimum value of its adjacent upper or left cell in a given grid.
\n## Intuition\nThe **goal** is to find the maximum difference between the value of a cell and the minimum value of its adjacent upper or left cell in a given grid. \n\nThe **challenge** is to efficiently calculate this maximum difference while updating the grid in place to keep track of the minimum values encountered so far. This can be achieved by iterating through the grid and applying **dynamic programming principles** to store and update intermediate results.\n\n## Approach\n1. **Initialization**:\n   - Initialize `res` with a very small value (`-1000000`) to store the maximum score found during the iteration.\n   - Determine the number of rows (`m`) and columns (`n`) in the grid.\n   - Create a mutable copy of the input grid to allow modifications.\n\n2. **Iterate Through the Grid**:\n   - Use nested loops to traverse each cell in the grid. The outer loop iterates through each row (`i`), and the inner loop iterates through each column (`j`).\n\n3. **Calculate `pre`**:\n   - For each cell, calculate the minimum value (`pre`) between the cell above (`grid[i-1][j]`) if it exists and the cell to the left (`grid[i][j-1]`) if it exists.\n   - If there is no cell above (`i == 0`) or no cell to the left (`j == 0`), use a large value (`1000000`) instead.\n\n4. **Update the Result `res`**:\n   - Update `res` with the maximum value between the current `res` and the difference between the current cell value (`grid[i][j]`) and `pre`.\n\n5. **Update the Current Cell Value**:\n   - If `pre` is less than the current cell value, update the current cell value to `pre`. This ensures that future calculations consider the minimum path values.\n\n6. **Return the Result**:\n   - After iterating through the entire grid, return the maximum score (`res`).\n\n## Complexity\n- **Time complexity**:\n  - The time complexity is  $$O(m \\times n)$$, where $$m$$ is the number of rows and $$n$$ is the number of columns in the grid. This is because each cell in the grid is visited once.\n\n- **Space complexity**:\n  - The space complexity is $$O(1)$$ beyond the input storage. The input grid is modified in place, and only a few additional variables are used.\n\n![Screenshot 2024-05-15 at 02.16.42.png](https://assets.leetcode.com/users/images/85ccb869-112f-446c-b248-a7ffddd61628_1715728888.966588.png)\n\n\n## Code\n```swift []\nclass Solution {\n    func maxScore(_ grid: [[Int]]) -> Int {\n        // Initialize the result with a very small value\n        var res = -1000000\n        // Get the number of rows and columns in the matrix\n        let m = grid.count\n        let n = grid[0].count\n        \n        // Create a mutable copy of the input matrix\n        var grid = grid\n        \n        // Iterate through each cell in the matrix\n        for i in 0..<m {\n            for j in 0..<n {\n                // Determine the minimum value between the cell above (if exists) and the cell to the left (if exists)\n                let pre = min(\n                    i > 0 ? grid[i - 1][j] : 1000000, // If i > 0, take the value from the cell above; otherwise, use a large value\n                    j > 0 ? grid[i][j - 1] : 1000000  // If j > 0, take the value from the cell to the left; otherwise, use a large value\n                )\n                \n                // Update the result with the maximum difference found so far\n                res = max(res, grid[i][j] - pre)\n                \n                // If the previous minimum value is less than the current cell value, update the current cell value\n                if pre < grid[i][j]) {\n                    grid[i][j] = pre\n                }\n            }\n        }\n        \n        // Return the maximum difference found\n        return res\n    }\n}\n
['Array', 'Dynamic Programming', 'Swift']