Numbers With Same Consecutive Differences: Digit-by-Digit BFS

Given two integers n and k, return all non-negative integers of length n where the absolute difference between every two consecutive digits is k. Note that every number in the answer must not have leading zeros. The answer can be returned in any order.

This is LeetCode 967: Numbers With Same Consecutive Differences, and it is a clean example of building valid sequences one element at a time. Instead of generating all possible n-digit numbers and checking each one, you grow numbers digit by digit, only keeping those that satisfy the constraint at every step.

The problem

You are given n (the number of digits) and k (the required absolute difference between consecutive digits). You need to find every n-digit number where each pair of adjacent digits differs by exactly k.

For example, with n=3 and k=7, the valid numbers are [181, 292, 707, 818, 929]. Starting from digit 1, the only next digit that differs by 7 is 8 (since 1+7=8). From 8, the only valid next digit is 1 (since 8-7=1, and 8+7=15 is out of the single-digit range). So 181 is one answer.

Why this problem matters

This problem teaches you the BFS level-by-level construction pattern. Rather than thinking about the entire number at once, you think about one digit position at a time. At each level of the BFS, every number in your queue grows by one digit. This is the same idea behind Letter Combinations of a Phone Number, where each BFS level processes one digit of the input.

The constraint here is local: you only need to look at the last digit of the current number to decide which digits can come next. That makes the problem a natural fit for BFS or DFS, because at each step you have at most two choices (last digit + k or last digit - k), and you can immediately reject any choice that falls outside the range 0-9.

Understanding this pattern also helps with problems where you need to construct sequences subject to step-by-step constraints. Once you see that "build it one piece at a time, pruning invalid extensions" is the core idea, you can apply the same approach to a wide range of problems.

The brute force approach

The naive approach would be to generate every n-digit number from 10^(n-1) to 10^n - 1, then check whether each one satisfies the consecutive-difference constraint. For each number, you would extract its digits and verify that every adjacent pair differs by exactly k.

This works, but the search space is enormous. For n=9, you would check roughly 900 million numbers. Most of them will fail the constraint. The brute force approach does not exploit the structure of the problem at all.

The key insight

Instead of generating all numbers and filtering, build the numbers digit by digit. Start with every valid first digit (1 through 9, since leading zeros are not allowed). Then, for each partial number, look at its last digit and compute which digits could come next: last + k and last - k. If either of those falls in the range 0 to 9, extend the number. Repeat until the number has n digits.

This is BFS where each level corresponds to one digit position. The queue starts with single-digit seeds, and after n - 1 rounds of expansion, every number in the queue has n digits and satisfies the constraint by construction.

Walking through it step by step

The solution

class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> list[int]:
        current = list(range(1, 10))  # seeds: digits 1-9

        for _ in range(n - 1):
            nxt = []
            for num in current:
                last = num % 10
                if last + k <= 9:
                    nxt.append(num * 10 + last + k)
                if k != 0 and last - k >= 0:
                    nxt.append(num * 10 + last - k)
            current = nxt

        return current

The outer loop runs n - 1 times (we already have 1-digit seeds, so we need n - 1 more digits). In each iteration, we build a new list nxt by expanding every number in current.

For each number, last = num % 10 extracts the last digit. We then check whether last + k is a valid digit (<= 9). If so, we append num * 10 + last + k, which is the original number with the new digit tacked on. Similarly, if last - k is valid (>= 0) and k is not zero, we append num * 10 + last - k.

The k != 0 check prevents adding the same number twice when k is zero. If k=0, then last + k and last - k are both last, so without the check you would get duplicates.

After the loop, current contains all valid n-digit numbers.

Complexity analysis

Time: At each BFS level, every number can branch into at most 2 new numbers (one for last + k and one for last - k). Starting with 9 seeds and expanding n - 1 times, the upper bound is 9 * 2^(n-1), which is O(2^n). In practice the branching factor is often less than 2 because many expansions fall outside the 0-9 range.

Space: The queue current holds all numbers at the current BFS level. In the worst case this is also O(2^n). The output itself requires the same space, since we return all valid numbers.

Building blocks

1. BFS level-by-level construction

The core pattern here is using BFS to build sequences one element at a time. You maintain a queue of partial results, and at each level you extend every partial result by one step. This same approach works for Letter Combinations of a Phone Number, where each level processes one digit of the input and appends all possible letters.

2. Digit constraint propagation

At each step, the only information you need to decide valid extensions is the last digit. This is a form of local constraint propagation: you do not need to re-examine the entire number, just the most recent digit. This locality is what makes the BFS approach efficient. Problems like Knight Dialer use the same idea, where the next move depends only on the current position.

Edge cases

• k = 0: Every consecutive pair must differ by 0, so all digits are the same. The answer is [111...1, 222...2, ..., 999...9]. The k != 0 guard in the code prevents double-counting.
• n = 1: Return [0, 1, 2, ..., 9]. Every single digit is valid. Note that 0 is included here because single-digit numbers do not have leading-zero issues. You need to handle this as a special case since the seed list normally starts at 1.
• Large k (e.g., k = 8 or 9): Very few starting digits produce valid branches. For k = 9, only 9 can extend to 90... and 0 can extend back to 9. The BFS queue stays small.
• k = 1: Many digits branch into two valid next digits (e.g., 5 can go to 4 or 6). This produces the largest output for a given n.

Common mistakes

1. Forgetting the k = 0 duplicate check. When k = 0, last + k and last - k are the same value. Without the k != 0 guard on the subtraction branch, you add each number twice to the next queue.

2. Allowing leading zeros. The seeds must be 1-9, not 0-9. A number like 070 is not a valid 3-digit number. The only exception is n = 1, where 0 is a valid single-digit answer.

3. Off-by-one in digit range. The valid digit range is 0 through 9 inclusive. A common mistake is using last + k < 10 (which happens to be correct) but writing last - k > 0 instead of last - k >= 0. Digit 0 is valid as a non-leading digit.

4. Running the expansion loop n times instead of n - 1. The seeds already have 1 digit. You only need n - 1 more rounds of expansion to reach n digits. Running n rounds produces numbers with n + 1 digits.

From understanding to recall

You understand the BFS level-by-level expansion. You see how starting with 1-digit seeds and appending valid next digits builds the answer without generating any invalid numbers. But can you write the solution from scratch in under two minutes during an interview?

The tricky parts are the k = 0 guard, the n = 1 special case, and the loop bound of n - 1. These are small details that are easy to forget under pressure. Spaced repetition drills them into your recall so they become automatic. You see "consecutive differences" and the code flows out: seed with 1-9, loop n - 1 times, expand by last + k and last - k, guard against duplicates when k = 0.

Related posts

• Letter Combinations of a Phone Number - BFS digit-by-digit expansion pattern
• Permutations - Backtracking to build sequences with constraints
• Combination Sum - Constraint-based exploration of choices

The BFS construction pattern is one of the reusable building blocks that CodeBricks drills independently. Once it is automatic, any problem that asks you to build valid sequences step by step becomes a matter of plugging in the right expansion logic.