5 Best Ways to Check if You Can Reach the End of a List Starting from Index K in Python

Rate this post

πŸ’‘ Problem Formulation: You’re given a list of non-negative integers. Each integer represents your maximum jump length at that position. Your task is to determine if you can reach the end of the list starting from index k. For example, given the list [2, 3, 1, 1, 4] and the starting index k = 2, the result should be True as you can jump to the end of the list from this position.

Method 1: Recursive Check

The recursive method checks from the current index if any position reachable from there can lead to the end of the list. This method applies the ideology of backtracking through recursion until a path to the end of the list is found or all possibilities are exhausted.

Here’s an example:

def can_reach_end(nums, k):
    if k >= len(nums) - 1:
        return True
    
    furthest_jump = min(k + nums[k], len(nums) - 1)
    for next_position in range(k + 1, furthest_jump + 1):
        if can_reach_end(nums, next_position):
            return True
    
    return False

# Test the function
nums = [2, 3, 1, 1, 4]
k = 2
print(can_reach_end(nums, k))

True

This function, can_reach_end(), starts at index k and recursively attempts to jump to each index that is within reach. If any of these subsequent calls return true, indicating that the end can be reached, the function returns True. Otherwise, it exhausts all options and returns False.

Method 2: Dynamic Programming

In this method, dynamic programming is applied where the past results are stored in a table to avoid redundant calculations. This reduces the time-complexity by trading off space.

Here’s an example:

def can_reach_end_dp(nums, k):
    dp = [False] * len(nums)
    dp[k] = True

    for i in range(k, -1, -1):
        furthest_jump = min(i + nums[i], len(nums) - 1)
        for j in range(i, furthest_jump + 1):
            if dp[j]:
                dp[i] = True
                break
    return dp[0]

# Test the function
nums = [2, 3, 1, 1, 4]
k = 2
print(can_reach_end_dp(nums, k))

True

The function can_reach_end_dp() initializes a dp table with values False, except for the starting index k which is set to True. Then, it iterates backwards and uses the values in the table to determine if earlier positions can reach the end. If the end can be reached from the starting index, dp[0] would be True.

Method 3: Greedy Approach

This method uses a greedy approach by keeping track of the furthest position that can be reached at each step. If, at any point, the current position is greater than the furthest reached, it means the end cannot be reached.

Here’s an example:

def can_reach_end_greedy(nums, k):
    furthest_reach = k
    for i in range(k, len(nums)):
        if i > furthest_reach:
            return False
        furthest_reach = max(furthest_reach, i + nums[i])
    return furthest_reach >= len(nums) - 1

# Test the function
nums = [2, 3, 1, 1, 4]
k = 2
print(can_reach_end_greedy(nums, k))

True

The function can_reach_end_greedy() initializes furthest_reach to the starting index k and incrementally updates it if a greater reach is found. It returns False immediately if the loop index surpasses furthest_reach, otherwise, it will return True if the accumulated furthest reach is greater than or equal to the last index.

Method 4: Iterative Depth-First Search

An iterative depth-first search (DFS) can also be used to solve this problem by traversing all possible paths from the starting position iteratively using a stack data structure.

Here’s an example:

def can_reach_end_iterative_dfs(nums, k):
    stack = [k]
    visited = set()
    while stack:
        current = stack.pop()
        if current >= len(nums) - 1:
            return True
        visited.add(current)
        for next_position in range(current + 1, min(current + nums[current] + 1, len(nums))):
            if next_position not in visited:
                stack.append(next_position)
    return False

# Test the function
nums = [2, 3, 1, 1, 4]
k = 2
print(can_reach_end_iterative_dfs(nums, k))

True

The function can_reach_end_iterative_dfs() uses a stack to keep track of positions to visit and a set to remember visited positions to avoid loops. It tries to reach the end of the list iteratively, returning True if successful. If the stack becomes empty, it implies all positions are exhausted without reaching the end, hence returning False.

Bonus One-Liner Method 5: Pythonic Conditional Expression

A pythonic approach could be to use list comprehension with any() function that checks if the end can be reached in a single line by looking at the reachability from every possible position starting from the index k.

Here’s an example:

can_reach_end_one_liner = lambda nums, k: any(nums[i] >= len(nums) - i - 1 for i in range(k, len(nums)))

# Test the function
nums = [2, 3, 1, 1, 4]
k = 2
print(can_reach_end_one_liner(nums, k))

True

This one-liner uses a lambda function and applies any() to a generator expression that checks for each i starting from k if the jump from i can reach the end by comparing the jump length with the distance to the end.

Summary/Discussion

  • Method 1: Recursive Check. This is conceptually simple but can lead to exponential time complexity without memoization. Not the most efficient for large inputs.
  • Method 2: Dynamic Programming. More efficient than the recursive method as it avoids redundant calculations. However, it comes with extra space costs for the memoization table.
  • Method 3: Greedy Approach. This is the most efficient in terms of both time and space complexities, as it only requires O(n) time and O(1) space, but it might not be as intuitive as other methods.
  • Method 4: Iterative Depth-First Search. Useful if stack size is a limitation for recursion. However, it generally holds a lower performance due to the overhead of maintaining a stack and a set.
  • Bonus One-Liner Method 5: Pythonic Conditional Expression. Elegant and concise but might lack clarity for someone not familiar with Python’s functional style.