1718. Construct the Lexicographically Largest Valid Sequence

MediumArrayBacktracking
Leetcode Link

Problem Description

The challenge is to create a sequence based on a given integer n with a specific set of requirements. The sequence should be such that:

  • The integer 1 appears exactly once.
  • Each integer from 2 to n appears exactly twice.
  • For each integer i from 2 to n, the locations of the two occurrences of i in the sequence are separated by exactly a distance of i. This means if the first occurrence is at position j, the second occurrence must be at position j + i.

The goal is to return the lexicographically largest sequence possible while satisfying the above conditions. Remember, a sequence a is considered lexicographically larger than a sequence b if, at their first differing position, the number in a is greater than the number in b.

Intuition

The solution to this problem lies in depth-first search (DFS) and utilizes backtracking to explore all possible positions for each integer. Since we’re aiming for the lexicographically largest sequence, it’s beneficial to place the larger numbers first. This is why, in the DFS, integers are attempted in a descending order from n down to 1.

Here's how we derive at the approach:

  1. Depth-first search (DFS) is a common approach for problems that involve exploring all possible combinations or sequences to find one that meets given conditions. In this case, DFS is used to try different positions for each integer iteratively.

  2. We employ backtracking, which goes hand-in-hand with DFS. Backtracking allows us to undo certain steps and roll back to earlier decisions if we determine that the current path doesn't lead to a solution. This is especially important because not every initial placement of an integer will lead to a valid sequence.

  3. Beginning with the largest integer and placing it in the sequence before moving on to smaller ones ensures that we will get the lexicographically largest sequence. Because if a smaller number is placed before a larger number, the sequence cannot be the largest as per lexicographic rules.

  4. To keep track of the sequence and which numbers have been used, an array path is used to represent the current sequence, and a count array cnt helps us know how many times an integer has been placed in the sequence (0 for placed twice, 2 for not placed at all, and 1 for only 1 which should be placed once).

  5. The recursive dfs function works by trying to place each number at the current position u. If placing the number i is valid (not already used up and there is room at u + i for the second occurrence), the function recurs with the updated sequence u+1. If at any step the sequence can't be completed, the function backtracks by resetting the count and path for that number and then tries the next number.

The solution iteratively attempts to construct the sequence by exploring different positions for placing each number and backtracking if it ends up at a dead end. The process continues until the entire sequence is filled satisfactorily.

Learn more about Backtracking patterns.

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

How many times is a tree node visited in a depth first search?

Solution Approach

The solution provided is a Python implementation of depth-first search (DFS), an algorithmic technique to iterate through all possible sequences that satisfy the problem’s conditions.

Here is a breakdown of the main elements of the solution:

  • Depth-First Search (DFS): DFS is selected for its ability to iterate deep into one possible sequence path before backtracking and trying another path. The nature of DFS makes it fitting for problems where we need to explore all possible combinations to find one that meets particular criteria.

  • Backtracking: Backtracking is a form of recursion that involves choosing a path, and if it leads to an undesirable solution, we retreat and choose another path. The implementation uses backtracking to place numbers in the sequence, then backtrack if the current number choice does not lead to a valid sequence.

  • Recursive Function dfs: The dfs function takes the current position u in the sequence array as an argument. It tries to find a suitable place for each integer, beginning with n and decrementing. If the integer can be placed without violating the conditions, dfs is called recursively to try to place the next number.

  • Count Array cnt: An array called cnt keeps a count of how many times each integer can still be used in the sequence. Initially, all values are set to 2 (representing the 'unused' state), except for the integer 1 set to 1.

  • Path Array path: An array called path represents the current state of the sequence. Zeros in this array represent empty positions where integers can be placed.

The procedure of the DFS in the code is as follows:

  1. Base Case Check: If u equals the sequence length n * 2, we have filled all positions in the sequence successfully, and the function returns True.

  2. Skip Filled Position: If path[u] is non-zero, it means the position is already filled, and the function calls itself with the next position u + 1.

  3. Place Larger Numbers First: The loop runs through integers i from n down to 2 (since 1 is only placed once). It checks if the integer i can be placed at the current and corresponding u + i positions by ensuring that it has not been used yet (cnt[i] > 0) and that the u + i position is empty.

  4. Placing an Integer and Recursive Call: If the number i can be placed, it is put in the path at the current position and at u + i. The count is decremented (or set to 0, meaning the number is placed in both positions), and dfs(u + 1) is called.

  5. Backtracking: If the recursive call returns False, we backtrack by resetting the path and cnt for the integer i and trying the next integer.

  6. Placing the Number 1: After trying all numbers from n down to 2, if cnt[1] is non-zero, it means 1 has not yet been placed. It is then placed at path[u] and a recursive call is made to attempt to place the next numbers.

