Scale Engineer

Number of Ways to Reach a Position After Exactly k Steps

Med
#2184Time: O(k * D) or O(k^2). Each state `(stepsLeft, currentPos)` is computed only once. The number of steps ranges from 0 to `k`. The range of positions `D` we can reach is `startPos +/- k`, which is `O(k)`. Therefore, the total time complexity is `O(k * k) = O(k^2)`.Space: O(k * D) or O(k^2). The space is dominated by the memoization table, which stores results for each `(stepsLeft, currentPos)` state. The number of steps is `k`, and the range of positions `D` is `O(k)`. An additional `O(k)` is used for the recursion stack.
Patterns
MathDynamic ProgrammingCombinatorics

Prompt

You are given two positive integers startPos and endPos. Initially, you are standing at position startPos on an infinite number line. With one step, you can move either one position to the left, or one position to the right.

Given a positive integer k, return the number of different ways to reach the position endPos starting from startPos, such that you perform exactly k steps. Since the answer may be very large, return it modulo 109 + 7.

Two ways are considered different if the order of the steps made is not exactly the same.

Note that the number line includes negative integers.

 

Example 1:

Input: startPos = 1, endPos = 2, k = 3
Output: 3
Explanation: We can reach position 2 from 1 in exactly 3 steps in three ways:
- 1 -> 2 -> 3 -> 2.
- 1 -> 2 -> 1 -> 2.
- 1 -> 0 -> 1 -> 2.
It can be proven that no other way is possible, so we return 3.

Example 2:

Input: startPos = 2, endPos = 5, k = 10
Output: 0
Explanation: It is impossible to reach position 5 from position 2 in exactly 10 steps.

 

Constraints:

  • 1 <= startPos, endPos, k <= 1000

Approaches

3 approaches with complexity analysis and trade-offs.

A recursive approach can be formulated by considering the choices at each step. From any position, we can move left or right. This leads to a recursive function solve(currentPos, stepsLeft). However, this simple recursion involves many redundant calculations for the same state (currentPos, stepsLeft). We can optimize this using memoization, a technique where we store the results of expensive function calls and return the cached result when the same inputs occur again. This is a top-down dynamic programming approach.

Algorithm

  • Create a memoization table memo (e.g., a 2D array or a map of maps) initialized with a value indicating 'not computed'.
  • Define a recursive function solve(currentPos, stepsLeft):
    • Pruning: If abs(endPos - currentPos) > stepsLeft, it's impossible to reach the target, so return 0.
    • Base Case: If stepsLeft == 0, return 1 if currentPos == endPos, otherwise return 0.
    • Check if memo[stepsLeft][currentPos + offset] has been computed. If yes, return the stored value.
    • Recursive Step: Calculate ways = solve(currentPos - 1, stepsLeft - 1) + solve(currentPos + 1, stepsLeft - 1).
    • Store ways % MOD in the memoization table and return it.
  • The initial call is solve(startPos, k).

Walkthrough

We define a function solve(currentPos, stepsLeft) that computes the number of ways to reach endPos from currentPos in stepsLeft moves.

  • Base Cases:
    • If stepsLeft is 0, we have found a path if and only if currentPos == endPos. So we return 1, otherwise 0.
    • A crucial optimization (pruning): If the remaining distance abs(endPos - currentPos) is greater than stepsLeft, it's impossible to reach the target. We can return 0 immediately.
  • Recursive Step: The number of ways to reach the target from (currentPos, stepsLeft) is the sum of ways from the two possible next states: (currentPos - 1, stepsLeft - 1) and (currentPos + 1, stepsLeft - 1).
  • Memoization: We use a 2D array, memo[stepsLeft][currentPos + offset], to store the results. The offset is used to map potentially negative positions to non-negative array indices. Before computing, we check if the result for the current state is already in our memoization table. If so, we return it. Otherwise, we compute it, store it, and then return it.

The initial call is solve(startPos, k).

class Solution {    private int MOD = 1_000_000_007;    private Integer[][] memo;    private int offset = 1000; // Offset to handle negative positions     public int numberOfWays(int startPos, int endPos, int k) {        // With offset, max index is startPos + k + offset <= 1000 + 1000 + 1000 = 3000        memo = new Integer[k + 1][3002];         return solve(startPos, endPos, k);    }     private int solve(int currentPos, int endPos, int stepsLeft) {        if (Math.abs(endPos - currentPos) > stepsLeft) {            return 0;        }        if (stepsLeft == 0) {            return currentPos == endPos ? 1 : 0;        }         if (memo[stepsLeft][currentPos + offset] != null) {            return memo[stepsLeft][currentPos + offset];        }         long ways = (long)solve(currentPos - 1, endPos, stepsLeft - 1) +                     solve(currentPos + 1, endPos, stepsLeft - 1);         return memo[stepsLeft][currentPos + offset] = (int)(ways % MOD);    }}

Complexity

Time

O(k * D) or O(k^2). Each state `(stepsLeft, currentPos)` is computed only once. The number of steps ranges from 0 to `k`. The range of positions `D` we can reach is `startPos +/- k`, which is `O(k)`. Therefore, the total time complexity is `O(k * k) = O(k^2)`.

Space

O(k * D) or O(k^2). The space is dominated by the memoization table, which stores results for each `(stepsLeft, currentPos)` state. The number of steps is `k`, and the range of positions `D` is `O(k)`. An additional `O(k)` is used for the recursion stack.

Trade-offs

Pros

  • Conceptually similar to the brute-force recursion, making it relatively easy to understand and implement.

  • Avoids recomputing results for the same subproblems, drastically improving efficiency over simple recursion.

Cons

  • Can lead to a StackOverflowError for very large k due to deep recursion, although k <= 1000 is generally safe.

  • The space complexity of O(k^2) might be large for bigger constraints.

Solutions

class Solution {private  Integer[][] f;private  final int mod = (int)1 e9 + 7;public  int numberOfWays(int startPos, int endPos, int k) {    f = new Integer[k + 1][k + 1];    return dfs(Math.abs(startPos - endPos), k);  }private  int dfs(int i, int j) {    if (i > j || j < 0) {      return 0;    }    if (j == 0) {      return i == 0 ? 1 : 0;    }    if (f[i][j] != null) {      return f[i][j];    }    int ans = dfs(i + 1, j - 1) + dfs(Math.abs(i - 1), j - 1);    ans %= mod;    return f[i][j] = ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem