Program to check we can reach end of list by starting from k in Python
-
07-10-2020 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Program to check we can reach end of list by starting from k in Python
Suppose we have a list of numbers called nums and another number k. If we start at index k and at any index i, we can go either left or right by exactly nums[i] number of steps. We have to check whether we can reach the end of the list or not.
So, if the input is like nums = [0, 0, 2, 1, 3, 3, 1, 1] k = 2, then the output will be True, as if we start at index 2, then jump to index 4 and then jump to the last index 7.
To solve this, we will follow these steps−
n:= size of nums
visited := a list of size n and fill with 0
tovisit := a list of size 1, and insert k into it
while size of tovisit < 0, do
i:= last element from tovisit and delete it from tovisit
if i is same as n-1, then
return True
if visited[i] is not same as 1, then
visited[i]:= 1
up:= i + nums[i]
down:= i - nums[i]
if up < n, then
insert up at the end of tovisit
if down >= 0, then
insert down at the end of tovisit
return False
Let us see the following implementation to get better understanding−
Example
class Solution: def solve(self, nums, k): n=len(nums) visited = [0]*n tovisit = [k] while len(tovisit)>0: i=tovisit.pop() if i==n-1: return True if visited[i]!=1: visited[i]=1 up=i+nums[i] dn=i-nums[i] if up=0: tovisit.append(dn) return False ob = Solution() nums = [0, 0, 2, 1, 3, 3, 1, 1] k = 2 print(ob.solve(nums, k))
Input
[0, 0, 2, 1, 3, 3, 1, 1], 2
Output
True
