2375. Construct Smallest Number From DI String

MediumStackGreedyStringBacktracking
Leetcode Link

Problem Description

In this problem, youโ€™re given a string pattern consisting of characters 'I' and 'D'. The 'I' stands for "increasing" and 'D' for "decreasing". Based on this pattern, you need to create another string num that follows these rules:

  1. String num is formed by the digits '1' to '9', each digit can only be used once.
  2. If pattern[i] == 'I', then the ith element of num must be less than the (i+1)th element.
  3. If pattern[i] == 'D', then the ith element of num must be greater than the (i+1)th element.

The goal is to find the lexicographically smallest string num that satisfies the given pattern.

Intuition

To solve this problem, we can use a backtracking approach which is a type of depth-first search (DFS). The main idea is to build the string num one digit at a time, choosing the smallest possible digit at each step that satisfies the pattern requirement.

When we are at index u in the num string, we have some options to consider for num[u]. We can choose any digit from '1' to '9', but only if that digit has not been used before (because each digit should appear at most once), and it must also satisfy the increasing or decreasing conditions as per the pattern.

As soon as we place a digit at index u, we recursively call the function to handle index u+1. If we reach the end of the pattern and have built a valid num string, we store the result and stop the search.

The reason why this generates the lexicographically smallest num is that we always try to place the smallest possible digit at each step. If at any step, no digit satisfies the condition, we backtrack, which means we undo the last step and try a different digit.

This process continues until all the possibilities are explored, or we find the answer. As soon as the answer is found, we stop the search to ensure we have the lexicographically smallest solution.

Learn more about Stack, Greedy and Backtracking patterns.

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

Which of the following array represent a max heap?

Solution Approach

The solution approach uses a backtracking algorithm, which is implemented through a recursive function named dfs. It explores all possible combinations of the digits from '1' to '9' to build the string num. Here's a run-down of the key aspects of the backtracking approach:

  1. The recursion is controlled by the function dfs(u), where u represents the current index in num that we are trying to fill.

  2. A list vis of length 10 is used to keep track of the digits that have been used so far. vis[i] is True if the digit i is already used in the string.

  3. The t list is used to construct the num string in progress. When a digit is placed at index u, it is appended to t.

  4. The base case of the recursion occurs when u == len(pattern) + 1. This means we have filled all the positions in num and we have a candidate solution. We then join all the characters in t to form the string ans, and the search is halted since we only want the lexicographically smallest solution.

  5. Within the recursive function, a for-loop iterates through digits i from 1 to 9 to try each as the next character of num. For each digit, there are two main conditions to check:

    • If the current index u is not zero and the pattern at u-1 is 'I', the current digit i should only be placed if it is greater than the last placed digit t[-1].
    • Similarly, if the pattern at u-1 is 'D', the digit i should be less than t[-1].

    If either condition is not satisfied, it skips the current digit.

  6. If the digit i satisfies the condition, it is marked as visited (vis[i] = True), added to the temporary list t, and the function recursively calls itself with the next index (dfs(u + 1)).

  7. After the recursive call returns, whether it found a solution or not, the chosen digit is unmarked (vis[i] = False) and removed from t (backtracking) so that future recursive calls can consider it.

  8. The recursion and backtracking continue until all valid digit permutations that meet the pattern conditions are explored or until the solution is found.

The ans variable is used to store the lexicographically smallest number that is formed. Since the algorithm always tries the smallest digit first and goes in increasing order, it ensures that the first complete number that is formed will be the lexicographically smallest.

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

What's the relationship between a tree and a graph?

Example Walkthrough

Let's consider a small example to illustrate the solution approach using the pattern "IDID". Our aim is to find the lexicographically smallest num that follows this pattern.

  1. Start with an empty num string and vis list initializing all elements to 'False' indicating that no digits have been used yet.

  2. Call dfs(0) to fill num[0]. At this stage, our num string and the pattern look like this: num = "", pattern = "IDID".

  3. Since u is 0, we don't have any previous digits in num. We can choose any digit from 1 to 9. We start by choosing the smallest available digit, '1'. Before we move on to the next index, we mark '1' as used in vis.

  4. Now, we recursively call dfs(1). The pattern at u - 1 (pattern[0]) is 'I', which means we need num[1] to be greater than '1'. The smallest available digit that satisfies this is '2'. num now looks like this: num = "12".

  5. Next, we call dfs(2). The pattern at u - 1 (pattern[1]) is 'D'. Hence, num[2] needs to be less than '2'. We choose the smallest available digit that is less than '2', which is '1', but since '1' is already used, our next available smallest option is '3', this does not satisfy the condition so we move to the next digit which is not used that satisfies the 'D', which is '1'.

  6. With num = "121", we recursively call dfs(3). The pattern at u - 1 (pattern[2]) is 'I', so num[3] should be greater than '1'. The smallest available digit is '2', but it's already used. The next smallest available is '3', so we choose '3' and num becomes "1213".

  7. Finally, we call dfs(4). Since we're at the end of the pattern, we've generated a valid num that adheres to the rules. The recursion base case is reached and we store num = "1213" as ans.

  8. Since we attempt to place the digits in increasing order and stop once the valid num is completed, we guarantee that our solution is the lexicographically smallest possible num.

