3644. Maximum K to Sort a Permutation

Time: O(n)

Space: O(1)

Problem Overview

You may swap two values only when their bitwise AND equals k, and the goal is the largest k that can still sort the permutation.

Intuition

You may swap two values only when their bitwise AND equals k, and the goal is the largest k that can still sort the permutation. A value already sitting at its own index never has to move, so it does not restrict k. Every value that is out of place must be able to swap with the others that are out of place, which means every bit set in k has to be set in all of those values. The largest mask with that property is their bitwise AND. If nothing is out of place, no swap is required and the answer is 0.

Algorithm

1Start the running AND at all ones, which in two's complement is -1.
2For each index i, skip nums[i] when it already equals i.
3Otherwise AND nums[i] into the running value.
4If that value becomes 0, return 0 immediately. Later values cannot turn a 0 bit back on.
5If the scan finishes without a misplaced value, return 0. Otherwise return the running AND.

Example Walkthrough

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

1.Index 0 holds 0 and index 2 holds 2, so both are already home.
2.The misplaced values are 3 and 1.
3.3 AND 1 is 1, and swapping those two values sorts the array.

Output: 1

Common Pitfalls

•AND the misplaced values, not the indices and not the values that are already correct.
•A sorted permutation must return 0. Leaving the initial all-ones mask in place would be wrong.
•Once the running AND is 0, the answer is fixed. The rest of the array cannot raise it.
•k has to work for every required swap. Using the AND of only one pair can be too large.

3644.cs

// Approach: A swap is allowed only when the two values AND to k, so every bit
// of k must be set in every value that is not already at its own index. The
// largest such k is the AND of those misplaced values. AND with 0 stays 0, so
// the scan stops as soon as the running AND becomes 0. A sorted permutation
// has no misplaced value and returns 0.
// Time: O(n) Space: O(1)

public class Solution
{
    public int SortPermutation(int[] nums)
    {
        int result = -1;
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] == i)
                continue;
            result &= nums[i];
            if (result == 0)
                return 0;
        }
        return result == -1 ? 0 : result;
    }
}

Was this solution helpful?