Skip to content

3644. Maximum K to Sort a Permutation

SourceWeekly Contest 462 Q2DifficultyMediumRating1775

Description

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 <= 105
  • 0 <= nums[i] <= n - 1
  • nums is a permutation of integers from 0 to n - 1.

Solutions

Solution 1: Bit Manipulation

Thinking

The direct approach tries \(k\) from large to small and asks whether the misplaced values can be sorted using only swaps whose bitwise AND equals \(k\). With \(n \le 10^5\), any pair of values may be swapped, so building that graph is quadratic and enumeration does not fit.

What must move is each value that is not stored at its own index. Such a value takes part in at least one swap, so every bit set in \(k\) has to be set in that value as well. A feasible \(k\) therefore cannot exceed the bitwise AND of all misplaced values.

Call that AND \(k\) again. The number \(k\) itself belongs to the permutation of \([0,n)\), and its AND with every misplaced value is exactly \(k\), so it can be used as a hub to arrange those values in any order. An array that is already sorted needs no swap, and the answer is \(0\).

The identity element of AND is all-ones, so \(\textit{ans}\) starts at \(-1\) and only combines entries with \(\textit{nums}[i] \ne i\). When the permutation is sorted, \(\textit{ans}\) stays \(-1\), and \(\max(\textit{ans}, 0)\) turns that sentinel into \(0\).

We maintain \(\textit{ans}\) as the bitwise AND of every element that is not in its home position, starting from \(-1\).

Scan each index \(i\). If \(\textit{nums}[i] \ne i\), fold \(\textit{nums}[i]\) into \(\textit{ans}\) with a bitwise AND.

When the scan finishes, \(\textit{ans}\) is still \(-1\) if the array is already sorted, in which case the result is \(0\). Otherwise \(\textit{ans}\) is the largest feasible \(k\). Return \(\max(\textit{ans}, 0)\).

The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of \(\textit{nums}\).

1
2
3
4
5
6
7
class Solution:
    def sortPermutation(self, nums: list[int]) -> int:
        ans = -1
        for i, x in enumerate(nums):
            if i != x:
                ans &= x
        return max(ans, 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int sortPermutation(int[] nums) {
        int ans = -1;
        for (int i = 0; i < nums.length; ++i) {
            if (i != nums[i]) {
                ans &= nums[i];
            }
        }
        return Math.max(ans, 0);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int sortPermutation(vector<int>& nums) {
        int ans = -1;
        for (int i = 0; i < nums.size(); ++i) {
            if (i != nums[i]) {
                ans &= nums[i];
            }
        }
        return max(ans, 0);
    }
};
1
2
3
4
5
6
7
8
9
func sortPermutation(nums []int) int {
    ans := -1
    for i, x := range nums {
        if i != x {
            ans &= x
        }
    }
    return max(ans, 0)
}
1
2
3
4
5
6
7
8
9
function sortPermutation(nums: number[]): number {
    let ans = -1;
    for (let i = 0; i < nums.length; ++i) {
        if (i != nums[i]) {
            ans &= nums[i];
        }
    }
    return Math.max(ans, 0);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
impl Solution {
    pub fn sort_permutation(nums: Vec<i32>) -> i32 {
        let mut ans = -1;
        for (i, &x) in nums.iter().enumerate() {
            if i as i32 != x {
                ans &= x;
            }
        }
        ans.max(0)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public class Solution {
    public int SortPermutation(int[] nums) {
        int ans = -1;
        for (int i = 0; i < nums.Length; i++) {
            if (i != nums[i]) {
                ans &= nums[i];
            }
        }
        return Math.Max(ans, 0);
    }
}

Comments