Watch 10 video solutions for Maximum K to Sort a Permutation, a medium level problem involving Array, Bit Manipulation. This walkthrough by Techdose has 1,457 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums of length n, where nums is a permutation of the numbers in the range [0..n - 1].
You may swap elements at indices i and j only if nums[i] AND nums[j] == k, where AND denotes the bitwise AND operation and k is a non-negative integer.
Return the maximum value of k such that the array can be sorted in non-decreasing order using any number of such swaps. If nums is already sorted, return 0.
Example 1:
Input: nums = [0,3,2,1]
Output: 1
Explanation:
Choose k = 1. Swapping nums[1] = 3 and nums[3] = 1 is allowed since nums[1] AND nums[3] == 1, resulting in a sorted permutation: [0, 1, 2, 3].
Example 2:
Input: nums = [0,1,3,2]
Output: 2
Explanation:
Choose k = 2. Swapping nums[2] = 3 and nums[3] = 2 is allowed since nums[2] AND nums[3] == 2, resulting in a sorted permutation: [0, 1, 2, 3].
Example 3:
Input: nums = [3,2,1,0]
Output: 0
Explanation:
Only k = 0 allows sorting since no greater k allows the required swaps where nums[i] AND nums[j] == k.
Constraints:
1 <= n == nums.length <= 1050 <= nums[i] <= n - 1nums is a permutation of integers from 0 to n - 1.Problem Overview: You are given a permutation of indices and must determine the maximum integer k such that the permutation can be rearranged into sorted order while respecting a bitwise constraint between indices involved in swaps.
Approach 1: Simulation with Swap Constraints (Brute Force) (Time: O(n^2), Space: O(1))
A direct way to reason about the problem is to simulate swaps while checking whether the constraint involving k is satisfied for the pair of indices. For each candidate value of k, iterate over all index pairs and attempt to move each element to its correct position. The permutation can only be fixed if every required swap satisfies the bitwise rule. This approach quickly becomes expensive because every misplaced element may require scanning many indices. It works for very small inputs but is not practical for interview‑scale constraints.
Approach 2: Bitwise Constraint Aggregation (Optimal) (Time: O(n), Space: O(1))
The key observation is that each element in a permutation must eventually move from index i to index p[i]. For the swap constraint to allow that movement, the chosen k must be compatible with both indices. In bit terms, every bit set in k must also be present in both indices participating in the swap. That means k must be a subset of the bitwise intersection of those indices.
For each position i, compute the mask (i & p[i]). This mask represents the bits that both indices share and therefore the bits that could safely appear in k. Since the same k must work for the entire permutation, take the bitwise AND across all these masks. The result keeps only the bits valid for every pair of indices involved in the permutation mapping.
This aggregated mask is the maximum valid k. The algorithm performs a single pass through the array and uses constant additional memory. The reasoning relies heavily on properties of bit manipulation and permutation index relationships in an array. The permutation guarantee ensures each value appears exactly once, so each mapping contributes one constraint.
Recommended for interviews: The bitwise aggregation approach is what interviewers expect. A brute-force swap simulation demonstrates understanding of the constraint but fails to scale. Recognizing that every element movement imposes a bitmask restriction—and combining those restrictions with a global AND—shows strong problem-solving skills with bit manipulation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Swap Simulation with Constraint Checks | O(n^2) | O(1) | Understanding the mechanics of the swap rule or testing small inputs |
| Bitwise Constraint Aggregation | O(n) | O(1) | General case; optimal interview solution using bit masks |