Problem Description

You have an integer array nums of length n that contains a permutation of all numbers from 0 to n-1 (each number appears exactly once).

You can perform swap operations on this array, but with a specific constraint: you can only swap elements at positions i and j if nums[i] AND nums[j] == k, where AND is the bitwise AND operation and k is a non-negative integer that you choose.

Your goal is to find the maximum possible value of k such that using this value, you can sort the array into non-decreasing order (ascending order) through any number of valid swaps.

If the array is already sorted, return 0.

For example:

• If you choose k = 2, you can only swap elements where their bitwise AND equals 2
• Elements like 6 (binary: 110) and 3 (binary: 011) have 6 AND 3 = 2, so they could be swapped if k = 2
• You need to find the largest k value that still allows you to completely sort the array

The solution works by checking which elements are not in their correct positions (where element x should be at index x). For all misplaced elements, it performs a bitwise AND operation on all of them. This gives the maximum k that allows necessary swaps to sort the array, since any bit that's 1 in the result must be 1 in all misplaced elements, ensuring they can all participate in swaps with each other or with correctly placed elements sharing those bits.

Intuition

To understand why we need to find the bitwise AND of all misplaced elements, let's think about what swaps are necessary to sort the array.

Since nums is a permutation of [0, 1, 2, ..., n-1], the sorted array should have each element i at position i. Any element that's not at its correct position needs to be moved through swaps.

The key insight is that for a given k, elements can only be swapped if their bitwise AND equals k. This creates "swap groups" - elements that can potentially exchange positions with each other. For the array to be sortable:

• All misplaced elements must be able to participate in swaps (either directly or indirectly through a chain of swaps)
• The value k must be present as a common pattern in the binary representation of all misplaced elements

Consider what happens at the bit level: if k has a bit set to 1 at position p, then for two numbers to have AND = k, both numbers must have bit 1 at position p. This means any bit that's 1 in k must be 1 in all numbers we need to swap.

Therefore, the maximum k is the bitwise AND of all misplaced elements. This ensures:

1. Every misplaced element has all the bits of k set to 1, so they can potentially participate in swaps
2. We're using the largest possible k that satisfies this condition
3. Elements already in correct positions don't restrict our choice of k since they don't need to be moved

If all elements are already in place, no swaps are needed, so we return 0. The solution elegantly handles this by initializing ans = -1 (all bits set to 1), and the AND operation naturally gives 0 or positive when needed through max(ans, 0).

Solution Approach

The implementation follows a straightforward approach to find the maximum k:

1. Initialize the answer: Start with ans = -1. In binary, -1 is represented as all bits set to 1 (due to two's complement representation). This serves as our starting point for the bitwise AND operation.

2. Iterate through the array: For each element at index i, check if it's in its correct position:

   for i, x in enumerate(nums):
       if i != x:

   • If element x is at index i and i != x, then this element is misplaced
   • In a sorted permutation of [0, 1, ..., n-1], element x should be at index x

3. Accumulate the bitwise AND: For each misplaced element, perform bitwise AND with the current answer:

   ans &= x

   • This operation keeps only the bits that are 1 in both ans and x
   • After processing all misplaced elements, ans will contain only the bits that are 1 in ALL misplaced elements
   • This gives us the maximum k where all misplaced elements satisfy the condition that their AND with other elements can equal k

4. Handle the edge case: Return the maximum of ans and 0:

   return max(ans, 0)

   • If the array is already sorted (no misplaced elements), ans remains -1, so we return 0
   • Otherwise, we return the computed bitwise AND value

The algorithm runs in O(n) time with O(1) extra space, making it highly efficient. The beauty of this solution lies in recognizing that the constraint on swaps translates directly to a bitwise AND operation on all elements that need to be moved.

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

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

Step 1: Identify misplaced elements

First, let's check which elements are not in their correct positions:

• Index 0: has value 3 (should be 0) → misplaced
• Index 1: has value 0 (should be 1) → misplaced
• Index 2: has value 1 (should be 2) → misplaced
• Index 3: has value 2 (should be 3) → misplaced
• Index 4: has value 5 (should be 4) → misplaced
• Index 5: has value 4 (should be 5) → misplaced

All elements are misplaced! The misplaced values are: 3, 0, 1, 2, 5, 4

Step 2: Calculate bitwise AND of misplaced elements

Let's convert to binary and perform the AND operation:

3 = 011
0 = 000
1 = 001
2 = 010
5 = 101
4 = 100

Starting with ans = -1 (all bits set to 1):

• ans = -1 & 3 = 3 (binary: 011)
• ans = 3 & 0 = 0 (binary: 000)
• Since we get 0, all subsequent AND operations will remain 0

Step 3: Return result

The maximum k value is 0.

Verification: With k = 0, we can swap any two elements whose AND equals 0. Let's check some pairs:

• 3 & 0 = 0 ✓ (can swap)
• 1 & 2 = 0 ✓ (can swap)
• 5 & 2 = 0 ✓ (can swap)
• 4 & 3 = 0 ✓ (can swap)

This allows enough flexibility to sort the array through a series of swaps.

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

• Index 0: has value 2 (should be 0) → misplaced
• Index 1: has value 0 (should be 1) → misplaced
• Index 2: has value 1 (should be 2) → misplaced
• Index 3: has value 3 (should be 3) → correct!

Misplaced values: 2, 0, 1

Binary representation:

2 = 10
0 = 00
1 = 01

Bitwise AND: 2 & 0 & 1 = 0

So the maximum k is 0, which allows swaps between elements with AND = 0, enabling us to sort the array.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input list nums. The algorithm iterates through the list exactly once using enumerate(), performing constant-time operations (comparison and bitwise AND) for each element.

Space Complexity: O(1). The algorithm only uses a fixed amount of extra space for variables ans, i, and x, regardless of the input size. The space used does not grow with the size of the input list.

Common Pitfalls

1. Misunderstanding the Initial Value of -1

Pitfall: Developers might incorrectly initialize ans with 0 or float('inf') instead of -1, thinking they need to start with a neutral or maximum value.

Why it's wrong:

• Starting with 0 would immediately make any bitwise AND operation result in 0, losing all information
• Starting with float('inf') doesn't work with bitwise operations
• -1 in binary is all 1s (e.g., 11111111...), which is the identity element for bitwise AND when finding common bits

Correct approach:

ans = -1  # All bits set to 1, perfect for finding common bits via AND

2. Forgetting to Handle the Already-Sorted Case

Pitfall: Returning ans directly without checking if it's still -1:

# Wrong implementation
def sortPermutation(self, nums: List[int]) -> int:
    ans = -1
    for i, x in enumerate(nums):
        if i != x:
            ans &= x
    return ans  # Would return -1 for sorted arrays!

Why it's wrong: If the array is already sorted, no elements are misplaced, so ans remains -1. The problem states we should return 0 for already-sorted arrays.

Correct approach:

return max(ans, 0)  # Ensures we return 0 instead of -1 for sorted arrays

3. Incorrectly Identifying Misplaced Elements

Pitfall: Using wrong comparison logic like nums[i] != i+1 (1-indexed thinking) or nums[i] != nums[x]:

# Wrong: assuming 1-indexed positions
if x != i + 1:
    ans &= x

# Wrong: comparing with value at position x
if nums[i] != nums[x]:
    ans &= x

Why it's wrong: The problem describes a permutation of [0, 1, ..., n-1], where element x should be at index x in the sorted array.

Correct approach:

if i != x:  # Element x at position i is misplaced if i ≠ x
    ans &= x

4. Misunderstanding What Value to AND

Pitfall: Performing AND with the index instead of the value:

# Wrong implementation
for i, x in enumerate(nums):
    if i != x:
        ans &= i  # Should be x, not i!

Why it's wrong: We need to find common bits among the VALUES that need to be swapped, not their current positions. The swap condition is based on nums[i] AND nums[j] == k, involving the actual values.

Correct approach:

ans &= x  # AND with the misplaced value, not its index