Construct the Lexicographically Largest Valid Sequence

medium backtracking pruning

Problem

Given an integer n, build a sequence of length 2n − 1 in which the number 1 appears exactly once and every value i from 2 to n appears exactly twice, with the extra rule that the two copies of each i must sit exactly i indices apart. A valid arrangement always exists for 1 ≤ n ≤ 20; among all of them, return the lexicographically largest sequence.

The winning strategy is greedy backtracking: fill the leftmost empty slot with the biggest unused number whose mirror slot (i positions to the right) is still free, and undo the choice whenever the search gets stuck further on.

Inputn = 5

Output[5, 3, 1, 4, 3, 5, 2, 4, 2]

The two 5s are 5 apart (indices 0 and 5), the 3s are 3 apart, the 4s 4 apart, the 2s 2 apart, and the single 1 fills the remaining slot — no valid sequence starts with anything bigger.

n (integer, 1 to 6 — sequence length 2n − 1)

def construct_distanced_sequence(n):
    size = 2 * n - 1
    seq = [0] * size
    used = [False] * (n + 1)

    def backtrack(pos):
        if pos == size:
            return True
        if seq[pos] != 0:
            return backtrack(pos + 1)
        for num in range(n, 0, -1):      # largest first
            if used[num]:
                continue
            mirror = pos if num == 1 else pos + num
            if mirror >= size or seq[mirror] != 0:
                continue                 # prune: mirror slot blocked
            seq[pos] = seq[mirror] = num
            used[num] = True
            if backtrack(pos + 1):
                return True              # first full sequence wins
            seq[pos] = seq[mirror] = 0   # undo, try smaller
            used[num] = False
        return False

    backtrack(0)
    return seq

function constructDistancedSequence(n) {
  const size = 2 * n - 1;
  const seq = new Array(size).fill(0);
  const used = new Array(n + 1).fill(false);
  function backtrack(pos) {
    if (pos === size) return true;
    if (seq[pos] !== 0) return backtrack(pos + 1);
    for (let num = n; num >= 1; num--) {   // largest first
      if (used[num]) continue;
      const mirror = num === 1 ? pos : pos + num;
      if (mirror >= size || seq[mirror] !== 0) continue;
      seq[pos] = num; seq[mirror] = num;
      used[num] = true;
      if (backtrack(pos + 1)) return true; // first hit wins
      seq[pos] = 0; seq[mirror] = 0;       // undo, try smaller
      used[num] = false;
    }
    return false;
  }
  backtrack(0);
  return seq;
}

class Solution {
    public int[] constructDistancedSequence(int n) {
        int size = 2 * n - 1;
        int[] seq = new int[size];
        boolean[] used = new boolean[n + 1];
        backtrack(seq, used, 0, n);
        return seq;
    }
    boolean backtrack(int[] seq, boolean[] used, int pos, int n) {
        if (pos == seq.length) return true;
        if (seq[pos] != 0) return backtrack(seq, used, pos + 1, n);
        for (int num = n; num >= 1; num--) {   // largest first
            if (used[num]) continue;
            int mirror = num == 1 ? pos : pos + num;
            if (mirror >= seq.length || seq[mirror] != 0) continue;
            seq[pos] = num; seq[mirror] = num;
            used[num] = true;
            if (backtrack(seq, used, pos + 1, n)) return true;
            seq[pos] = 0; seq[mirror] = 0;     // undo, try smaller
            used[num] = false;
        }
        return false;
    }
}

class Solution {
public:
    vector<int> constructDistancedSequence(int n) {
        int size = 2 * n - 1;
        vector<int> seq(size, 0);
        vector<bool> used(n + 1, false);
        backtrack(seq, used, 0, n);
        return seq;
    }
    bool backtrack(vector<int>& seq, vector<bool>& used, int pos, int n) {
        if (pos == (int)seq.size()) return true;
        if (seq[pos] != 0) return backtrack(seq, used, pos + 1, n);
        for (int num = n; num >= 1; num--) {   // largest first
            if (used[num]) continue;
            int mirror = num == 1 ? pos : pos + num;
            if (mirror >= (int)seq.size() || seq[mirror] != 0) continue;
            seq[pos] = num; seq[mirror] = num;
            used[num] = true;
            if (backtrack(seq, used, pos + 1, n)) return true;
            seq[pos] = 0; seq[mirror] = 0;     // undo, try smaller
            used[num] = false;
        }
        return false;
    }
};

Explanation

The key insight is that "lexicographically largest" turns into a greedy ordering rule: fill positions strictly left to right, and at each empty slot try candidates from n down to 1. Because earlier positions dominate the lexicographic comparison, the first complete sequence the search finds is automatically the largest one — we can stop immediately instead of enumerating every solution.

The pairing rule gives us a powerful pruning check. Placing num > 1 at position pos forces its twin into the mirror slot pos + num. If that slot is past the end of the array or already occupied, the candidate is rejected in O(1) without any recursion. Only 1 is exempt, since it appears once and needs no mirror.

Walk through n = 5 (length 9). Position 0 takes 5 (mirror 5). At position 1, 4 is pruned because slot 5 is taken, so 3 goes in (mirror 4). Position 2 takes 4 (mirror 6) and position 3 takes the lone 1 — but then position 7 has no fitting number: 2 would need slot 9, which does not exist. The search hits a dead end.

Now backtracking earns its keep: the 1 is removed, position 3 is exhausted, and the 4 is pulled back out of positions 2 and 6. Retrying position 2 with smaller numbers, 2 is pruned (slot 4 is taken) and 1 fits. Then 4 lands at 3 and 7, 2 at 6 and 8, and every slot is full: [5, 3, 1, 4, 3, 5, 2, 4, 2].

Why is the first hit provably optimal? Suppose some other valid sequence were larger. At the first index where they differ, the larger sequence would hold a bigger number — but the search tried bigger numbers at that position first and only moved on after they failed to extend to any complete sequence. Contradiction.

The worst-case running time is factorial, O(n!), since each empty slot may branch over all unused numbers, but the mirror-slot pruning cuts the tree so aggressively that for n ≤ 20 the search finishes almost instantly. The recursion depth and the seq/used arrays need only O(n) extra space.

Time: O(n!) Space: O(n)