Minimum Path Sum


  • 0

    Click here to see the full article post


  • 0
    S

    Dijkstra might be overkill here, but it also works.


  • 0
    A

    overwriting the inputs, how is that O(1) space? I was asked in some interviews specifically that inputs are read only! please correct me if my understanding is not right, thanks.


  • 0
    D

    @adarsh4321.dsp it's O(1) space because we don't introduce any extra memory ourselves in the function. We're operating on a "constant" size multidimensional array in the scope of our function. If inputs are read only, then the only option is to make our own array and then space complexity grows to m*n or n depending on how you implement


Log in to reply
 

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