967. Numbers With Same Consecutive Differences

Problem Description

The given problem requires us to generate all possible integers of a specified length 'n' where the absolute difference between every pair of consecutive digits is 'k'. The key points to consider are:

The length of each integer should be exactly 'n' digits long.
Consecutive digits in an integer should have a difference of 'k'.
The integers should not contain any leading zeros.
The result can be returned in any order.

For example, if n = 3 and k = 7, one possible integer could be 181, where the difference between 8 and 1 is 7.

Intuition

To solve this problem, a depth-first search (DFS) algorithm can be leveradged. The intuition behind using DFS is to build each valid integer digit by digit and to backtrack when a digit that does not satisfy the constraints is reached. Here is a step-by-step intuition guide for the DFS approach:

Start with a digit between 1 and 9 (since we cannot have leading zeros), and treat this as the current integer.
Perform DFS to add the next digit to the current integer. This digit must be within the range 0-9 and should differ by 'k' from the last digit of the current integer.
If 'k' is zero, ensure that you only add the same digit as previously added to prevent duplicates.
Repeat the process until the length of the current integer is 'n'.
Once an integer of length 'n' is built, add it to the result list.
Continue exploring other possibilities by backtracking and trying other digits for each position.

The DFS continues until all possible combinations that meet the conditions have been explored and added to the result list. By using DFS, we both build the integers and validate them at each step of the process.

Learn more about Breadth-First Search and Backtracking patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which two pointer techniques do you use to check if a string is a palindrome?

Fast-slow pointersTwo pointers moving in opposite directionSliding windowPrefix sum

I don’t know

Solution Approach

The implementation uses a Depth-First Search (DFS) method defined as dfs, a recursive approach, which is suitable for building combinations and is used to explore each possible number according to the constraints. The dfs function receives three parameters: n, k, and the current temporary integer t.

Here's a step-by-step explanation of the solution approach based on the provided code:

Initializing the Answer List: A list named ans is initialized to store the resulting valid integers.
Depth-First Search (DFS): The dfs function is defined with the following logic:
- Base Case: If the remaining length for the integer (n) is zero, the current integer (t) satisfies the length requirement and is added to the answer list, ans.
- Calculating the Next Digit: The last digit is obtained by performing t % 10.
- Exploring Next Digits:
  - If last + k is less than or equal to 9, a recursive call dfs(n - 1, k, t * 10 + last + k) is made to explore the possibility of adding last + k as the next digit.
  - Similarly, if last - k is greater or equal to zero and k is not zero (to avoid duplicate digits when k is zero), another recursive call dfs(n - 1, k, t * 10 + last - k) is made to explore the possibility of adding last - k as the next digit.
This recursive pattern allows the exploration of all valid combinations of digits where the difference between each consecutive pair is k.
Initiating DFS for Each Starting Digit: A loop from 1 to 9 is used to start the process since the numbers cannot have leading zeros. For each starting digit i, the dfs function is called with n - 1 since one digit is already used, k, and i as the current temporary integer t.
Returning the Result: After all the DFS calls are completed, return the list ans which contains all the valid integers meeting the specified conditions.

Pattern used: DFS (Depth-First Search)

Data Structures: List for storing the results (ans).

The recursive nature of DFS helps in building numbers digit by digit while maintaining the difference k between consecutive digits, thus satisfying all the constraints of the problem effectively.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

To illustrate the solution approach, let's consider a small example where n = 2 and k = 1. We want to generate all possible integers of length 2 where the absolute difference between every pair of adjacent digits is 1.

Initializing the Answer List: We start by initializing an empty list ans which will store our results.
Initiating DFS for Each Starting Digit: We iterate through digits 1 to 9 as the first digit of our potential integer because we cannot have leading zeros.
- Let's choose the starting digit 1. We now call dfs(n - 1, k, t), which translates to dfs(1, 1, 1) since we have used one digit (1) already.
Depth-First Search (DFS): Inside the DFS function:
- Base Case: For dfs(1, 1, 1), n is not zero, so we do not add t to ans yet.
- Calculating the Next Digit: The last digit obtained is 1 (since t % 10 = 1).
- Exploring Next Digits:
  - Since last + k is 2 (which is less than or equal to 9), we make a recursive call: dfs(n - 1, k, t * 10 + last + k) which is dfs(0, 1, 12).
  - For dfs(0, 1, 12), n is zero, meaning we've built a valid integer of the correct length, hence we add 12 to our answer list ans.
  - Now we also check if we can subtract k from last, but since last - k would be 0 and it's already been considered, we don't proceed with this subtraction.
