What's the time complexity when using DFS?


  • 1
    C

    When using DFS to solve, it take O(m * n) to iterate through the matrix, but in the recursion dfs function, it also need to iterate over the matrix , so does it mean that the overall time complexity turn out to be O(m * n) * O(m * n)?


  • 0
    Y

    I believe the time complexity is still O(m * n). The DFS does not traverse the entire matrix every every time it is called - once the DFS is called and it somehow explores half of the matrix, the portions it explore is marked with a value that is not 1, and will not be explored by future DFS calls.


Log in to reply
 

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