Once the DFS completes, and if it finds a valid sequence, the path array holds the lexicographically largest sequence, with the first element trimmed (path[1:]), as the sequence was built with a "dummy" start position to simplify index calculations.

The algorithm used ensures that the lexicographically largest sequence is found by always trying the larger numbers first. It avoids unnecessary searches by checking if placement is possible before proceeding and backtracks efficiently when it hits a dead end.

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

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Example Walkthrough

Let's say we want to create a sequence based on the integer n = 3 with the set of requirements mentioned. To illustrate the solution approach using depth-first search (DFS) and backtracking, we'll walk through a small example.

  1. We start with the largest number, n = 3. We have an empty path [0, 0, 0, 0, 0, 0] (since the sequence will be of length n * 2) and a count array cnt equal to [0, 1, 2, 2] (0 for filled, 1 for the number 1, and 2 for numbers 2 and 3).

  2. We try to place 3 in the first position of the path. Since 3 should be placed again exactly 3 positions apart, we check the fourth position path[3 + 0]. Both are empty, so we place 3 in positions 0 and 3, yielding [3, 0, 0, 3, 0, 0], and decrement cnt[3] to 0.

  3. With 3 placed, we move to the next vacant position and try to place 2. Since cnt[2] is non-zero, we can place 2 at position 1 and subsequently at position 1 + 2 = 3. However, since position 3 is already occupied by 3, placing 2 here isn't possible. So, we skip this and move to the next available position which is 2.

  4. At position 2, we place 2, and then at 2 + 2 = 4, yielding [3, 0, 2, 3, 2, 0], and we update cnt[2] to 0.

  5. Now, we only have 1 left to place, which only appears once. The next vacant position is 1, so we place 1 there, leading to [3, 1, 2, 3, 2, 0]. Since the position 5 is still empty, the sequence is not complete.

  6. We place the last 1 at position 5 to complete the sequence, resulting in [3, 1, 2, 3, 2, 1]. We have now constructed a valid sequence with cnt equal to [0, 0, 0, 0] indicating all numbers have been placed according to the rules.

By applying DFS and backtracking, we started with the largest number and worked our way down, ensuring at each step that we were creating the lexicographically largest sequence possible. When a number could not be placed, we moved to the next available spot without backtracking since the path wasn't filled yet. Once all numbers were placed correctly, we arrived at the final sequence.

Solution Implementation

