Watch 10 video solutions for Numbers With Same Consecutive Differences, a medium level problem involving Backtracking, Breadth-First Search. This walkthrough by Knowledge Center has 7,338 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |