LeetCode 2400 - Number of Ways to Reach a Position After Exactly k Steps

This problem asks us to count the number of distinct ways to move from startPos to endPos on an infinite number line using exactly k steps. At each step, we may move either one position to the left (-1) or one position to the right (+1).

leetcodemediummathdynamic-programmingcombinatorics

LeetCode Problem 2400

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming, Combinatorics

Solution

Problem Understanding

This problem asks us to count the number of distinct ways to move from startPos to endPos on an infinite number line using exactly k steps. At each step, we may move either one position to the left (-1) or one position to the right (+1).

The important detail is that order matters. Two movement sequences are considered different if the order of left and right moves differs. For example, moving right, left, right is different from left, right, right, even if both end at the same position.

We are given three integers:

  • startPos, the starting position on the number line
  • endPos, the destination position
  • k, the exact number of steps we must take

The goal is to return the total number of valid movement sequences modulo 10^9 + 7, since the result may become very large.

A useful way to think about this problem is to focus on the net displacement. Suppose:

distance = endPos - startPos

Every right move contributes +1, and every left move contributes -1.

If we take:

  • r right moves
  • l left moves

then:

r + l = k
r - l = distance

Solving these equations gives:

r = (k + distance) / 2
l = (k - distance) / 2

This immediately reveals an important constraint:

  1. We must be able to physically reach the target, meaning abs(distance) <= k.
  2. The parity must match, meaning (k + distance) must be even.

If either condition fails, the answer is 0.

The constraints are relatively small:

1 <= startPos, endPos, k <= 1000

Since k is at most 1000, both dynamic programming and combinatorial methods are feasible. However, brute force enumeration of all possible paths is completely impractical because the number of paths grows exponentially.

Several edge cases can trip up a naive implementation. If the target is farther away than the number of available steps, reaching it is impossible. Similarly, parity mismatches matter. For example, moving from position 2 to 5 in exactly 10 steps is impossible because the parity does not work out. Another edge case occurs when startPos == endPos, where only paths with an even number of steps can return to the same location.

Approaches

Brute Force Approach

A straightforward way to solve the problem is to recursively try every possible sequence of moves. At each step, we can either move left or right, meaning there are two choices per step.

We could define a recursive function:

dfs(position, remainingSteps)

At every call, we branch into:

  • position - 1
  • position + 1

When remainingSteps == 0, we check whether the current position equals endPos.

This approach is correct because it explicitly explores every possible movement sequence and counts only those that finish at the target after exactly k steps.

However, the number of possibilities grows exponentially:

2^k

Since k can be 1000, this is far too slow.

Optimal Approach, Combinatorics

The key insight is that we do not care about the exact positions visited along the way. We only care about how many left and right moves exist.

Suppose we need net displacement:

distance = endPos - startPos

If we make r right moves and l left moves:

r + l = k
r - l = distance

From algebra:

r = (k + distance) / 2

Once we know how many right moves are required, the problem becomes:

In k total positions, how many ways can we choose where the right moves occur?

This is simply a combinations problem:

C(k, r)

We compute the binomial coefficient modulo 10^9 + 7.

Since k <= 1000, we can efficiently compute combinations using dynamic programming based on Pascal's Triangle.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^k) O(k) Explores every possible movement sequence
Optimal O(k²) O(k²) Uses combinatorics with Pascal's Triangle

Algorithm Walkthrough

  1. Compute the displacement needed.

We first calculate:

distance = abs(endPos - startPos)

We use the absolute value because moving left or right is symmetric. 2. Check whether reaching the destination is possible.

There are two conditions that make the answer impossible:

  • distance > k, meaning the target is too far away
  • (k - distance) % 2 != 0, meaning parity does not match

If either condition fails, return 0. 3. Compute the number of required right moves.

Since:

r = (k + distance) / 2

we calculate:

right_moves = (k + distance) // 2
  1. Build Pascal's Triangle.

We create a dynamic programming table where:

dp[n][r] = C(n, r)

using the recurrence:

C(n, r) = C(n - 1, r - 1) + C(n - 1, r)

This works because every combination either includes or excludes the current element. 5. Return the final combination.

The answer becomes:

C(k, right_moves)

modulo 10^9 + 7.

Why it works

The algorithm works because every valid path contains exactly a certain number of right and left moves. Once these counts are fixed, the only remaining question is where the right moves appear among the k steps. Each distinct placement corresponds to a unique path, and every valid path corresponds to exactly one placement. Therefore, counting combinations gives the exact number of valid sequences.

Python Solution

class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        MOD = 10**9 + 7

        distance = abs(endPos - startPos)

        # Impossible to reach
        if distance > k or (k - distance) % 2 != 0:
            return 0

        right_moves = (k + distance) // 2

        # Pascal's Triangle for combinations
        dp = [[0] * (right_moves + 1) for _ in range(k + 1)]

        for i in range(k + 1):
            dp[i][0] = 1

        for i in range(1, k + 1):
            limit = min(i, right_moves)

            for j in range(1, limit + 1):
                if j == i:
                    dp[i][j] = 1
                else:
                    dp[i][j] = (
                        dp[i - 1][j - 1] +
                        dp[i - 1][j]
                    ) % MOD

        return dp[k][right_moves]

The implementation starts by computing the required distance between the start and end positions. Before doing any expensive computation, it checks the impossibility conditions. If the destination is too far away or parity does not match, the function immediately returns 0.

