We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Stay in the Same Place After Some Steps

Number: 1398

Difficulty: Hard

Paid? No

Companies: Amazon, Google

Problem Description

You are given a pointer that starts at index 0 in an array with a specified length (arrLen). In each step, the pointer can move one step to the left, one step to the right, or stay in the same position. However, it must never move outside the boundaries of the array. The goal is to determine the number of ways to have the pointer return to index 0 after exactly a given number of steps. Because the answer can be very large, it should be returned modulo 10^9 + 7.

Key Insights

  • Only positions within the range [0, min(arrLen - 1, steps)] can ever be reached in a valid sequence.
  • Use dynamic programming where dp[i][j] denotes the number of ways to reach index j after i steps.
  • The state transition is based on three possibilities: staying in the same place, moving left (if possible), and moving right (if possible).
  • The recurrence relation is:
    dp[i][j] = dp[i-1][j] + (if j-1 >= 0 then dp[i-1][j-1]) + (if j+1 is within bounds then dp[i-1][j+1])
  • The solution can be optimized to use a single 1D DP array by iterating over the number of steps and updating the position counts.
  • Always perform modulo arithmetic at each step to keep numbers within the integer limits.

Space and Time Complexity

Time Complexity: O(steps * min(steps, arrLen))
Space Complexity: O(min(steps, arrLen))

Solution

We can solve the problem using dynamic programming. The idea is to simulate each step using a one-dimensional dp array, where the index of the array represents the current position of the pointer and the value at that index represents the number of ways to get to that position with the current number of steps taken. The maximum effective range for our pointer is min(arrLen, steps + 1), because even if the array is larger, the pointer cannot move more than steps positions away from the starting point. At every step, we update the dp array using the information from the previous step considering three possible moves (stay, left, right). Finally, the answer is the number of ways to get back to index 0 after all given steps, taken modulo 10^9 + 7.

Code Solutions

MOD = 10**9 + 7

def numWays(steps: int, arrLen: int) -> int:
    # The maximum position we need to consider is min(arrLen-1, steps)
    maxPos = min(arrLen - 1, steps)
    # Initialize dp array for step 0 with 1 way to be at index 0
    dp = [0] * (maxPos + 1)
    dp[0] = 1
    # Iterate for each step
    for step in range(1, steps + 1):
        # Initialize a new array for the current step
        new_dp = [0] * (maxPos + 1)
        # For each position up to maxPos
        for pos in range(0, maxPos + 1):
            # Stay at the same position
            new_dp[pos] = (new_dp[pos] + dp[pos]) % MOD
            # Move left if possible
            if pos - 1 >= 0:
                new_dp[pos - 1] = (new_dp[pos - 1] + dp[pos]) % MOD
            # Move right if within bounds (pos+1 <= maxPos)
            if pos + 1 <= maxPos:
                new_dp[pos + 1] = (new_dp[pos + 1] + dp[pos]) % MOD
        dp = new_dp
    # Return the number of ways to be back at index 0
    return dp[0]

# Example usage:
# print(numWays(3, 2))  # Output: 4
← Back to All Questions