In summary, the smallest num that follows the pattern "IDID" is "1213".

Solution Implementation

1class Solution:
2    def smallest_number(self, pattern: str) -> str:
3        # Helper function for depth-first search to build valid numbers
4        def dfs(position):
5            nonlocal smallest
6            # If a valid number is found, stop further search
7            if smallest:
8                return
9            # Check if all positions are filled satisfying the pattern
10            if position == len(pattern) + 1:
11                smallest = ''.join(current_number)
12                return
13            # Try all possible digits from 1 to 9 for the next character
14            for digit in range(1, 10):
15                if not visited[digit]:
16                    # If 'I' is encountered, the digit must be greater than the previous digit
17                    if position and pattern[position - 1] == 'I' and int(current_number[-1]) >= digit:
18                        continue
19                    # If 'D' is encountered, the digit must be smaller than the previous digit
20                    if position and pattern[position - 1] == 'D' and int(current_number[-1]) <= digit:
21                        continue
22                    # Mark the digit as used and add it to the current number
23                    visited[digit] = True
24                    current_number.append(str(digit))
25                    # Recursively continue to the next position
26                    dfs(position + 1)
27                    # Backtrack: unmark the digit and remove it from the current number
28                    visited[digit] = False
29                    current_number.pop()
30
31        # Initialize the list to keep track of visited digits
32        visited = [False] * 10
33        # Initialize the list to construct the current number
34        current_number = []
35        # Variable to keep track of the smallest number found
36        smallest = None
37        # Start DFS from the first digit
38        dfs(0)
39        # Return the smallest number that fits the given pattern
40        return smallest
41
1class Solution {
2    // Array to keep track of visited digits
3    private boolean[] visited = new boolean[10];
4    // StringBuilder to construct the sequence incrementally
5    private StringBuilder sequence = new StringBuilder();
6    // String to store the given pattern
7    private String pattern;
8    // String to store the final answer sequence
9    private String answer;
10
11    public String smallestNumber(String pattern) {
12        this.pattern = pattern;
13        // Starting the depth-first search (DFS)
14        dfs(0);
15        // Return the final answer sequence
16        return answer;
17    }
18
19    // Helper method for the DFS
20    private void dfs(int position) {
21        // If an answer is already found, stop the recursion
22        if (answer != null) {
23            return;
24        }
25        // If the length of sequence equals the length of pattern + 1, we have a complete sequence
26        if (position == pattern.length() + 1) {
27            // Set the current sequence as the answer
28            answer = sequence.toString();
29            return; // Stop further recursion
30        }
31        // Iterate through all possible digits (1 to 9)
32        for (int i = 1; i < 10; ++i) {
33            // If the current digit i has not been used yet
34            if (!visited[i]) {
35                // If the last added digit should be less according to the pattern 'I'
36                if (position > 0 && pattern.charAt(position - 1) == 'I' && sequence.charAt(position - 1) - '0' >= i) {
37                    continue; // Skip this digit since it would break the pattern
38                }
39                // If the last added digit should be more according to the pattern 'D'
40                if (position > 0 && pattern.charAt(position - 1) == 'D' && sequence.charAt(position - 1) - '0' <= i) {
41                    continue; // Skip this digit since it would break the pattern
42                }
43                // Mark the digit as used
44                visited[i] = true;
45                // Add the digit to the sequence
46                sequence.append(i);
47                // Recurse to the next position with updated sequence and visited digits
48                dfs(position + 1);
49                // Backtrack: remove the last digit from the sequence
50                sequence.deleteCharAt(sequence.length() - 1);
51                // Mark the digit as not used (undo the previous marking)
52                visited[i] = false;
53            }
54        }
55    }
56}
57
1class Solution {
2public:
3    string smallestNumber = "";     // To store the answer
4    string pattern;                 // To store the input pattern
5    vector<bool> visited;           // To keep track of visited digits
6    string tempNumber = "";         // Temporary number for DFS traversal
7
8    // Entry function to find the smallest number satisfying the pattern
9    string smallestNumber(string pattern) {
10        this->pattern = pattern;    // Initialize the class member with the input pattern
11        visited.assign(10, false);  // All digits are initially not visited
12        dfs(0);                     // Start the Depth-First Search (DFS) from index 0
13        return smallestNumber;      // Return the smallest number that satisfies the pattern
14    }
15
16    // Recursive function to perform DFS and find the solution
17    void dfs(int index) {
18        if (smallestNumber != "") return; // If already found the solution, exit the function
19        if (index == pattern.size() + 1) { // If the size of tempNumber is correct
20            smallestNumber = tempNumber;   // Assign tempNumber to smallestNumber
21            return;
22        }
23        for (int i = 1; i < 10; ++i) { // Loop through digits 1 to 9
24            if (!visited[i]) { // If digit i has not been used
25                // Skip if current pattern requires increase and the last digit in tempNumber is not less than i
26                if (index > 0 && pattern[index - 1] == 'I' && tempNumber.back() - '0' >= i) continue;
27                // Skip if current pattern requires decrease and the last digit in tempNumber is not greater than i
28                if (index > 0 && pattern[index - 1] == 'D' && tempNumber.back() - '0' <= i) continue;
29                visited[i] = true;               // Mark digit i as visited
30                tempNumber += to_string(i);      // Append digit i to the tempNumber
31                dfs(index + 1);                  // Recur for the next index
32                tempNumber.pop_back();           // Backtrack: remove the last digit from tempNumber
33                visited[i] = false;              // Backtrack: mark digit i as not visited
34            }
35        }
36    }
37};
38
1// Function to find the smallest number that matches the given pattern
2function smallestNumber(pattern: string): string {
3    const patternLength = pattern.length;
4    // Result array to hold the sequence of digits forming the smallest number
5    const result = new Array(patternLength + 1).fill('');
6    // Visited array to keep track of used digits
7    const visited = new Array(patternLength + 1).fill(false);
8
9    // Depth-first search function to build the result sequence
10    // i: current position in the pattern, currentNum: current digit to consider
11    const depthFirstSearch = (i: number, currentNum: number) => {
12        // Base case: if we've reached the end of the pattern, return
13        if (i === patternLength) {
14            return;
15        }
16
17        // If currentNum has been used, backtrack and try a different number
18        if (visited[currentNum]) {
19            visited[currentNum] = false;
20            if (pattern[i] === 'I') { // 'I' means increasing; we go backwards with a smaller number
21                depthFirstSearch(i - 1, currentNum - 1);
22            } else { // 'D' means decreasing; we go backwards with a larger number
23                depthFirstSearch(i - 1, currentNum + 1);
24            }
25            return;
26        }
27
28        // Mark the current number as used
29        visited[currentNum] = true;
30        // Assign current number to the result array at position i
31        result[i] = currentNum;
32
33        // If the current pattern character is 'I', explore the next numbers in increasing order
34        if (pattern[i] === 'I') {
35            for (let j = result[i] + 1; j <= patternLength + 1; j++) {
36                if (!visited[j]) { // If the number has not been used
37                    depthFirstSearch(i + 1, j); // Recur with the next position and the current number
38                    return;
39                }
40            }
41            // If no valid number is found, backtrack
42            visited[currentNum] = false;
43            depthFirstSearch(i, currentNum - 1);
44        } else { // If the current pattern character is 'D', explore numbers in decreasing order
45            for (let j = result[i] - 1; j > 0; j--) {
46                if (!visited[j]) { // If the number has not been used
47                    depthFirstSearch(i + 1, j); // Recur with the next position and the current number
48                    return;
49                }
50            }
51            // If no valid number is found, backtrack
52            visited[currentNum] = false;
53            depthFirstSearch(i, currentNum + 1);
54        }
55    };
56
57    // Start the DFS with the first number being 1
58    depthFirstSearch(0, 1);
59    // Once the DFS is complete, fill in the last available number in the result
60    for (let i = 1; i <= patternLength + 1; i++) {
61        if (!visited[i]) {
62            result[patternLength] = i; // The last number in the result should be the unvisited number
63            break;
64        }
65    }
66
67    // Convert the result array to a string and return it
68    return result.join('');
69}
70
Not Sure What to Study? Take the 2-min Quiz๏ผš

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by the number of recursive calls to the dfs function, which is dependent on the length of the pattern string (n) and the branching factor at each step of the recursion.

