Katkat
Back

Restore an Array with One Displaced Element

GleanSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Restore a nearly sorted array where at most one element has been removed and reinserted elsewhere, in linear time and without mutating the input array.

Problem Statement

You are given an array of integers nums. The array was originally sorted in non-decreasing order. However, at most one element was removed from its position and reinserted at a different index in the array.

Write a function restore_array(nums: list[int]) -> list[int] that returns a new array containing the elements restored to non-decreasing sorted order. You must not mutate the input array nums.

Your solution should run in O(n) time and use O(1) auxiliary space (excluding the memory required to store the returned array).

Function Signature

def restore_array(nums: list[int]) -> list[int]:
    pass

Input and Output

  • Input: A list of integers nums of length n.
  • Output: A new list of integers containing all elements of nums in non-decreasing order.

Constraints

  • 1 <= len(nums) <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums is guaranteed to be reachable by moving at most one element from an originally sorted array.

Examples

Example 1

Input: nums = [1, 5, 2, 3, 4]
Output: [1, 2, 3, 4, 5]
Explanation: The value 5 was displaced from index 4 to index 1. Restoring it returns [1, 2, 3, 4, 5].

Example 2

Input: nums = [3, 1, 2, 4]
Output: [1, 2, 3, 4]
Explanation: The value 3 was moved to index 0. Removing 3 leaves [1, 2, 4], which is sorted. Reinserting 3 yields [1, 2, 3, 4].

Example 3

Input: nums = [-5, -2, -10, 0, 3]
Output: [-10, -5, -2, 0, 3]
Explanation: The negative number -10 was inserted between -2 and 0.

Edge Cases to Consider

  • The array is already sorted (nums[i] <= nums[i+1] for all valid i).
  • Arrays containing duplicate elements (e.g., [2, 2, 1, 2, 2]).
  • Displaced element moved to the very beginning or very end of the array.
  • Arrays of size 1 or 2.

Hints

Hint 1

Notice that if you remove the single displaced element, the remaining n - 1 elements are guaranteed to be in non-decreasing order.

Hint 2

Examine the inversion points where nums[i] > nums[i + 1]; there can be at most two such drop points in the array.

Hint 3

After identifying the index of the displaced element, construct the output array by copying elements and inserting the displaced value into its correct sorted location in a single O(n) pass.

Follow-up questions

  • How does the problem change if two elements were swapped instead of one element being shifted to a new position?
  • Could you return the original source and destination indices of the displaced element in O(n) time?
  • How would you approach this problem if up to k elements were displaced instead of just one?