We proceed to the next starting digit 2 and repeat the DFS steps:
- Call dfs(1, 1, 2).
  - Possible next digits are 1 (2-1) and 3 (2+1).
  - For 1, call dfs(0, 1, 21) and add 21 to ans.
  - For 3, call dfs(0, 1, 23) and add 23 to ans.
Continue this process with all starting digits from 1 to 9.
Returning the Result: After all DFS calls with starting digits 1 to 9 are completed, we return the list ans which now contains [12, 21, 23, 32, 34, 43, ..., 89, 98].

For this example, we have iteratively built each possible 2-digit number that follows the absolute difference constraint of 1 by exploring each digit starting from 1 to 9 and using the DFS method to build out the integers.

Pattern used: DFS (Depth-First Search)

Data Structures: List (ans) for storing the results.

Solution Implementation

1from typing import List
2
3class Solution:
4    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
5        # Initialize a list to hold the final results
6        results = []
7
8        # Define a depth-first search function for constructing numbers
9        def depth_first_search(num_length: int, k: int, current_number: int):
10            # Base case: when the number length becomes 0, we have a complete number
11            if num_length == 0:
12                results.append(current_number)
13                return
14            # Get the last digit of the current number
15            last_digit = current_number % 10
16            # If adding k to the last digit fills the condition (digit stays between 0 to 9)
17            if last_digit + k <= 9:
18                depth_first_search(num_length - 1, k, current_number * 10 + last_digit + k)
19            # If subtracting k from the last digit fills the condition and k is not 0 (to prevent duplicates)
20            if last_digit - k >= 0 and k != 0:
21                depth_first_search(num_length - 1, k, current_number * 10 + last_digit - k)
22
23        # Start the DFS process from digits 1 to 9 (since the number cannot start with 0)
24        for i in range(1, 10):
25            depth_first_search(n - 1, k, i)
26        # Return the list of results after DFS completion
27        return results
28
29# Example usage:
30# solution = Solution()
31# print(solution.numsSameConsecDiff(3, 7))  # This will print all the numbers of length 3 with consecutive differences of 7.
32

1class Solution {
2
3    // Main method to find and return all numbers of length n where the difference between 
4    // every two consecutive digits is k
5    public int[] numsSameConsecDiff(int n, int k) {
6        List<Integer> results = new ArrayList<>();
7        // Starting from 1 because numbers cannot have leading zeros
8        for (int i = 1; i < 10; ++i) {
9            depthFirstSearch(n - 1, k, i, results);
10        }
11        // Convert the list to an array
12        int[] answer = new int[results.size()];
13        for (int i = 0; i < results.size(); ++i) {
14            answer[i] = results.get(i);
15        }
16        return answer;
17    }
18
19    // Helper function for depth-first search
20    private void depthFirstSearch(int remainingDigits, int diff, int currentNum, List<Integer> results) {
21        // Base case: if no more digits are needed, add the current number to the result
22        if (remainingDigits == 0) {
23            results.add(currentNum);
24            return;
25        }
26        // Get the last digit of the current number
27        int lastDigit = currentNum % 10;
28        // Check if we can add 'diff' to the last digit without exceeding 9
29        if (lastDigit + diff <= 9) {
30            depthFirstSearch(remainingDigits - 1, diff, currentNum * 10 + lastDigit + diff, results);
31        }
32        // Check if we can subtract 'diff' from the last digit without going below 0
33        // Also, avoid repeating the same number if diff is 0
34        if (lastDigit - diff >= 0 && diff != 0) {
35            depthFirstSearch(remainingDigits - 1, diff, currentNum * 10 + lastDigit - diff, results);
36        }
37    }
38}
39

