Sort a nearly sorted array
Company: Citadel
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Quick Answer: This question evaluates algorithmic problem-solving skills, specifically understanding sorting under constrained inputs and rigorous time and space complexity analysis.
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].
Input: ([], 4)
Expected Output: []
Explanation: An empty array is already sorted.
Input: ([1, 2, 3, 4], 0)
Expected Output: [1, 2, 3, 4]
Explanation: When k is 0, every element is already exactly in its sorted position.
Input: ([2, 1, 1, 3, 3], 2)
Expected Output: [1, 1, 2, 3, 3]
Explanation: Duplicates should be handled correctly while producing nondecreasing order.
Input: ([42], 5)
Expected Output: [42]
Explanation: A single-element array is sorted regardless of k.
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.