Domain 2MediumMEDIUM

Numbers With Same Consecutive Differences

Generate valid numbers of length n where adjacent digit difference is k using DFS, avoiding leading zeros and pruning invalid branches.

Domain: medium•Updated: 2026-09-05
#Depth First Search#Recursion#Backtracking

Problem Breakdown

We need to construct all non-negative integers of a specific length n such that the absolute difference between every two consecutive digits equals k.

Inputs:

  • int n: The target number of digits (length). Constraint: 2≤n≤92 \le n \le 9.
  • int k: The required absolute difference between consecutive digits. Constraint: 0≤k≤90 \le k \le 9.

Outputs:

  • A list containing all valid integers satisfying the condition, in any order.

Implicit Constraints & Edge Cases:

  1. Leading Zeros: Since n≥2n \ge 2, numbers like “07” are invalid because they have a leading zero (unless n=1, which is outside constraints). The first digit must be between 1 and 9. Subsequent digits can include ‘0’ if valid by the difference rule.
  2. Overflow: Since max length is 9, numbers fit within standard integer types easily in Python or 32-bit integers (<109< 10^9). No overflow issues expected here.
  3. Duplicates: The generation process naturally avoids duplicates because we branch deterministically from each state based on valid next digits. However, when k=0k=0, the subtraction and addition branches yield the same digit; logic must ensure this single path is not traversed twice unnecessarily (though correctness remains intact).

Intuition

A brute-force approach would iterate through all numbers in the range [10n−1,10n−1][10^{n-1}, 10^n - 1] and check if they satisfy the condition for every adjacent pair of digits.

  • Complexity: This is roughly proportional to checking 9×10n−19 \times 10^{n-1} candidates, which results in exponential time complexity relative to n. For large inputs (even though constrained here), this would be too slow (O(10n)O(10^n)).

Key Insight: Instead of generating all numbers and filtering them out, we can construct valid numbers digit-by-digit. This is a classic Depth-First Search (DFS) or Backtracking problem on the state space tree where each node represents a partial number built so far.

  • We start with digits 1 through 9 for the first position to avoid leading zeros.
  • For every subsequent position, we only branch into valid next digits based on last_digit - k and last_digit + k.
  • This prunes invalid paths immediately (e.g., if a digit goes below 0 or above 9), keeping us proportional to the number of actual solutions generated rather than checking all 10n10^n possibilities.

Approach

  1. Initialize an empty list result to store valid numbers.
  2. Define a recursive helper function, say dfs(current_num, length). Passing length avoids converting integers to strings repeatedly for depth checks.
  3. Base Case: If the current number’s length equals n, append it to result and return.
  4. Recursive Step:
    • Extract the last digit from current_num using modulo 10 (%).
    • Calculate potential next digits: last_digit - k and last_digit + k.
    • Use a set or conditional logic to collect valid candidates (checking bounds [0, 9]) to handle the k=0k=0 case where both branches are identical without redundant recursion.
    • If valid, recurse with (current_num * 10) + next_digit and length + 1.
  5. Initialization: Call the DFS function for every starting digit from 1 to 9 (inclusive).

Complexity Analysis

  • Time Complexity: O(N⋅M)O(N \cdot M) where NN is n and MM is the number of valid integers generated. Since we only traverse nodes in our search tree that correspond to prefixes of valid numbers, the work done at each level is constant per branch (max 2 branches). The total time is proportional to the output size times the depth of recursion (O(output_size×n)O(\text{output\_size} \times n)). Given constraints n≤9n \le 9, this runs extremely fast.
  • Space Complexity: O(n)O(n) for the recursion stack depth, plus O(M)O(M) space to store the resulting list where MM is the count of valid numbers found.

Solution

from typing import List

def numsSameConsecDiff(n: int, k: int) -> List[int]:
    result = []
    
    # Helper function tracking current number and depth to avoid string conversion overhead
    def dfs(current_num, length):
        if length == n:
            result.append(current_num)
            return
        
        last_digit = current_num % 10
        
        candidates = set()
        
        d_minus = last_digit - k
        if d_minus >= 0:
            candidates.add(d_minus)
            
        d_plus = last_digit + k
        if d_plus <= 9:
            candidates.add(d_plus)
            
        for digit in candidates:
            dfs(current_num * 10 + digit, length + 1)

    # Start DFS with first digits from 1 to 9 (no leading zeros allowed since n >= 2)
    for i in range(1, 10):
        dfs(i, 1)
        
    return result

Edge Cases Handled

  • Leading Zeros: The initial loop range(1, 10) ensures no number starts with ‘0’. Subsequent recursive calls allow ‘0’ as a digit if valid (e.g., k=7k=7, last digit 7 →\to next is 0