Given two integers n and k, return an array of all the integers of length n where the difference between every two consecutive digits is k. You may return the answer in any order.
Note that the integers should not have leading zeros. Integers as 02 and 043 are not allowed.
Example 1:
Input: n = 3, k = 7 Output: [181,292,707,818,929] Explanation: Note that 070 is not a valid number, because it has leading zeroes.
Example 2:
Input: n = 2, k = 1 Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]
Constraints:
2 <= n <= 90 <= k <= 9Problem Overview: Generate all n-digit integers where the absolute difference between every pair of consecutive digits equals k. Leading zeros are not allowed, so every number must start with digits 1–9. The goal is to efficiently construct all valid numbers that satisfy this constraint.
Approach 1: Brute Force Method (O(10^n * n) time, O(1) extra space)
The straightforward strategy checks every possible n-digit number from 10^(n-1) to 10^n - 1. For each number, iterate through its digits and verify that the absolute difference between consecutive digits equals k. If all pairs satisfy the condition, add the number to the result. This approach works but wastes time validating numbers that clearly cannot satisfy the constraint. Because it examines up to 9 * 10^(n-1) numbers and each validation scans up to n digits, the total complexity becomes O(10^n * n). It is useful for understanding the problem but rarely acceptable in interviews due to the exponential search space.
Approach 2: BFS / Backtracking Construction (O(2^n) time, O(2^n) space)
A better strategy constructs valid numbers digit by digit instead of testing every possibility. Start with digits 1–9. For each partial number, look at its last digit d. The next digit must be either d + k or d - k (if those values stay within 0–9). Append the valid digit and continue building the number until the length reaches n. This can be implemented using either backtracking recursion or a queue-based breadth-first search. Each step expands at most two branches, so the search tree stays small compared to brute force. A small optimization avoids duplicating work when k = 0, since both transitions produce the same digit.
Recommended for interviews: The BFS/backtracking construction is the expected solution. It demonstrates that you recognize the constraint structure and generate only valid states rather than filtering invalid ones. Mentioning the brute force approach first shows problem analysis skills, but implementing the constructive search shows stronger algorithmic thinking and familiarity with state expansion techniques.
The brute force method involves iterating through all possible solutions to find the correct one. While it might not be the most efficient, it serves as a good starting point to understand the problem.
This solution demonstrates a basic function using the brute force approach in C. Adjust the implementation as per your problem.
Time Complexity: O(n^2)
Space Complexity: O(1)
This approach utilizes an efficient data structure that best fits the problem, reducing time complexity. Choose from hash tables, arrays, or trees based on the requirements.
This solution demonstrates a more optimized function using specific data structures in C. Optimize the implementation based on your problem.
Time Complexity: O(n)
Space Complexity: O(n) using auxiliary data structures.
We can enumerate the first digit of all numbers of length n, and then use the depth-first search method to recursively construct all numbers that meet the conditions.
Specifically, we first define a boundary value boundary = 10^{n-1}, which represents the minimum value of the number we need to construct. Then, we enumerate the first digit from 1 to 9. For each digit i, we recursively construct the number of length n with i as the first digit.
The time complexity is (n times 2^n times |\Sigma|), where |\Sigma| represents the set of digits, and in this problem |\Sigma| = 9. The space complexity is O(2^n).
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force Method | Time Complexity: O(n^2) |
| Approach 2: Optimized Method using a Data Structure | Time Complexity: O(n) |
| DFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(10^n * n) | O(1) | Conceptual baseline or when constraints are extremely small |
| BFS / Backtracking Digit Construction | O(2^n) | O(2^n) | Preferred solution; generates only valid numbers and scales well for typical constraints |
Numbers With Same Consecutive Differences | LeetCode 967 | C++, Java, Python • Knowledge Center • 7,338 views views
Watch 9 more video solutions →Practice Numbers With Same Consecutive Differences with our built-in code editor and test cases.
Practice on FleetCode