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 <= 1000Problem Overview: You start at startPos on a number line and can move either left or right by 1 step. After exactly k moves, you must land on endPos. The task is to count how many different sequences of moves reach the target. The answer can be large, so return it modulo 1e9 + 7.
Approach 1: Combinatorics and Parity Check (Time: O(k), Space: O(1))
Each step is either +1 (right) or -1 (left). Let d = |endPos - startPos|. To reach the target in exactly k steps, the difference between right and left moves must equal d. If k < d or (k - d) is odd, reaching the target is impossible because extra moves must cancel in pairs. Otherwise, compute the number of ways to choose the right moves using combinations: C(k, (k + d) / 2). The problem reduces to a binomial coefficient calculation under modulo arithmetic. This approach relies on basic math reasoning and combinatorics and avoids exploring all paths explicitly.
Approach 2: Dynamic Programming (Time: O(k²), Space: O(k²))
Model the process as state transitions. Let dp[step][pos] represent the number of ways to reach a position after a given number of moves. From position x, the next step can go to x - 1 or x + 1. Start with dp[0][startPos] = 1 and iterate for k steps, updating counts for adjacent positions. Because positions can become negative or large, shift indices by an offset or track relative distance from startPos. After filling the table, return dp[k][endPos]. This approach directly simulates all reachable states and demonstrates the classic transition pattern used in dynamic programming.
Recommended for interviews: The combinatorics solution is what most interviewers expect once you notice the parity constraint and the relationship between left/right moves. It reduces the problem to a single binomial coefficient and runs in linear time for factorial or iterative combination computation. The dynamic programming approach is easier to derive during the interview and shows solid state‑transition thinking, but it is less efficient. Showing the DP first and then optimizing to the combinatorics formula demonstrates strong problem‑solving progression.
This approach uses combinatorics to determine the number of ways to reach endPos from startPos in exactly k steps by considering the number of right (R) and left (L) moves required.
To reach from startPos to endPos, you need to have a net movement of rightSteps - leftSteps = endPos - startPos. Furthermore, since rightSteps + leftSteps = k, solving these equations gives the number of right and left steps needed.
The key observation is to check if (k - abs(endPos - startPos)) is even; otherwise it is impossible to reach endPos in exactly k steps. If it is possible, we compute the number of combinations for choosing positions of 'R' in the sequence of k steps using nCr formula, i.e., C(k, rightSteps).
The function calculates whether it is possible to reach endPos by checking if the distance and steps difference meet the parity requirement.
If possible, it computes the binomial coefficient C(k, n) using a loop and Fermat's little theorem for modular inverse, returning the result modulo 10^9 + 7.
Time Complexity: O(k), where k is the number of steps.
Space Complexity: O(1), as only a fixed number of variables are used.
This approach utilizes dynamic programming to solve the problem. We define dp[i][j] as the number of ways to reach position i in j steps. The transition depends on moves to the left or right: dp[i][j] = dp[i-1][j-1] + dp[i+1][j-1].
Start from dp[startPos][0] = 1 and calculate until dp[endPos][k]. The results are all computed modulo 10^9 + 7.
The solution initializes the DP table with the starting position incremented by 1000 (to handle negative indices).
For each step, it calculates possible ways to reach each position by considering movement from the neighboring positions.
The final answer is the number of ways to reach the endPos, returned modulo 10^9 + 7.
Time Complexity: O(k * range), where range is the possible positions due to step limits.
Space Complexity: O(range), determined by the size of the DP table.
We design a function dfs(i, j), which represents the number of ways to reach the target position when the current position is i distance from the target position and there are j steps left. The answer is dfs(abs(startPos - endPos), k).
The calculation method of the function dfs(i, j) is as follows:
i \gt j or j \lt 0, it means that the current distance from the target position is greater than the remaining steps, or the remaining steps are negative. In this case, it is impossible to reach the target position, so return 0;j = 0, it means that there are no steps left. At this time, only when the current distance from the target position is 0 can the target position be reached, otherwise it is impossible to reach the target position. Return 1 or 0;i, and there are j steps left. There are two ways to reach the target position:i + 1, and there are j - 1 steps left. The number of methods is dfs(i + 1, j - 1);abs(i - 1), and there are j - 1 steps left. The number of methods is dfs(abs(i - 1), j - 1);10^9 + 7.To avoid repeated calculations, we use memorization search, that is, we use a two-dimensional array f to record the result of the function dfs(i, j). When the function dfs(i, j) is called, if f[i][j] is not -1, return f[i][j] directly, otherwise calculate the value of f[i][j], and return f[i][j].
The time complexity is O(k^2), and the space complexity is O(k^2). Here, k is the number of steps given in the problem.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Combinatorics and Parity Check | Time Complexity: O(k), where k is the number of steps. |
| Dynamic Programming | Time Complexity: O(k * range), where range is the possible positions due to step limits. |
| Memorization Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Combinatorics + Parity Check | O(k) | O(1) | Best for interviews and production; converts the problem into a binomial coefficient calculation. |
| Dynamic Programming | O(k²) | O(k²) | Useful when deriving the solution step‑by‑step or when practicing DP state transitions. |
2400. Number of Ways to Reach a Position After Exactly k Steps | Leetcode Weekly 309| LeetCode 2400 • Bro Coders • 3,841 views views
Watch 9 more video solutions →Practice Number of Ways to Reach a Position After Exactly k Steps with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor