Leetcode Problem 1718. Construct the Lexicographically Largest Valid Sequence

1718. Construct the Lexicographically Largest Valid Sequence

Leetcode Solutions

Backtracking to Construct Lexicographically Largest Sequence

  1. Initialize an array ans of size 2*n - 1 with zeros, and a set unseen with numbers from 1 to n.
  2. Define a recursive function backtrack(idx1) that will attempt to fill the ans array starting from index idx1.
  3. If unseen is empty, we have successfully filled the sequence, so return True.
  4. If ans[idx1] is not zero, move to the next index by calling backtrack(idx1 + 1).
  5. Iterate over the numbers in unseen in reverse order (from n to 1) to ensure lexicographical order.
  6. For each number num, calculate its pair index idx2 as idx1 + num (if num is not 1).
  7. If num is in unseen, idx2 is within bounds, and ans[idx2] is zero, place num at both idx1 and idx2.
  8. Remove num from unseen and recursively call backtrack(idx1 + 1).
  9. If the recursive call returns True, the sequence is valid, so return True.
  10. If the recursive call returns False, backtrack by resetting ans[idx1] and ans[idx2] to zero and adding num back to unseen.
  11. If no number can be placed, return False to indicate failure.
UML Thumbnail

Greedy and Backtracking for Constructing Sequence

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...