Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- https://www.geeksforgeeks.org/check-if-the-end-of-the-array-can-be-reached-from-a-given-position/
- This whole code is GFG article code so don't write this code anywhere,Modify the code.
- Logic: BFS
- 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.
- T.C : O(N) as we move all i once.
- S.C : O(N) for queue for BFS
- */
- def solve(arr, n, start):
- # Simple list used as queue
- q = []
- # Visited array
- visited = [False] * n
- # Push starting index
- q.append(start)
- reached = False
- while len(q) > 0:
- temp = q[0]
- q = q[1:] # pop front
- # Skip if already visited
- if visited[temp]:
- continue
- visited[temp] = True
- # Check if reached end
- if temp == n - 1:
- reached = True
- break
- # Forward move
- if temp + arr[temp] < n:
- q.append(temp + arr[temp])
- # Backward move
- if temp - arr[temp] >= 0:
- q.append(temp - arr[temp])
- if reached:
- print("Yes")
- else:
- print("No")
Advertisement
Add Comment
Please, Sign In to add comment