Sort a nearly sorted array
Company: Citadel
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Given an array of length \(n\) in which every element is at most \(k\) positions away from its location in the fully sorted order, design an algorithm to return the sorted array. Aim for a solution that is more efficient than \(O(n \log n)\), and state the time and space complexity.
Quick Answer: This question evaluates algorithmic problem-solving skills, specifically understanding sorting under constrained inputs and rigorous time and space complexity analysis.
Given an integer array nums of length n where every element is at most k positions away from its position in the fully sorted array, return the array sorted in nondecreasing order. Design an algorithm that takes advantage of the nearly sorted property and is more efficient than sorting the entire array with a general O(n log n) algorithm when k is small.
Constraints
- 0 <= len(nums) <= 100000
- 0 <= k <= 100000
- -1000000000 <= nums[i] <= 1000000000
- nums is guaranteed to be k-nearly sorted
Examples
Input: ([6, 5, 3, 2, 8, 10, 9], 3)
Expected Output: [2, 3, 5, 6, 8, 9, 10]
Explanation: Each value is at most 3 positions away from its sorted position. Sorting the array gives the expected result.
Input: ([-1, -3, -2, 2, 1, 4], 2)
Expected Output: [-3, -2, -1, 1, 2, 4]
Explanation: The array contains negative numbers and is 2-nearly sorted. The sorted order is [-3, -2, -1, 1, 2, 4].
Hints
- At any point, the next smallest element must be among the next k + 1 elements that have not yet been placed.
- Use a data structure that can efficiently return and remove the smallest candidate.