You are given two integers:

• n → the number of digits the number must have
• k → the required absolute difference between every pair of consecutive digits

Your task:

Return all non-negative integers of length n such that:

1. They have exactly n digits
2. No leading zero is allowed
3. The absolute difference between every adjacent digit is exactly k

Example:

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

Another example:

Input: n = 2, k = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

---

Problem Understanding

We must generate numbers with:

• length exactly n
• digits 0–9
• no leading zeros
• |digit[i] − digit[i−1]| = k

Important details:

• For n = 1, all digits 0–9 are allowed
• For n > 1, numbers cannot start with 0
• For each digit, next digit can be:
  • current + k
  • current − k
• If k = 0, avoid duplicates (only one path)

This is a number construction problem, not a checking problem.

---

Logic Explained in Simple English

A simple way to think about building valid numbers:

1. Choose a starting digit:
   • Must be 1 through 9 (cannot be 0)
2. For each next digit:
   • Look at the previous digit
   • Compute possible next digits: next1 = prev + k next2 = prev - k
   • Only keep next digits that are between 0 and 9
3. Continue until number has n digits
4. Store the completed numbers

This naturally suggests DFS or backtracking:

• Build numbers digit by digit
• Branch when multiple next digits are possible
• Stop when desired length reached

Why this works:

• It generates only valid numbers
• No filtering required afterward
• Works efficiently even when branching

---

Step-by-Step Approach

1. If n == 1 → return list containing digits 0–9
2. Initialize result list
3. Loop starting digits from 1 to 9
4. Perform DFS:
   • If built length == n → add to result
   • Else:
     • compute next digits using ±k
     • recurse if next digit within 0–9
5. Return result

Special handling:

• If k == 0, only one next digit branch should be followed to avoid duplicates

---

Java Implementation

class Solution {
    public int[] numsSameConsecDiff(int n, int k) {
        List<Integer> result = new ArrayList<>();

        if (n == 1) {
            // For n == 1, digits 0-9 are allowed
            for (int i = 0; i <= 9; i++) {
                result.add(i);
            }
            return result.stream().mapToInt(i -> i).toArray();
        }

        // Start numbers from 1 to 9 (no leading zeros)
        for (int start = 1; start <= 9; start++) {
            dfs(n, k, 1, start, result);
        }

        return result.stream().mapToInt(i -> i).toArray();
    }

    private void dfs(int n, int k, int length, int number, List<Integer> result) {
        if (length == n) {
            result.add(number);
            return;
        }

        int lastDigit = number % 10;

        int next1 = lastDigit + k;
        int next2 = lastDigit - k;

        if (next1 >= 0 && next1 <= 9) {
            dfs(n, k, length + 1, number * 10 + next1, result);
        }

        if (k != 0 && next2 >= 0 && next2 <= 9) {
            dfs(n, k, length + 1, number * 10 + next2, result);
        }
    }
}

---

Dry Run Example

Input:

n = 3, k = 2

Start digits: 1 to 9

Start = 3

Length 1: 3

Possible next digits:

3 + 2 = 5
3 - 2 = 1

Branch A:

35
Possible next digits: 3 or 7
Final numbers: 353, 357

Branch B:

31
Possible next digits: 3 or -1 (invalid)
Final number: 313

Similar expansion occurs for other starting digits.

Final output (ordered by search):

[131,135, 242,246, 353,357, 464,468, 575,579, 686,680, 797,791]

(Note: Exact ordering depends on DFS traversal.)

---

Time and Space Complexity

Time Complexity

O(2^(n-1))

Worst case when k ≠ 0 and both branches valid
But actual branching is limited (max 2 choices)

Space Complexity

O(n)

DFS recursion depth + result storage

---

Common Mistakes and How to Avoid Them

Mistake 1: Starting with 0

Only allowed when n == 1

Mistake 2: Forgetting to avoid duplicate next digits when k == 0

Must prevent double branching

Mistake 3: Filtering all numbers afterward

Better to generate only valid ones

Mistake 4: Treating negative digits as valid

Check boundaries:

0 <= digit <= 9

Mistake 5: Confusing permutations with digit constraints

Digits must follow consecutive difference, not permutation rules