The Maze II



@sean46 If by node, you mean the nodes of the search space indicated by the tree in the first figure, then YES, each node(which is distinct from the other nodes depending on the paths through which it is reached) is visited only once. But, if by node, you mean to say some position (i,j) in the maze, then NO. This is because, it could be possible that we would've visited (i,j) earlier through a worse path than the one considered currently.

In approach #4, we use a PriorityQueue to find the minimum distance between the visited cells and the starting point in O(1) time. But the PriorityQueue is decalred as max heap: PriorityQueue < int[] > queue = new PriorityQueue < > ((a, b)  > b[2]  a[2]); The comparator lambda expression indicates this is max heap. Is this a bug or am I missing something here?

@itnovice The priority queue is a maxheap only as mentioned in the explanation. Further, it is used to find the unvisited cell(NOT the visited cell) which is at a minimum distance from the starting node. Also, finding the minimum element takes O(log(n)) time, since it is a heap(NOT O(1) time), which has also been mentioned in the time complexity.

@vinod23 You're correct. The priority queue is used to find the minimum distance between unvisited cells in the queue and starting node. Considering heapify the worst case running time is O(long(n)). Thanks for pointing this out. However, I still don't understand why we should use max heap here. You mentioned this in the post: "The criteria used for heapifying is that the node which is unvisited and at the smallest distance from the startstart node, is always present on the top of the heap. Thus, the node to be chosen as the current node, is always present at the front of the queue." By definition, a max heap will place the cell with largest distance to the front of the queue. That way, the cell with the largest distance in the current level will be popped off the queue first. Isn't this contradicting with your statement above? Thanks!

@vinod23 I observed the same thing. Whether using min heap or using max heap I always get the same result. As far as I can see, no matter in which sequence we traverse the search space the distance matrix will always be updated with a smaller value if one exists. So using min heap or max heap makes no difference to me. Not sure if I have sufficient test case coverage though.

I think I know the answer why min/max heap both work. The reason is that when you find a smaller distance, you push this point with this distance into the queue. And the same point was probably pushed into the queue multiple times with different distance (including the minimum distance). For the same point, its copy with different distance will all be processed (including the min distance) in descending or increasing order, depending on max/min heap. So the code is correct, but inefficient. What you can do is to pop the queue, and check whether this point is visited first. And in this case, only minheap will work correctly.

@zestypanda Thanks for your explanation. You, are right. I think one solution is to update the distance of point in priorityqueue rather than inserting new distance of same point, but I found it difficult in implementing. Another solution is to process the point of queue only when its distance is smaller than distance in
distance
array. I have updated the code according to second solution. Please let me know your thoughts. Also, I have removed unnecessary arguments in all the solutions. Thanks.

@Seddas This condition will get hit. If you remove this condition still solution will get AC. This condition optimises the code little bit. The cell which is processed will get hit by this condition as there is no need to process it again.

Please discard the last reply (leetcode doesn't allow edit comment : (. Shouldn't you consider the time wasted on visiting the same node multiple times in Approach 2? Also, I think your time complexity for approach 4 is wrong, you still have to find neighbors so the max(m, n) should appear as well, right?