1718. Construct the Lexicographically Largest Valid Sequence

UnknownView on LeetCode

Array Backtracking

Time: O(n!)

Space: O(n)

Intuition

Build lex-smallest valid array where adjacent difference is either 1 or equals the element. Backtracking with pruning.

Algorithm

1DFS: fill n positions. At each position i: try values from 1 upward. Check conditions: |arr[i]-arr[i-1]|==1 or divisible.
2Use a set to track used values.

Common Pitfalls

•Try smallest values first for lex-smallest. Backtrack when stuck.

1718.cs

// Approach: DFS backtracking with bitmask; place largest unused number first at valid positions.
// Time: O(n!) Space: O(n)

public class Solution
{
    public int[] ConstructDistancedSequence(int n)
    {
        var ans = new int[2 * n - 1];
        Dfs(n, 0, 0, ans);
        return ans;
    }

    private bool Dfs(int n, int i, int mask, int[] ans)
    {
        if (i == ans.Length)
            return true;
        if (ans[i] > 0)
            return Dfs(n, i + 1, mask, ans);

        // Greedily fill in `ans` in descending order.
        for (int num = n; num >= 1; --num)
        {
            if ((mask >> num & 1) != 0)
                continue;
            if (num == 1)
            {
                ans[i] = num;
                if (Dfs(n, i + 1, mask | (1 << num), ans))
                    return true;
                ans[i] = 0;
            }
            else
            {  // num in [2, n]
                if (i + num >= ans.Length || ans[i + num] > 0)
                    continue;
                ans[i] = num;
                ans[i + num] = num;
                if (Dfs(n, i + 1, mask | (1 << num), ans))
                    return true;
                ans[i + num] = 0;
                ans[i] = 0;
            }
        }

        return false;
    }
}

Was this solution helpful?