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.