Skip to main content

967 - Numbers With Same Consecutive Differences

Difficulty: Medium | Pattern: BFS / DFS (Digit Building) | Company tags: Amazon, Google

Problem Statement​

Given two integers n and k, return all the integers of length n such that the absolute difference between every two consecutive digits is k.

Note that every number in the answer must not have leading zeros except for the number 0 itself. For example, 01 has one leading zero and is therefore invalid.

Return the answer in any order.

Example 1:

Input: n = 3, k = 7
Output: [181,292,707,818,929]

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]

Algorithm Flow​

Approach: BFS — O(2^n)​

def numsSameConsecDiff(n: int, k: int) -> list[int]:
    if n == 1:
        return list(range(10))
    
    # Start with first digit 1-9 (no leading zeros)
    queue = list(range(1, 10))
    
    for _ in range(n - 1):
        next_queue = []
        for num in queue:
            last_digit = num % 10
            next_digits = set()
            if last_digit + k <= 9:
                next_digits.add(last_digit + k)
            if last_digit - k >= 0:
                next_digits.add(last_digit - k)
            for d in next_digits:
                next_queue.append(num * 10 + d)
        queue = next_queue
    
    return queue

Dry Run​

n=3, k=7

Start: [1,2,3,4,5,6,7,8,9]

After 1st expansion (n-1=2 steps):

  • 1: +7=8 → 18; -7 lt 0, skip → [18]
  • 2: +7=9 → 29; -7 lt 0, skip → [29]
  • ...
  • 7: +7=14 gt 9, skip; -7=0 → 70 → [70]
  • 8: +7=15 gt 9, skip; -7=1 → 81 → [81]
  • 9: +7=16 gt 9, skip; -7=2 → 92 → [92]

After 2nd expansion:

  • 18: 8+7=15 gt 9, skip; 8-7=1 → 181 ✓
  • 29: 9+7=16 gt 9, skip; 9-7=2 → 292 ✓
  • ...

Result: [181,292,707,818,929] ✓

Why Set for Next Digits?​

When k=0, last_digit + k == last_digit - k, so we'd add the same digit twice. The set() deduplicates.

Complexity​

  • Time: O(2^n) — each digit branches into at most 2 choices
  • Space: O(2^n)

Key Terms​

TermDefinition
BFS by digit-buildingGrow candidate numbers one digit at a time, level by level, until length n
Branching factorNumber of valid next digits from a given last digit (1 or 2, based on k)
Leading-zero constraintThe first digit must come from 1-9, not 0, unless the whole number is 0
Set deduplicationUsing a set to avoid adding the same next digit twice when k == 0

FAQ​

Q1: Can this be solved with DFS/backtracking instead of BFS? Yes — DFS recursively builds one number at a time (choosing a starting digit, then extending), producing the same results with O(h) recursion depth instead of holding the full frontier in memory.

Q2: What happens when k == 0? last_digit + k and last_digit - k are equal, so without the set() deduplication step you'd append the same next number twice; the set collapses that to one.

Q3: What if n == 1? The function short-circuits and returns list(range(10)) since single-digit numbers have no "consecutive difference" constraint to apply, and 0 is allowed only in this case.

Q4: How does the algorithm avoid leading zeros? The initial queue is seeded with range(1, 10) (digits 1-9) rather than range(10), so no generated number ever starts with 0 except the special n == 1 case.

Q5: What is the time and space complexity, and why? O(2^n) time and space in the worst case, because each of the n-1 digit-extension steps can at most double the queue size (two valid next digits per number).

Quick Revision​

  • Build numbers digit by digit using BFS; each level appends one digit to every number in the queue.
  • Seed the queue with digits 1-9 to avoid leading zeros; handle n == 1 as a special case (0-9 allowed).
  • For each number, the last digit determines up to 2 valid next digits: last + k and last - k, each checked to stay in [0, 9].
  • Use a set per number to dedupe when k == 0 (both candidates are identical).
  • Run the expansion n - 1 times since the first digit is already placed.
  • Time and space are O(2^n) — branching factor of at most 2 per step.
  • This is the "generate all valid sequences" pattern, common to constrained combinatorial generation problems.
  • Compare to N-Queens style backtracking: both build a sequence one choice at a time under a positional constraint.
  • 51 - N-Queens — shares the constrained-sequence-building pattern (choose a valid value per position)
  • 52 - N-Queens II — same backtracking/counting pattern applied to a different constraint
  • Pattern match: "digit DP" / combinatorial BFS-DFS generation problems (e.g. generating valid IP addresses, letter combinations of a phone number)