Sort in Linear Time an Array Where At Most One Element Was Moved Out of Place
Company: Glean
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
```python
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**
```text
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**
```text
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**
```text
Input: nums = [1, 1, 2]
Output: [1, 1, 2]
```
The array is already sorted.
Overview: Given an array that was sorted until one element was moved to another position, return it sorted again in linear time without a full sort. Tests locating the displaced element in either direction, handling duplicates and already-sorted input, and reasoning about O(n) time with constant extra space.
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.
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
Examples
Input: ([1, 2, 9, 3, 4, 5],)
Expected Output: [1, 2, 3, 4, 5, 9]
Explanation: Source Example 1: the 9 was moved from the end toward the front to index 2.
Input: ([3, 5, 7, 1, 9],)
Expected Output: [1, 3, 5, 7, 9]
Explanation: Source Example 2: the 1 was moved from the front toward the back to index 3.
Hints
- If you removed the one displaced element, the remaining elements would already be in non-decreasing order.
- The displaced element may have moved toward the front or toward the back, by any distance, so consider both directions.
- Values may repeat, so check how your comparisons treat equal neighbors.