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

rr459595's blog

By rr459595, history, 4 weeks ago, In English,

Link to the question:- https://www.interviewbit.com/problems/rook-movement/

I tried BFS where in each state I store min steps,direction (up,down,left or right). I am getting TLE for large inputs.

Can someone help me ?

Thanks.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Why do you need to store the direction? BFS will never revisit the same cell due to the shortest number of steps property. And I also don't understand how you can get TLE because the input is small. Try posting your code here.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I thought that direction is required.

    Consider the eg:-

    000111

    000000

    where '1' denotes obstacles.

    We can visit (1,2) in 2 steps in 2 ways from (0,0):-

    1) (0,2) and (1,2)

    2) (1,0) and (1,2).

    Now if destination is (1,3), we would prefer 2nd) option over first as using first option would give 3 steps as answer but optimal answer to reach (1,3) should be 2.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      Nope. In the second case, BFS will go from (0, 0) to (1, 0) then straight to (1, 3). In the first case, BFS must make two steps before going to (1, 3). Hence, BFS will still take option 2 first

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

There is one difficulty in this problem though (if you don't use direction) — the number of transitions on each iteration of BFS can be up to O(n) if you do not code the BFS properly. So the time complexity will become O(n^3) in this case. You will need to use a simple trick to resolve this. I leave this as an exercise for you.

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Anyway, your method works as well. Just that I don't understand how you got TLE. Posting some code would certainly help people to determine the cause of the problem.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Ok. There are 2 problems with your code (1 is minor enough that you can ignore anyway).

  1. The serious problem: You are not doing the BFS properly. When you push nodes into the queue, you should check if the previously found distance is more optimal, and update the shortest distance accordingly. However, what you are doing now is to push nodes into the queue indiscriminately. This means that your queue could potentially have a lot of unnecessary nodes, which you will filter out based on distance optimality later. But this wastes computation time. Why waste time filtering unnecessary nodes?

  2. The minor problem: LinkedList in Java is pretty slow. I think using something like ArrayList or Queue can give you better performance. But this is just some micro-optimization and you may choose to ignore it.