Next, the code computes how many right moves are required. Since every valid path must contain exactly this many right moves, the problem reduces to computing a binomial coefficient.

To calculate combinations efficiently under modulo arithmetic, the implementation builds Pascal's Triangle using dynamic programming. The first column is initialized to 1 because:

C(n, 0) = 1

For every row, the recurrence relation constructs larger combinations from smaller ones. Finally, the answer stored in dp[k][right_moves] is returned.

Go Solution

func numberOfWays(startPos int, endPos int, k int) int {
	const mod = 1_000_000_007

	distance := endPos - startPos
	if distance < 0 {
		distance = -distance
	}

	// Impossible to reach
	if distance > k || (k-distance)%2 != 0 {
		return 0
	}

	rightMoves := (k + distance) / 2

	// Pascal's Triangle
	dp := make([][]int, k+1)

	for i := 0; i <= k; i++ {
		dp[i] = make([]int, rightMoves+1)
		dp[i][0] = 1
	}

	for i := 1; i <= k; i++ {
		limit := i
		if limit > rightMoves {
			limit = rightMoves
		}

		for j := 1; j <= limit; j++ {
			if j == i {
				dp[i][j] = 1
			} else {
				dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod
			}
		}
	}

	return dp[k][rightMoves]
}

The Go implementation follows exactly the same logic as the Python version. One difference is that Go does not have a built in abs() function for integers, so we manually convert negative values to positive.

The dynamic programming table is implemented using a slice of slices. Since modulo arithmetic is required, every update applies % mod immediately to prevent overflow and keep values within range.

Worked Examples

Example 1

startPos = 1
endPos = 2
k = 3

First compute distance:

distance = |2 - 1| = 1

Check feasibility:

distance <= k
1 <= 3, valid

(k - distance) % 2
(3 - 1) % 2 = 0, valid

Compute right moves:

right_moves = (3 + 1) / 2 = 2

Now compute:

C(3, 2)

Pascal's Triangle progression:

i Combination Row
0 [1]
1 [1,1]
2 [1,2,1]
3 [1,3,3,1]

Result:

C(3,2) = 3

The valid paths are:

R R L
R L R
L R R

Which correspond to:

1 -> 2 -> 3 -> 2
1 -> 2 -> 1 -> 2
1 -> 0 -> 1 -> 2

Example 2

startPos = 2
endPos = 5
k = 10

Compute distance:

distance = |5 - 2| = 3

Check parity:

(10 - 3) % 2 = 1

Since parity is odd, it is impossible to reach exactly position 5 after 10 steps.

Result:

0

Complexity Analysis

Measure Complexity Explanation
Time O(k²) Building Pascal's Triangle up to k rows
Space O(k²) Dynamic programming table stores combinations

The dominant work comes from constructing the DP table. Since we iterate through roughly k × k states and k <= 1000, this runs comfortably within limits. The memory cost is also quadratic because the Pascal Triangle table stores intermediate combination values.

Test Cases

solution = Solution()

assert solution.numberOfWays(1, 2, 3) == 3  # Provided example 1
assert solution.numberOfWays(2, 5, 10) == 0  # Provided example 2

assert solution.numberOfWays(1, 1, 2) == 2  # Return to same position
assert solution.numberOfWays(1, 1, 3) == 0  # Odd parity prevents return

assert solution.numberOfWays(1, 4, 3) == 1  # Exact distance match
assert solution.numberOfWays(1, 5, 3) == 0  # Target too far

assert solution.numberOfWays(3, 1, 2) == 1  # Moving left
assert solution.numberOfWays(3, 2, 3) == 3  # Multiple valid paths

assert solution.numberOfWays(1000, 1000, 1000) > 0  # Large boundary
assert solution.numberOfWays(1, 1000, 1000) == 1  # Always move right

assert solution.numberOfWays(5, 7, 4) == 4  # Combination count check
Test Why
(1,2,3) Verifies provided example
(2,5,10) Verifies impossible parity
(1,1,2) Tests returning to same position
(1,1,3) Tests odd parity failure
(1,4,3) Tests exact distance case
(1,5,3) Tests unreachable target
(3,1,2) Tests leftward movement
(3,2,3) Tests multiple path counting
(1000,1000,1000) Large input boundary
(1,1000,1000) Tests single unique path
(5,7,4) Verifies combinatorial counting

Edge Cases

One important edge case occurs when the destination is farther away than the number of available steps. For example:

startPos = 1
endPos = 10
k = 3

Even if every move goes in the correct direction, reaching the destination is impossible. A naive implementation might still attempt dynamic programming unnecessarily. Our implementation handles this immediately with:

distance > k

and returns 0.

Another subtle edge case involves parity mismatch. Suppose:

startPos = 2
endPos = 5
k = 10

The required displacement is odd (3), but the number of total moves is even (10). Since every unnecessary move must come in canceling left-right pairs, the parity must match. The implementation correctly detects this using:

(k - distance) % 2 != 0

and returns 0.

A third important case happens when startPos == endPos. To return to the same position, every right move must eventually be canceled by a left move. Therefore, only even values of k are valid. For example:

startPos = 5
endPos = 5
k = 4

works, but:

startPos = 5
endPos = 5
k = 3

does not. The parity check naturally handles this scenario without needing any special logic.