Restore an Array with One Displaced Element
Company: Glean
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Restore an Array with One Displaced Element
An integer array was originally sorted in nondecreasing order. It was then changed by removing at most one element and reinserting that same element at a different index. Restore sorted order in linear time.
```python
def restore_sorted(nums: list[int]) -> list[int]:
...
```
Return the sorted array. Do not modify the caller's input. Duplicate and negative values are allowed. The input is guaranteed to satisfy the one-displaced-element property; you do not need to validate it.
## Constraints
- `0 <= len(nums) <= 200_000`
- `-10^9 <= nums[i] <= 10^9`
- Required time complexity: `O(n)`
- Target auxiliary space, excluding the returned array: `O(1)`
## Examples
```text
Input: nums = [1, 2, 6, 3, 4, 5, 7]
Output: [1, 2, 3, 4, 5, 6, 7]
```
```text
Input: nums = [2, 1, 2, 3, 4]
Output: [1, 2, 2, 3, 4]
```
```text
Input: nums = [1, 2, 2, 3]
Output: [1, 2, 2, 3]
```
Quick Answer: Restore a nearly sorted array after at most one element was removed and reinserted elsewhere. The problem tests linear-time reasoning, constant auxiliary-space goals, duplicates, negative values, already-sorted input, and boundary cases without mutating the caller's array.
An integer array was originally sorted in nondecreasing order. It was then changed by removing at most one element and reinserting that same element at a different index. Restore sorted order in linear time.
Return the sorted array. Do not modify the caller's input. Duplicate and negative values are allowed. The input is guaranteed to satisfy the one-displaced-element property; you do not need to validate it.
## Examples
Example 1:
```text
Input: nums = [1, 2, 6, 3, 4, 5, 7]
Output: [1, 2, 3, 4, 5, 6, 7]
```
The 6 was removed from its sorted position and reinserted earlier, at index 2. Moving it back between 5 and 7 restores nondecreasing order.
Example 2:
```text
Input: nums = [2, 1, 2, 3, 4]
Output: [1, 2, 2, 3, 4]
```
A 2 was reinserted at index 0. Restoring it among its duplicates yields [1, 2, 2, 3, 4].
Example 3:
```text
Input: nums = [1, 2, 2, 3]
Output: [1, 2, 2, 3]
```
The array is already nondecreasing (at most one element may be displaced, including none), so the sorted array contains the same values in the same order.
Constraints
- 0 <= len(nums) <= 200_000
- -10^9 <= nums[i] <= 10^9
- Required time complexity: O(n)
- Target auxiliary space, excluding the returned array: O(1)
Examples
Input: ([],)
Expected Output: []
Explanation: Empty input: nothing was displaced; return an empty array.
Input: ([5],)
Expected Output: [5]
Explanation: A single element is trivially sorted.
Hints
- Scan once for the first index i where nums[i] > nums[i + 1]; if no such index exists, the array is already sorted.
- At that first descent, exactly one of the two neighbors is the displaced element. Decide by checking which single removal leaves the remaining elements nondecreasing.
- Reinserting one value into an already-sorted remainder needs only one more linear pass, not a full sort.