LeetCode 967 - Numbers With Same Consecutive Differences

The problem asks us to generate all integers of length n such that the absolute difference between every two consecutive digits is exactly k.

leetcodemediumbacktrackingbreadth-first-search

LeetCode Problem 967

Difficulty: 🟡 Medium
Topics: Backtracking, Breadth-First Search

Solution

Problem Understanding

The problem asks us to generate all integers of length n such that the absolute difference between every two consecutive digits is exactly k. The input consists of two integers: n, the number of digits the integers must have, and k, the difference constraint between consecutive digits. The output is an array of integers that satisfy these conditions, with no leading zeros allowed.

Constraints clarify that n is between 2 and 9, and k is between 0 and 9. This means numbers will not exceed nine digits and the difference between digits is always a single-digit non-negative number. A critical edge case arises when k = 0, which requires all digits in the number to be identical, and when n = 2, which is the minimum length that still allows a difference to exist. Another consideration is avoiding numbers starting with zero, since leading zeros are invalid.

In essence, we are asked to explore combinations of digits that satisfy a strict consecutive difference rule, similar to traversing paths in a graph where each node represents a digit and edges connect digits that differ by k.

Approaches

A brute-force approach would generate all n-digit numbers and then filter them based on the consecutive difference condition. This works because we can check each number one by one, but it is inefficient. For n = 9, there are potentially 9 * 10^8 numbers (all numbers with 9 digits), which is computationally expensive to check individually.

The optimal approach relies on a backtracking or breadth-first search strategy. We construct numbers digit by digit. Starting from digits 1 through 9 (to avoid leading zeros), we recursively or iteratively add the next digit if it maintains the consecutive difference k. This method avoids generating invalid numbers entirely, rather than filtering after generation, which significantly reduces the search space.

Approach Time Complexity Space Complexity Notes
Brute Force O(9 * 10^(n-1)) O(9 * 10^(n-1)) Generate all n-digit numbers and filter those with consecutive differences equal to k
Optimal (BFS/DFS) O(2 * 9 * 10^(n-1)) O(9 * 10^(n-1)) Build valid numbers incrementally using backtracking or BFS, pruning invalid paths

Algorithm Walkthrough

  1. Initialize a list to store valid numbers. Start by considering all single-digit numbers from 1 to 9.
  2. For each number, consider the last digit and attempt to append a new digit such that the absolute difference with the last digit is exactly k.
  3. If the new digit is within 0-9, append it to the current number and continue the process recursively until the number reaches length n.
  4. Once a number reaches length n, add it to the result list.
  5. Repeat this process for all starting digits from 1 to 9.

Why it works: By building numbers one digit at a time and enforcing the difference condition at each step, we ensure all generated numbers satisfy the consecutive difference requirement. Since we start from non-zero digits and only append valid digits, no number will have leading zeros, and all numbers will have exactly length n.

Python Solution

from typing import List

class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        if n == 1:
            return [i for i in range(10)]
        
        result = []

        def dfs(num: int, length: int):
            if length == n:
                result.append(num)
                return
            last_digit = num % 10
            next_digits = set([last_digit + k, last_digit - k])
            for next_digit in next_digits:
                if 0 <= next_digit <= 9:
                    dfs(num * 10 + next_digit, length + 1)
        
        for starting_digit in range(1, 10):
            dfs(starting_digit, 1)
        
        return result

The Python solution uses a depth-first search strategy. We define a recursive function dfs that appends valid digits to the current number. By using a set for the next digits, we automatically handle the case where k = 0 without duplication. We iterate over all starting digits to avoid leading zeros. Each recursive call builds the number until the desired length n is reached.

Go Solution

func numsSameConsecDiff(n int, k int) []int {
    if n == 1 {
        result := make([]int, 10)
        for i := 0; i < 10; i++ {
            result[i] = i
        }
        return result
    }

    var result []int

    var dfs func(num int, length int)
    dfs = func(num int, length int) {
        if length == n {
            result = append(result, num)
            return
        }
        lastDigit := num % 10
        nextDigits := []int{lastDigit + k, lastDigit - k}
        for _, next := range nextDigits {
            if next >= 0 && next <= 9 {
                dfs(num*10 + next, length+1)
            }
        }
    }

    for start := 1; start <= 9; start++ {
        dfs(start, 1)
    }

    return result
}

The Go solution closely mirrors the Python version. We use a closure for the recursive DFS function. Slice operations handle appending valid numbers. Since Go does not have a built-in set, we handle duplicates implicitly because adding the same number twice is avoided by the recursion.

Worked Examples

Example 1: n = 3, k = 7

We start with digits 1-9. Consider 1:

  1. Last digit is 1. Next possible digits: 1+7=8, 1-7=-6 (invalid)
  2. Append 8 → number is 18. Last digit 8: next digits 1 and 15 (only 1 valid)
  3. Append 1 → number is 181, length reached 3 → add to result

Repeating for starting digits 2-9 yields [181, 292, 707, 818, 929].

Example 2: n = 2, k = 1

Starting digits 1-9:

  • Start with 1: next digits 0 and 2 → numbers 10, 12
  • Start with 2: next digits 1 and 3 → numbers 21, 23
  • Continue this process to generate [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Complexity Analysis

Measure Complexity Explanation
Time O(2 * 9 * 10^(n-1)) Each number can branch into at most two new numbers for each digit, starting with 9 digits
Space O(9 * 10^(n-1)) Recursive stack depth can reach n and we store all valid numbers in result

The key reasoning is that each digit has at most two options (plus or minus k) and the branching is exponential in the number of digits. Storage is dominated by the number of valid results.

Test Cases

# Provided examples
assert sorted(Solution().numsSameConsecDiff(3, 7)) == sorted([181,292,707,818,929])  # standard case
assert sorted(Solution().numsSameConsecDiff(2, 1)) == sorted([10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98])  # standard case

# Edge cases
assert sorted(Solution().numsSameConsecDiff(2, 0)) == sorted([11,22,33,44,55,66,77,88,99])  # k=0, identical digits
assert sorted(Solution().numsSameConsecDiff(1, 0)) == sorted([0,1,2,3,4,5,6,7,8,9])  # n=1 includes 0
assert sorted(Solution().numsSameConsecDiff(2, 9)) == sorted([18,27,36,45,54,63,72,81,90])  # k=9, max difference
Test Why
n=3, k=7 standard case with n>2 and k>0
n=2, k=1 standard small case, multiple valid numbers
n=2, k=0 all digits identical
n=1, k=0 single-digit numbers, including 0
n=2, k=9 edge case with max possible difference

Edge Cases

The first edge case is when k = 0. Here, the next digit must equal the last digit, producing numbers with repeated digits. Handling this properly avoids duplicates and ensures correctness. Our DFS approach naturally handles this with the set of possible next digits.

The second edge case occurs when n = 1. Since the length is one, numbers can include zero, which is normally invalid as a leading digit in longer numbers. Our implementation checks this separately and returns all digits 0-9.

The third edge case is when consecutive difference calculation results in an invalid digit outside 0-