Construct the Lexicographically Largest Valid Sequence

The constraints are practically asking for brute-force. You do not need to find any special tricks; there is no way you TLE.

Since, we are trying to find the lexicographically largest answer, realise that for each index, if we start checking every value from n to 1, the first answer we return will naturally be the lexicographically largest answer.

code

class Solution {
private:
    bool recursion (int index, int n, vector<int>& current, vector<int>& used) {
        if (index == current.size()) {
            return true;
        }
        if (current[index] != 0) {
            return recursion(index+1, n, current, used);
        }
        for (int i = n; i >= 1; --i) {
            if (used[i] == 1) continue;

            current[index] = i;
            used[i] = 1;

            if (i == 1) {
                if (recursion(index+1, n, current, used)) {
                    return true;
                }
            } else if (index+i < 2*n-1 && current[index+i] == 0) {
                current[index+i] = i;

                if (recursion(index+1, n, current, used)) {
                    return true;
                }

                current[index+i] = 0;
            }

            current[index] = 0;
            used[i] = 0;
        }
        return false;
    }
public:
    vector<int> constructDistancedSequence(int n) {
        vector<int> current (2*n-1, 0);
        vector<int> used (n+1, 0);

        recursion(0, n, current, used);
        return current;
    }
};

complexity

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

learnings

• brother, look at the restraints before you attempt the question; a lot of the times the questions do not have a special trick or O(n) solution

Time taken:

• too long... (60+ minutes)
  • made the mistake of investing too much time into an O(n) solution that does not work