LeetCode 3644 - Maximum K to Sort a Permutation

The problem provides a permutation array nums of length n, meaning it contains each integer from 0 to n-1 exactly once, in some arbitrary order.

leetcodemediumarraybit-manipulation

LeetCode Problem 3644

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation

Solution

Problem Understanding

The problem provides a permutation array nums of length n, meaning it contains each integer from 0 to n-1 exactly once, in some arbitrary order. The task is to determine the maximum value of k such that the array can be sorted in non-decreasing order using only swaps where the bitwise AND of the two numbers being swapped equals k. In other words, you can swap nums[i] and nums[j] only if nums[i] & nums[j] == k.

The expected output is a single integer k, representing the largest value that allows the permutation to be fully sorted. If the array is already sorted, the problem specifies that the output should be 0.

The constraints tell us that n can be up to 10^5, which rules out naive solutions that consider all possible swaps directly, since that would involve O(n²) operations. The values in nums range from 0 to n-1, which ensures no duplicates and guarantees that nums is a proper permutation. This is crucial because it allows us to reason about positions and cycles in the permutation.

Edge cases include arrays that are already sorted, arrays in reverse order, arrays where swaps are possible only with k = 0, and arrays with small n (like 1 or 2) where trivial swaps may occur.

Approaches

Brute-Force Approach

A brute-force approach would be to check every possible k from n-1 down to 0, simulate all possible swaps that satisfy nums[i] & nums[j] == k, and see if the array can be sorted. This would involve repeatedly performing swaps or building a graph of possible swaps for each candidate k and checking reachability. While correct, this method is far too slow because for each k you might need to perform O(n²) operations to explore all swap possibilities, leading to a worst-case complexity of O(n² log n) or worse.

Optimal Approach

The key insight is to recognize that the allowed swaps form connected components in a graph where each node is a number and an edge exists between numbers a and b if a & b == k. Within each connected component, any permutation of its nodes can be sorted using swaps. Therefore, the array is sortable for a particular k if every cycle in the permutation is fully contained within one connected component defined by k.

To find the maximum k, we can perform bitmasking from the highest bit downwards. Starting from the most significant bit, we attempt to include it in k and check if the permutation is still sortable under this candidate k. If it is, we keep that bit; otherwise, we discard it. This is effectively a greedy approach using bitwise search, which runs in O(n log n) because we check each bit individually and only need a linear pass through the array per bit.

Approach Time Complexity Space Complexity Notes
Brute Force O(n² * log n) O(n²) Test every k and simulate swaps
Optimal O(n * log n) O(n) Use bitmasking and connected components

Algorithm Walkthrough

  1. Initialize k = 0. This will hold the maximum k as we construct it bit by bit.
  2. Iterate through the bits of numbers from the most significant bit down to the least significant bit. For 32-bit integers, consider bits 31 down to 0.
  3. For each bit, attempt to set it in k (candidate = k | (1 << bit)).
  4. Check if the permutation is sortable using only swaps where nums[i] & nums[j] has all the bits set in candidate. To do this efficiently:

a. Build connected components where two numbers belong to the same component if (nums[i] & candidate) == (nums[j] & candidate).

b. For each cycle in the permutation, ensure all elements belong to the same connected component. 5. If sortable, update k = candidate; otherwise, leave the bit unset. 6. After iterating through all bits, return k.

Why it works:

By iteratively trying to include each bit starting from the highest, we greedily maximize k while ensuring that sorting is possible. The connected component check guarantees that any cycle of misplaced numbers can be resolved within allowed swaps. This approach leverages the structure of permutations and the properties of bitwise AND to efficiently determine the maximum feasible k.

Python Solution

from typing import List

class Solution:
    def sortPermutation(self, nums: List[int]) -> int:
        n = len(nums)
        k = 0

        # Iterate from the highest bit to lowest
        for bit in reversed(range(n.bit_length() + 1)):
            candidate = k | (1 << bit)

            # Build components based on candidate
            parent = list(range(n))
            
            def find(x):
                while parent[x] != x:
                    parent[x] = parent[parent[x]]
                    x = parent[x]
                return x
            
            def union(x, y):
                px, py = find(x), find(y)
                if px != py:
                    parent[px] = py

            for i in range(n):
                for j in range(i+1, n):
                    if (nums[i] & candidate) == (nums[j] & candidate):
                        union(i, j)

            sortable = True
            for i in range(n):
                if find(i) != find(nums.index(i)):
                    sortable = False
                    break

            if sortable:
                k = candidate

        return k

Implementation walkthrough:

We iterate over bits from high to low and tentatively add them to k. For each candidate k, we construct connected components using a union-find structure. Elements in the same component can be swapped according to the bitwise AND rule. We then check that each number i can reach its target index nums.index(i) within its component. If all cycles are contained in components, the candidate k is valid.

Go Solution

func sortPermutation(nums []int) int {
    n := len(nums)
    k := 0

    for bit := 31; bit >= 0; bit-- {
        candidate := k | (1 << bit)
        parent := make([]int, n)
        for i := 0; i < n; i++ {
            parent[i] = i
        }

        var find func(int) int
        find = func(x int) int {
            if parent[x] != x {
                parent[x] = find(parent[x])
            }
            return parent[x]
        }

        union := func(x, y int) {
            px, py := find(x), find(y)
            if px != py {
                parent[px] = py
            }
        }

        for i := 0; i < n; i++ {
            for j := i + 1; j < n; j++ {
                if (nums[i] & candidate) == (nums[j] & candidate) {
                    union(i, j)
                }
            }
        }

        sortable := true
        indexMap := make([]int, n)
        for i, val := range nums {
            indexMap[val] = i
        }

        for i := 0; i < n; i++ {
            if find(i) != find(indexMap[i]) {
                sortable = false
                break
            }
        }

        if sortable {
            k = candidate
        }
    }

    return k
}

Go-specific notes:

Union-find is implemented recursively with path compression. The index map avoids repeated calls to index() like in Python. Bit iteration is hard-coded for 32 bits.

Worked Examples

Example 1: nums = [0,3,2,1]

Step Candidate k Connected Components Sortable? Updated k
bit 2 4 [0],[1],[2],[3] No 0
bit 1 2 [0],[1,3],[2] No 0
bit 0 1 [0],[1,3],[2] Yes 1

Output: 1

Example 2: nums = [0,1,3,2]

Step Candidate k Connected Components Sortable? Updated k
bit 2 4 [0],[1],[2],[3] No 0
bit 1 2 [0],[1],[2,3] Yes 2
bit 0 3 ... No 2

Output: 2

Example 3: nums = [3,2,1,0]

Step Candidate k Sortable? Updated k
... ... Only k=0 works 0

Output: 0

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Iterate over log n bits, for each we may need O(n) union-find operations
Space O(n) Union-find parent array, plus index maps

The union-find operations are almost