Sort in Linear Time an Array Where At Most One Element Was Moved Out of Place

An array was sorted in non-decreasing order, and then at most one of its elements was taken out and reinserted at a different position. Given the resulting array, return it sorted in non-decreasing order.

The interviewer asked for an O(n) time solution, so do not sort from scratch.

Function Signature

def fix_almost_sorted(nums: list[int]) -> list[int]:

Rules

• The input is guaranteed to be either already sorted, or obtainable from a sorted array by moving exactly one element to another position.
• The moved element may have moved toward the front or toward the back, by any distance.
• Values may repeat.
• Return the sorted array. You may rearrange nums in place and return it.
• Target O(n) time and O(1) extra space beyond the returned list.

Constraints

• 1 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9

Examples

Example 1

Input:  nums = [1, 2, 9, 3, 4, 5]
Output: [1, 2, 3, 4, 5, 9]

The 9 was moved from the end to index 2.

Example 2

Input:  nums = [3, 5, 7, 1, 9]
Output: [1, 3, 5, 7, 9]

The 1 was moved from the front to index 3.

Example 3

Input:  nums = [1, 1, 2]
Output: [1, 1, 2]

The array is already sorted.

Re-sort an Array With One Displaced Element

An integer array was sorted in non-decreasing order, and then at most one of its elements was taken out and reinserted at a different position. Given the resulting array nums, return it sorted in non-decreasing order.

The input is guaranteed to be either already sorted, or obtainable from a sorted (non-decreasing) array by moving exactly one element to another position. The moved element may have moved toward the front or toward the back, by any distance. Values may repeat. You may rearrange nums in place and return it.

The interviewer asked for an O(n) time solution, so do not sort from scratch: target O(n) time and O(1) extra space beyond the returned array.

The returned array must contain exactly the elements of nums, with multiplicity, in non-decreasing order; this arrangement is unique. Every value satisfies |nums[i]| <= 10^9, so no value exceeds 2^31 - 1 and 32-bit integers suffice in every language.

Example 1

Input: nums = [1, 2, 9, 3, 4, 5]
Output: [1, 2, 3, 4, 5, 9]

Explanation: the 9 was moved from the end to index 2.

Example 2

Input: nums = [3, 5, 7, 1, 9]
Output: [1, 3, 5, 7, 9]

Explanation: the 1 was moved from the front to index 3.

Constraints

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums is either already sorted in non-decreasing order, or obtainable from a non-decreasing array by moving exactly one element to a different position (toward the front or the back, by any distance).
• Values may repeat.

Hints

1. If you removed the one displaced element, the remaining elements would already be in non-decreasing order.
2. The displaced element may have moved toward the front or toward the back, by any distance, so consider both directions.
3. Values may repeat, so check how your comparisons treat equal neighbors.

Approach

Scan from the left for the first index i with nums[i] > nums[i + 1]. If there is none, the array is already sorted (this covers a single element and all-equal arrays) and is returned unchanged.

Moving one element out of a sorted array creates exactly one such descent. A value moved toward the front is at least as large as every element it jumped over, so it sits at i and is too large; a value moved toward the back is at most as large as every element it jumped over, so it sits at i + 1 and is too small. Every other adjacent pair is still in order, so deleting nums[i + 1] leaves a sorted array exactly when i + 1 is the last index or nums[i] <= nums[i + 2]. In that case carry nums[i + 1] leftward with adjacent swaps while its left neighbor is strictly larger. Otherwise deleting nums[i] must leave a sorted array, so carry nums[i] rightward while its right neighbor is strictly smaller.

Invariant: every element except the one being carried stays in non-decreasing order, and the carried element stops at the first position where its neighbors on both sides are compatible with it, so the final array is non-decreasing. The sorted arrangement of a multiset is unique, so when both deletions would leave a sorted array (for example [2, 1]) either carry produces the same answer.

The test nums[i] <= nums[i + 2] must treat equal values as in order: in [2, 3, 1, 3] the 1 is the displaced element, and a strict comparison would carry the 3 instead and return [2, 1, 3, 3]. Other edge cases: a descent at index 0 (the largest value moved to the front), a descent at the second-to-last index where nums[i + 2] does not exist (the smallest value moved to the end), values at the -10^9 and 10^9 bounds, and duplicates of the moved value. The scan and the carry each take at most n steps and use only a few index variables.

• Time complexity: O(n)
• Space complexity: O(1)