Katkat
Back

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

GleanSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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 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.