Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

What is the time complexity for this modified BFS code?

Revision en1, by _Satoru_, 2022-10-06 23:22:10

I am trying to figure out the time complexity of this code https://leetcode.com/submissions/detail/816740998/ for this problem on leetcode https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/ . Since after each update we are pushing the node to the queue again I am not able to convince myself that the time complexity is O(nm). How can we prove that each cell will be updated constant times?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English _Satoru_ 2022-10-07 11:46:44 38
en2 English _Satoru_ 2022-10-07 07:21:45 2311
en1 English _Satoru_ 2022-10-06 23:22:10 466 Initial revision (published)