Scale Engineer

Construct the Lexicographically Largest Valid Sequence

Med
#1574Time: O(S * n * n!), where S is the number of valid sequences. The algorithm explores a very large search space to find all solutions, making it very slow for larger `n`.Space: O(S * n), where S is the number of valid sequences. This is because we need to store all S solutions, each of length `2n - 1`.
Patterns
Backtracking
Data structures
Array

Prompt

Given an integer n, find a sequence with elements in the range [1, n] that satisfies all of the following:

  • The integer 1 occurs once in the sequence.
  • Each integer between 2 and n occurs twice in the sequence.
  • For every integer i between 2 and n, the distance between the two occurrences of i is exactly i.

The distance between two numbers on the sequence, a[i] and a[j], is the absolute difference of their indices, |j - i|.

Return the lexicographically largest sequence. It is guaranteed that under the given constraints, there is always a solution.

A sequence a is lexicographically larger than a sequence b (of the same length) if in the first position where a and b differ, sequence a has a number greater than the corresponding number in b. For example, [0,1,9,0] is lexicographically larger than [0,1,5,6] because the first position they differ is at the third number, and 9 is greater than 5.

 

Example 1:

Input: n = 3
Output: [3,1,2,3,2]
Explanation: [2,3,2,1,3] is also a valid sequence, but [3,1,2,3,2] is the lexicographically largest valid sequence.

Example 2:

Input: n = 5
Output: [5,3,1,4,3,5,2,4,2]

 

Constraints:

  • 1 <= n <= 20

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves finding every possible valid sequence that satisfies the given conditions. We use a standard backtracking algorithm to explore all placement possibilities. After generating all valid sequences, we compare them to find the one that is lexicographically the largest.

Algorithm

  • Create a recursive backtracking function, say generateAll(index), to build the sequence.
  • Use a boolean array used to keep track of numbers from 1 to n that have been placed in the sequence.
  • The recursive function will try to fill a sequence array of size 2n - 1.
  • Base Case: If the index reaches the end of the sequence (2n - 1), a valid sequence has been found. Add a copy of it to a list of solutions.
  • Recursive Step:
    • If the current position sequence[index] is already filled, recurse on the next index: generateAll(index + 1).
    • Otherwise, iterate through numbers i from 1 to n.
    • For each i that has not been used:
      • Try to place i at sequence[index]. If i > 1, its second occurrence must be placed at index + i.
      • If the placement is valid (i.e., the second position is within bounds and is empty), mark i as used, update the sequence, and make a recursive call: generateAll(index + 1).
      • After the recursive call returns, backtrack by undoing the placement and unmarking i as used.
  • After the initial call generateAll(0) completes, iterate through the list of all found solutions to find and return the lexicographically largest one.

Walkthrough

The fundamental idea is to treat this as a permutation problem with constraints. We can build a sequence recursively. A helper function, say generateAll(index), attempts to fill the sequence from the given index. It tries placing each unused number i (from 1 to n) at the current position and, if i > 1, its corresponding pair at index + i. If a placement is valid, it recurses to the next position. When a full valid sequence is formed, it's stored in a list. This process continues until all possibilities are exhausted. Finally, the list of solutions is scanned to find the lexicographically greatest sequence.

import java.util.ArrayList;import java.util.Arrays;import java.util.List; class Solution {    List<int[]> solutions;    boolean[] used;    int n;    int[] currentSequence;     public int[] constructDistancedSequence(int n) {        this.n = n;        this.solutions = new ArrayList<>();        this.used = new boolean[n + 1];        this.currentSequence = new int[2 * n - 1];                generateAll(0);                // This part is inefficient as it requires finding all solutions first.        if (solutions.isEmpty()) return new int[0];         int[] largest = solutions.get(0);        for (int i = 1; i < solutions.size(); i++) {            if (isLexicographicallyLarger(solutions.get(i), largest)) {                largest = solutions.get(i);            }        }        return largest;    }     private void generateAll(int index) {        if (index == currentSequence.length) {            solutions.add(Arrays.copyOf(currentSequence, currentSequence.length));            return;        }         if (currentSequence[index] != 0) {            generateAll(index + 1);            return;        }         // Iterate through numbers in an arbitrary order (e.g., 1 to n)        for (int i = 1; i <= n; i++) {            if (used[i]) continue;             currentSequence[index] = i;            used[i] = true;             if (i == 1) {                generateAll(index + 1);            } else {                int secondPos = index + i;                if (secondPos < currentSequence.length && currentSequence[secondPos] == 0) {                    currentSequence[secondPos] = i;                    generateAll(index + 1);                    currentSequence[secondPos] = 0; // Backtrack                }            }                        currentSequence[index] = 0; // Backtrack            used[i] = false;        }    }        private boolean isLexicographicallyLarger(int[] a, int[] b) {        for (int i = 0; i < a.length; i++) {            if (a[i] > b[i]) return true;            if (a[i] < b[i]) return false;        }        return false;    }}

Complexity

Time

O(S * n * n!), where S is the number of valid sequences. The algorithm explores a very large search space to find all solutions, making it very slow for larger `n`.

Space

O(S * n), where S is the number of valid sequences. This is because we need to store all S solutions, each of length `2n - 1`.

Trade-offs

Pros

  • It is a conceptually simple application of backtracking that guarantees finding the correct answer.

Cons

  • Extremely inefficient in terms of time complexity as it explores the entire search space for all possible valid sequences.

  • Requires a large amount of memory to store all the generated sequences, leading to poor space complexity.

Solutions

class Solution {private  int[] path;private  int[] cnt;private  int n;public  int[] constructDistancedSequence(int n) {    this.n = n;    path = new int[n * 2];    cnt = new int[n * 2];    Arrays.fill(cnt, 2);    cnt[1] = 1;    dfs(1);    int[] ans = new int[n * 2 - 1];    for (int i = 0; i < ans.length; ++i) {      ans[i] = path[i + 1];    }    return ans;  }private  boolean dfs(int u) {    if (u == n * 2) {      return true;    }    if (path[u] > 0) {      return dfs(u + 1);    }    for (int i = n; i > 1; --i) {      if (cnt[i] > 0 && u + i < n * 2 && path[u + i] == 0) {        cnt[i] = 0;        path[u] = i;        path[u + i] = i;        if (dfs(u + 1)) {          return true;        }        cnt[i] = 2;        path[u] = 0;        path[u + i] = 0;      }    }    if (cnt[1] > 0) {      path[u] = 1;      cnt[1] = 0;      if (dfs(u + 1)) {        return true;      }      cnt[1] = 1;      path[u] = 0;    }    return false;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem