imashutosh51

Check if the end of the Array can be reached from a given position

Nov 10th, 2022 (edited)
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.45 KB | None | 0 0
  1. /*
  2. https://www.geeksforgeeks.org/check-if-the-end-of-the-array-can-be-reached-from-a-given-position/
  3. This whole code is GFG article code so don't write this code anywhere,Modify the code.
  4.  
  5. Logic: BFS
  6. We are starting from S and there is two situation only either go s+arr[i] or s-arr[i].so now,we are having two new starting points if any of the above two reaches to end,then answer will be yes.Suppose we again reach at s+arr[i] after some steps then the results will be same.So keep a visited array where we don't need to come to the same point because nothing is going to change,you will follow the same path again you went earlier.
  7. T.C : O(N) as we move all i once.
  8. S.C : O(N) for queue for BFS
  9. */
  10. def solve(arr, n, start):
  11.     # Simple list used as queue
  12.     q = []
  13.  
  14.     # Visited array
  15.     visited = [False] * n
  16.  
  17.     # Push starting index
  18.     q.append(start)
  19.  
  20.     reached = False
  21.  
  22.     while len(q) > 0:
  23.         temp = q[0]
  24.         q = q[1:]   # pop front
  25.  
  26.         # Skip if already visited
  27.         if visited[temp]:
  28.             continue
  29.  
  30.         visited[temp] = True
  31.  
  32.         # Check if reached end
  33.         if temp == n - 1:
  34.             reached = True
  35.             break
  36.  
  37.         # Forward move
  38.         if temp + arr[temp] < n:
  39.             q.append(temp + arr[temp])
  40.  
  41.         # Backward move
  42.         if temp - arr[temp] >= 0:
  43.             q.append(temp - arr[temp])
  44.  
  45.     if reached:
  46.         print("Yes")
  47.     else:
  48.         print("No")
  49.  
  50.  
Advertisement
Add Comment
Please, Sign In to add comment