1from typing import List
2
3class Solution:
4    def constructDistancedSequence(self, n: int) -> List[int]:
5        # Helper function for depth-first search.
6        def dfs(index):
7            # Base case: if the end of the sequence is reached, return True.
8            if index == len(sequence):
9                return True
10          
11            # If the current position already has a value, skip to the next position.
12            if sequence[index]:
13                return dfs(index + 1)
14          
15            # Try placing numbers starting from n down to 2.
16            for i in range(n, 1, -1):
17                # Check if the number is available and can fit in the current position.
18                if count[i] > 0 and index + i < len(sequence) and sequence[index+i] == 0:
19                    # Place the number at the current and corresponding positions and mark as used.
20                    count[i] = 0
21                    sequence[index] = sequence[index+i] = i
22                    # Recursively try to fill in the next position.
23                    if dfs(index + 1):
24                        return True
25                    # If placing i didn't lead to a solution, backtrack.
26                    sequence[index] = sequence[index+i] = 0
27                    count[i] = 2
28          
29            # Try placing number 1 if available.
30            if count[1] > 0:
31                count[1], sequence[index] = 0, 1
32                # Recursively try to fill in the next position.
33                if dfs(index + 1):
34                    return True
35                # If placing 1 didn't lead to a solution, backtrack.
36                sequence[index], count[1] = 0, 1
37          
38            # If no number can be placed, return False.
39            return False
40      
41        # Initialise the sequence with zeros, length is 'n' elements plus 'n - 1' gaps.
42        sequence = [0] * (n * 2 - 1)
43        # Count array initialized with 2 for numbers 2 to n, and 1 for number 1.
44        count = [2] * (n + 1)
45        count[1] = 1
46
47        # Start DFS from the first position.
48        dfs(0)
49        # Return the sequence with the leading zero removed.
50        return sequence[:n] + sequence[n+1:]
51
52# Example usage:
53
54# sol = Solution()
55# result = sol.constructDistancedSequence(3)
56# print(result)  # Output would be the filled sequence satisfying the conditions.
57
1class Solution {
2    private int[] path; // path array to store the sequence
3    private int[] count; // count array to keep track of the usage of numbers
4    private int numberLimit; // the limit 'n' as provided in the problem statement
5
6    // Function to construct the distance sequence
7    public int[] constructDistancedSequence(int n) {
8        this.numberLimit = n;
9        path = new int[n * 2 - 1]; // since the last number will always be '1'
10        count = new int[n + 1]; // to track count of each number
11        Arrays.fill(count, 2); // each number can be used twice except '1'
12        count[1] = 1; // '1' is used only once
13      
14        if(dfs(0)) {
15            return path;
16        }
17      
18        return new int[0]; // return an empty array if a valid sequence is not found
19    }
20  
21    // Helper method for the depth-first search
22    private boolean dfs(int index) {
23        if (index == path.length) {
24            return true; // all the numbers are placed successfully
25        }
26        if (path[index] > 0) {
27            return dfs(index + 1); // skip filled positions
28        }
29      
30        for (int i = numberLimit; i > 1; --i) {
31            if (count[i] > 0 && index + i < path.length && path[index + i - 1] == 0) {
32                // Try to place the number 'i'
33                count[i]--;
34                path[index] = i;
35                path[index + i - 1] = i;
36              
37                // Recurse, if successful, return true
38                if (dfs(index + 1)) {
39                    return true;
40                }
41              
42                // Backtrack
43                count[i]++;
44                path[index] = 0;
45                path[index + i - 1] = 0;
46            }
47        }
48      
49        if (count[1] > 0) {
50            // Place '1' in the current index
51            path[index] = 1;
52            count[1]--;
53          
54            // Recurse, if successful, return true
55            if (dfs(index + 1)) {
56                return true;
57            }
58          
59            // Backtrack if placing '1' did not lead to a solution
60            count[1]++;
61            path[index] = 0;
62        }
63      
64        // No valid placement was found for this index; return false
65        return false;
66    }
67}
68
1class Solution {
2public:
3    int sequenceLength;
4    vector<int> counter, resultSequence;
5
6    // Function to construct the Distanced Sequence based on the given integer `n`.
7    vector<int> constructDistancedSequence(int n) {
8        sequenceLength = n;
9        counter.resize(n * 2, 2); // Initializing counter with '2' to track the availability of pairs.
10        resultSequence.resize(n * 2); // Creating a result sequence array with 2 * n size.
11        counter[1] = 1; // 1 only appears once in the sequence.
12      
13        // Start the Depth First Search from the first position.
14        dfs(1);
15
16        // Compile the result without the zeroth position (1-indexed).
17        vector<int> ans;
18        for (int i = 1; i < n * 2; ++i) {
19            ans.push_back(resultSequence[i]);
20        }
21        return ans;
22    }
23
24    // Recursive function to fill the sequence with valid numbers at the correct distances.
25    bool dfs(int position) {
26        // Base case: if the end of the sequence is reached, the sequence is valid. 
27        if (position == sequenceLength * 2) return true;
28
29        // Skip already filled positions.
30        if (resultSequence[position]) return dfs(position + 1);
31
32        // Try to place numbers starting from the largest.
33        for (int i = sequenceLength; i > 1; --i) {
34            // Check if the number is available and the corresponding paired position is not filled.
35            if (counter[i] && position + i < sequenceLength * 2 && !resultSequence[position + i]) {
36                resultSequence[position] = resultSequence[position + i] = i; // Place the number at both positions.
37                counter[i] = 0; // Mark the number as used.
38
39                if (dfs(position + 1)) return true; // Recursively continue to fill the next position.
40
41                // Backtrack if the placement does not lead to a solution.
42                counter[i] = 2;
43                resultSequence[position] = resultSequence[position + i] = 0;
44            }
45        }
46
47        // Special case for '1' as it appears only once.
48        if (counter[1]) {
49            resultSequence[position] = 1; // Place '1' at the current position.
50            counter[1] = 0; // Mark '1' as used.
51
52            if (dfs(position + 1)) return true; // Recursively continue with the next position.
53
54            // Backtrack if placement of '1' does not lead to solution.
55            counter[1] = 1;
56            resultSequence[position] = 0;
57        }
58
59        // If no placement is possible, return false for backtracking.
60        return false;
61    }
62};
63
1// The length of the resulting distanced sequence.
2let sequenceLength: number;
3// Counter to track the availability of pairs (initialized later).
4let counter: number[];
5// Array representing the resulting distanced sequence.
6let resultSequence: number[];
7
8// Function to construct the Distanced Sequence based on the given integer `n`.
9function constructDistancedSequence(n: number): number[] {
10    sequenceLength = 2 * n;
11    counter = new Array(n + 1).fill(2); // Initializing counter with '2' for each pair.
12    resultSequence = new Array(sequenceLength).fill(0); // Creating a result sequence array with 2 * n size, filled with zeros.
13    counter[1] = 1; // 1 only appears once in the sequence.
14
15    // Start the Depth First Search from the first position.
16    dfs(1);
17
18    // Compile the result without the zeroth position (1-indexed equivalent in original array).
19    return resultSequence.slice(1);
20}
21
22// Recursive function to fill the sequence with valid numbers at the correct distances.
23function dfs(position: number): boolean {
24    // Base case: if the end of the sequence is reached, the sequence is completed.
25    if (position === sequenceLength) return true;
26
27    // Skip already filled positions.
28    if (resultSequence[position] !== 0) return dfs(position + 1);
29
30    // Try to place numbers starting from the largest.
31    for (let i = sequenceLength / 2; i > 1; --i) {
32        // Check if the number is available and the corresponding paired position is not filled.
33        if (counter[i] > 0 && position + i < sequenceLength && resultSequence[position + i] === 0) {
34            // Place the number at both positions.
35            resultSequence[position] = i;
36            resultSequence[position + i] = i;
37            // Mark the number as used.
38            counter[i] = 0;
39
40            // Recursively continue to fill the next position.
41            if (dfs(position + 1)) return true;
42
43            // Backtrack if the placement does not lead to a solution.
44            counter[i] = 2;
45            resultSequence[position] = 0;
46            resultSequence[position + i] = 0;
47        }
48    }
49
50    // Special case for '1' as it appears only once.
51    if (counter[1] > 0) {
52        // Place '1' at the current position.
53        resultSequence[position] = 1;
54        // Mark '1' as used.
55        counter[1] = 0;
56
57        // Recursively continue with the next position.
58        if (dfs(position + 1)) return true;
59
60        // Backtrack if placement of '1' does not lead to solution.
61        counter[1] = 1;
62        resultSequence[position] = 0;
63    }
64
65    // If no placement is possible, return false for backtracking.
66    return false;
67}
68
69// Example usage:
70let sequence = constructDistancedSequence(3);
71console.log(sequence); // This would output the distanced sequence based on your selected `n`.
72
Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Time and Space Complexity