With each recursive call to dfs, the function tries to append each number from 1 to 9 that hasn't already been used to the temporary array t. This means that in the worst case, the first recursive call will have 9 options, the second will have 8 options, and so on, resulting in a factorial time complexity.

Let's denote the length of the pattern as n. The number of recursive calls can be bounded by 9! (factorial) for small patterns, since we have at most 9 digits to use, and it decreases for each level of the recursion. However, for longer patterns, the maximum branching factor will diminish as the pattern increases beyond 9, so it will be less than 9! for patterns longer than 9.

Therefore, the time complexity can be approximated as O(9!) for patterns up to length 9. For patterns longer than 9, the time complexity is still bounded by O(9!) due to the early termination of the recursion once all digits are used.

Space Complexity

The space complexity is determined by the depth of the recursion (which impacts the call stack size) and the additional data structures used (such as the vis array and the t list).

Since the maximum depth of the recursion is equal to the length of the pattern plus one (n + 1), the contribution to the space complexity from the call stack is O(n).

The vis array is always of size 10, representing the digits 1 through 9. The size of t corresponds to the depth of the recursion, which is O(n). Therefore, the space requirements for vis are O(1) whereas for t are O(n).

Combining the contributions, the total space complexity is O(n) due also to the recursive call stack size being at most n for patterns longer than 9.

To summarize:

  • The time complexity is O(9!).
  • The space complexity is O(n).

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

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