1class Solution {
2public:
3    vector<int> result; // Use a more descriptive name for the global answer storage.
4
5    // Function to find all numbers with unique digits and a difference of 'k' between consecutive digits.
6    vector<int> numsSameConsecDiff(int n, int k) {
7        // Start from digit 1 to 9, and use these as the starting digits for our numbers.
8        for (int start = 1; start <= 9; ++start) {
9            dfs(n - 1, k, start); // Start a DFS for each number of length n with the given 'k'.
10        }
11        return result; // Return the global result vector containing all valid numbers.
12    }
13
14    // Helper Depth-First Search function to build numbers according to the given constraints.
15    void dfs(int n, int k, int current) {
16        if (n == 0) { // If the number has reached its target length
17            result.push_back(current); // Add the number to the result list
18            return; // Exit the recursion
19        }
20        int lastDigit = current % 10; // Get the last digit of the current number
21        // Check if adding 'k' to the last digit remains a digit
22        if (lastDigit + k < 10) {
23            dfs(n - 1, k, current * 10 + lastDigit + k); // Form the next number in the sequence
24        }
25        // Check if subtracting 'k' from the last digit remains a digit and 'k' is non-zero to avoid repeats
26        if (lastDigit - k >= 0 && k != 0) {
27            dfs(n - 1, k, current * 10 + lastDigit - k); // Form the next number in the sequence
28        }
29    }
30};
31

1let result: number[] = []; // This now uses camelCase naming and TypeScript syntax for type declaration
2
3// Function to find all numbers with unique digits and a fixed difference 'k' between consecutive digits.
4function numsSameConsecDiff(n: number, k: number): number[] {
5    // Start from digit 1 to 9, treating these as the initial digits for potential numbers.
6    for (let start = 1; start <= 9; ++start) {
7        dfs(n - 1, k, start); // Initiate a Depth-First Search for each number of length 'n' matching difference 'k'.
8    }
9    return result; // Return the populated result array containing all valid numbers.
10}
11
12// Helper function for Depth-First Search to construct numbers adhering to the constraints.
13function dfs(n: number, k: number, current: number): void {
14    if (n === 0) { // Base case: if the number has reached its required length,
15        result.push(current); // it is added to the result array.
16        return; // Exit the current recursive call.
17    }
18    const lastDigit = current % 10; // Extract the last digit of the current number.
19
20    // If the new digit after adding 'k' is still in the range [0, 9],
21    if (lastDigit + k < 10) {
22        dfs(n - 1, k, current * 10 + lastDigit + k); // Construct and explore this next number in the sequence.
23    }
24  
25    // If the new digit after subtracting 'k' is in the range [0, 9] and 'k' is not zero (to avoid duplicates),
26    if (lastDigit - k >= 0 && k !== 0) {
27        dfs(n - 1, k, current * 10 + lastDigit - k); // Construct and explore this next number in the sequence.
28    }
29}
30
31// Example of calling the method:
32// const uniqueNumbers = numsSameConsecDiff(3, 7);
33

Not Sure What to Study? Take the 2-min Quiz：

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First SearchBreadth-First SearchBinary SearchPriority Queue

I don’t know

Time and Space Complexity

Time Complexity

The given Python code defines a function numsSameConsecDiff that generates numbers of length n having a difference of k between every two consecutive digits. The function uses Depth-First Search (DFS) with pruning.

For each starting digit from 1 to 9 (i in the loop), the DFS function is called. Inside dfs, the recursive call reduces the n by 1 until it reaches 0, at which point a number is formed and added to the answer list (ans). There are two recursive calls in the function, one for last + k and another for last - k, however, when k is 0, they result in the same digit being added, so only one recursive call is need in that case, effectively pruning the search space.

The worst-case time complexity is when k is not 0 and we have to explore both increasing and decreasing options at each step, which gives us O(2^n) - this is because, at each step, you have a possibility of two different digits to be appended, effectively doubling the possibilities with each additional digit until reaching the desired length n.

However, the actual time complexity might be less than O(2^n) due to two factors:

Pruning occurs when last + k > 9 or last - k < 0, in which case the respective recursive call is not made.
There's no branching when k = 0, since last + k and last - k result in the same digit.

Space Complexity

The space complexity of the code is O(n). This is because of the call stack that is used when the dfs function is recursively called. The depth of the recursive call stack will at most be n, where n is the length of the number we want to create. The list ans also uses space, but it doesn't contribute more than O(10^n) in space complexity, since we're only generating number sequences of length n starting with a non-zero digit, which in the worst-case gives us all permutations of n-length numbers starting with non-zero digits. However, this is a constant factor when considering space complexity with respect to n.

Thus, the overall space complexity is O(n) from the recursive call stack. Meanwhile, the space to hold the generated numbers is dependent on the number of valid combinations found, which is not directly dependent on n, but rather a combination of both n and k.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer techniques do you use to check if a string is a palindrome?

Fast-slow pointersTwo pointers moving in opposite directionSliding windowPrefix sum

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

967. Numbers With Same Consecutive Differences

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings