Maximum K to Sort a Permutation

Maximum K to Sort a Permutation

What is this problem about?

The Maximum K to Sort a Permutation coding problem gives you a permutation of integers from 1 to n and asks for the largest value K such that if you look at the last K elements of the array, they form a sorted (ascending) suffix. In other words, find the longest already-sorted suffix in the permutation. This is about identifying the boundary where the "sorted" region of the permutation begins from the right.

Why is this asked in interviews?

Amazon includes this problem to test understanding of permutation structure and suffix scanning. It's deceptively simple but requires careful reasoning about what "already in place" means for a permutation. Candidates who understand that the sorted suffix of a permutation [1..n] must consist of exactly the elements n, n-1, ..., n-k+1 can solve this in O(n) with a single right-to-left scan. Others might overcomplicate it.

Algorithmic pattern used

The solution uses a single right-to-left linear scan combined with bit tracking. Scan from right to left. Maintain the current minimum value seen so far from the right. The sorted suffix consists of elements where each element equals the count of elements seen so far from the right AND no element larger than the current has appeared out of order to the left. More precisely: the suffix is sorted iff it consists of {n, n-1, ..., n-k+1} in that order. Scan right-to-left and verify this property.

Example explanation

Permutation: [3, 1, 2, 5, 4], n = 5.

• From right: 4 at index 4. Expected: 5. 4 ≠ 5. Not sorted starting here.
• 5 at index 3, 4 at index 4: [5, 4] — not ascending. K for sorted suffix of length 2 fails.
• Actually, the sorted (ascending) suffix: check from right, [4] is sorted (trivially). [5, 4] is descending — not sorted. So K = 1.

Permutation: [1, 2, 3, 4, 5]:

• Entire array is sorted. K = 5.

Permutation: [2, 1, 3, 4, 5]:

• [5] ✓, [4,5] ✓, [3,4,5] ✓, [1,3,4,5] — not sorted (1 < 3 but we check the suffix starting at index 1). K = 3.

Common mistakes candidates make

• Comparing only adjacent pairs: Checking nums[i] < nums[i+1] catches local issues but misses globally correct suffix structure.
• Using the wrong definition of "sorted": The sorted suffix must be ascending — not descending or partially ordered.
• Off-by-one in K vs index: K is a count (length), not an index. Confusing the two leads to wrong answers.

Interview preparation tip

For the Array Bit Manipulation interview pattern in this context, recognize that permutations have structure you can exploit. The maximum already-sorted suffix is found with a single backward scan checking the ascending condition. Always clarify "sorted ascending or descending" in interviews — this problem's answer can differ drastically based on that assumption.