Skip to main content
Talentd

Maximum K to Sort a Permutation - Solution & Explanation

MediumArrayBit Manipulation4 min readAsked at: Amazon
Practice this problem

Problem Statement

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.

Approach Overview

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.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Swap Simulation with Constraint ChecksO(n^2)O(1)Understanding the mechanics of the swap rule or testing small inputs
Bitwise Constraint AggregationO(n)O(1)General case; optimal interview solution using bit masks

Video Solution

Maximum K to Sort a Permutation | Leetcode 3644 • Techdose • 1,505 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum K to Sort a Permutation easy or hard?
Maximum K to Sort a Permutation is generally considered a medium-level problem. The implementation is simple once the bitwise constraint observation is made, but identifying that all swap constraints can be combined into a single global mask requires insight.
Maximum K to Sort a Permutation Python/Java solution
Implement the algorithm by iterating through the permutation and maintaining a running bitwise AND of (i & p[i]). The logic is identical across Python, Java, C++, Go, and TypeScript since it relies only on primitive integer operations.
How to solve Maximum K to Sort a Permutation in O(n)?
Iterate through the permutation and compute the bitwise intersection mask (i & p[i]) for each index. Maintain a running AND of these masks across all elements. This aggregated value keeps only the bits valid for every required index movement, giving the maximum possible k in a single pass.
What is the best approach for Maximum K to Sort a Permutation?
The optimal approach aggregates bitwise constraints from each index mapping. For every position i, compute (i & p[i]) and take the bitwise AND across all positions. The resulting mask represents the largest valid k that satisfies the swap constraint for the entire permutation. This runs in O(n) time with O(1) extra space.
Is Maximum K to Sort a Permutation asked at Google/Amazon/Meta?
Permutation and bit manipulation problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that combine permutation properties with bit masks or swap constraints are common in system-level and algorithmic interview rounds.
What data structure is used in Maximum K to Sort a Permutation?
The solution primarily uses an array to represent the permutation and relies on bit manipulation operations such as AND. No additional complex data structures are required.
What is the time complexity of Maximum K to Sort a Permutation?
The optimal solution runs in O(n) time because it scans the permutation once and performs constant-time bitwise operations per element. Space complexity is O(1) since only a few integer variables are maintained.

Ready to solve this problem?

Practice Maximum K to Sort a Permutation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays