Is O(0) space?c++ solution


  • 0
    H
    class Solution {
    public:
        int minPathSum(vector<vector<int>>& grid) {
            if (grid.empty()) {
                return 0;
            }
            int m = grid.size(), n = grid[0].size();
            for (int i = 1; i < n; ++i) {
                grid[0][i] = grid[0][i-1] + grid[0][i];
            }
            for (int i = 1; i < m; ++i) {
                grid[i][0] = grid[i-1][0] + grid[i][0];
            }
            for (int i = 1; i < m; ++i) {
                for (int j = 1; j < n; ++j) {
                    grid[i][j] =  min(grid[i-1][j],grid[i][j-1]) + grid[i][j];
                }
            }
            return grid[m-1][n-1];
        }
    };

  • 0
    T

    We usually pick from these: Wikipedia Big O notation: Orders of common functions
    Check this out as well: SO about O(0)


  • 0
    H

    Thank you for your link! It's pretty useful!


  • 0
    T

    I just realized, that this is definitely in normal O(1) space as we have grid, m, n, i, j variables, all taking up space on the stack. The .size() and min(...) method calls also use more stack space.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.