The given Python code defines a function to construct a distinct sequence based on the input n using a backtracking approach. Let’s analyze its time complexity and space complexity:

Time Complexity

  • The maximum size of the sequence to be constructed is n * 2 - 1. We'll refer to this as m.
  • For each empty position in the path, the algorithm will attempt to place the largest number (n) down to 2, and then try 1 if all others fail.
  • The function dfs is called recursively. For each placement of a number i, it has to place i at one position and i at i positions away from the first, excluding 1 which only occupies one position.
  • Each placement of a number i > 1 reduces the number of recursive calls by i + 1 (since i and the position i steps away are filled), and for each placement of 1, the number of recursive calls is reduced by 1.
  • Since we attempt all possible placements for each number, in the worst case we have to explore nearly all permutations of the numbers greater than 1. It’s difficult to tightly bound this, but it’s a factorial relationship, leading us to an estimated upper bound of O((n-1)!*n). However, this could be considered overly pessimistic because the early placement of larger numbers greatly restricts subsequent placements.

In practice, the actual time complexity is hard to express in a closed form due to various pruning conditions in the backtracking process, which can significantly reduce the number of branches that need to be explored.

Space Complexity

  • O(n): path array of size m.
  • O(n): cnt array of similar size, although the maximum meaningful index is n.

Hence, the space complexity is dominated by these data structures and would be O(m) which simplifies to O(2n - 1) and can be denoted as O(n) since we drop constants in big O notation.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Recommended Readings

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

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

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 👨‍🏫