Sort Nearly Sorted Array
Description
You are given an array arr[] of integers where each element is at most k positions away from its correct position in the fully sorted order. This means that if the array were completely sorted, the element currently at index i would be somewhere between index max(0, i - k) and min(n - 1, i + k) in the sorted array.
Such an array is called a k-sorted or nearly sorted array.
Your task is to sort this array efficiently, taking advantage of the fact that elements are already close to their final positions.
You must rearrange the elements of arr[] in place to produce the fully sorted order. Do not use any built-in sort method.
Examples
Example 1
Input: arr = [2, 3, 1, 4], k = 2
Output: [1, 2, 3, 4]
Explanation: Each element is at most 2 positions away from where it belongs in the sorted array:
- Element 1 is at index 2 but belongs at index 0 (distance = 2)
- Element 2 is at index 0 but belongs at index 1 (distance = 1)
- Element 3 is at index 1 but belongs at index 2 (distance = 1)
- Element 4 is already at index 3 (distance = 0)
All distances are ≤ k = 2, confirming this is a valid 2-sorted array.
Example 2
Input: arr = [6, 5, 3, 2, 8, 10, 9], k = 3
Output: [2, 3, 5, 6, 8, 9, 10]
Explanation: Each element is at most 3 positions away from its sorted position:
- 2 is at index 3, belongs at index 0 (distance = 3)
- 3 is at index 2, belongs at index 1 (distance = 1)
- 5 is at index 1, belongs at index 2 (distance = 1)
- 6 is at index 0, belongs at index 3 (distance = 3)
- 8 is at index 4, belongs at index 4 (distance = 0)
- 9 is at index 6, belongs at index 5 (distance = 1)
- 10 is at index 5, belongs at index 6 (distance = 1)
All distances are ≤ k = 3.
Example 3
Input: arr = [7, 9, 14], k = 1
Output: [7, 9, 14]
Explanation: The array is already sorted. Every element is 0 positions away from its correct position, which is ≤ k = 1. No rearrangement is needed.
Constraints
- 1 ≤ arr.size() ≤ 10^6
- 0 ≤ k < arr.size()
- 1 ≤ arr[i] ≤ 10^6
Editorial
Brute Force
Intuition
The simplest way to sort any array — regardless of whether it is nearly sorted or completely random — is to use a general-purpose sorting algorithm like merge sort, quicksort, or any built-in sort.
This approach completely ignores the fact that the array is already nearly sorted. It treats the input as if it could be in any arbitrary order and applies a full O(N log N) sorting algorithm.
Think of it like hiring a professional organizer to rearrange your entire bookshelf from scratch, even though only a few books are slightly out of place. They will get the job done, but they are doing far more work than necessary because they do not leverage the existing near-order.
This is a valid starting point, but it wastes the valuable constraint that elements are at most k positions away from their correct spots.
Step-by-Step Explanation
Let's trace through with arr = [6, 5, 3, 2, 8, 10, 9], k = 3 using a simple sort:
Step 1: Start with the unsorted input: [6, 5, 3, 2, 8, 10, 9].
Step 2: Apply a comparison-based sort (e.g., merge sort). The algorithm does not know or care that k = 3. It treats the array as fully unsorted.
Step 3: The sort processes all N = 7 elements through its standard divide-and-conquer or comparison process, performing O(N log N) comparisons.
Step 4: Final sorted output: [2, 3, 5, 6, 8, 9, 10].
The sort succeeds, but it did O(7 × log 7) ≈ 20 comparisons. As we will see, a smarter approach can exploit k = 3 to reduce this.
Algorithm
- Take the input array
arr[]. - Apply any standard O(N log N) sorting algorithm (merge sort, heap sort, etc.).
- The array is now fully sorted.
Note: This approach does not use the value of k at all.
Code
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
void nearlySorted(vector<int>& arr, int k) {
int n = arr.size();
// Simple merge sort implementation
mergeSort(arr, 0, n - 1);
}
private:
void mergeSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int> temp;
int i = left, j = mid + 1;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) temp.push_back(arr[i++]);
else temp.push_back(arr[j++]);
}
while (i <= mid) temp.push_back(arr[i++]);
while (j <= right) temp.push_back(arr[j++]);
for (int idx = left; idx <= right; idx++)
arr[idx] = temp[idx - left];
}
};class Solution:
def nearlySorted(self, arr, k):
# Simple merge sort implementation
if len(arr) <= 1:
return
self._merge_sort(arr, 0, len(arr) - 1)
def _merge_sort(self, arr, left, right):
if left >= right:
return
mid = left + (right - left) // 2
self._merge_sort(arr, left, mid)
self._merge_sort(arr, mid + 1, right)
self._merge(arr, left, mid, right)
def _merge(self, arr, left, mid, right):
temp = []
i, j = left, mid + 1
while i <= mid and j <= right:
if arr[i] <= arr[j]:
temp.append(arr[i])
i += 1
else:
temp.append(arr[j])
j += 1
while i <= mid:
temp.append(arr[i])
i += 1
while j <= right:
temp.append(arr[j])
j += 1
for idx in range(left, right + 1):
arr[idx] = temp[idx - left]class Solution {
public void nearlySorted(int[] arr, int k) {
mergeSort(arr, 0, arr.length - 1);
}
private void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
private void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, idx = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) temp[idx++] = arr[i++];
else temp[idx++] = arr[j++];
}
while (i <= mid) temp[idx++] = arr[i++];
while (j <= right) temp[idx++] = arr[j++];
for (int t = 0; t < temp.length; t++)
arr[left + t] = temp[t];
}
}Complexity Analysis
Time Complexity: O(N log N)
Merge sort divides the array into halves log N times and merges in O(N) at each level. This gives O(N log N) total comparisons and swaps. The value of k is completely unused — even if k = 1 (array is almost sorted), we still do O(N log N) work.
Space Complexity: O(N)
Merge sort requires O(N) auxiliary space for the temporary merge buffer. If we used heap sort instead, space would be O(1), but time would still be O(N log N).
Why This Approach Is Not Efficient
The brute force approach uses O(N log N) time, but it ignores the crucial constraint that each element is at most k positions away from its sorted position. When k is much smaller than N (e.g., k = 3 for an array of 1,000,000 elements), the array is nearly sorted, and we are doing vastly more work than necessary.
The key insight is: to determine which element goes at position i in the sorted array, we only need to consider a window of at most k + 1 candidates (from index i to i + k). We do not need to compare every element against every other element.
A general-purpose sort does not exploit this locality. It compares elements that are far apart in the array, even though the k-sorted guarantee means distant elements could never swap with each other.
Can we find an approach that processes only local neighborhoods of size k instead of the entire array?
Better Approach - Insertion Sort
Intuition
Insertion sort is a sorting algorithm that works by maintaining a sorted prefix and inserting each new element into its correct position within that prefix. For a random array, insertion sort is O(N²) — terrible for large inputs. But for a nearly sorted array, it shines!
Why? Because insertion sort's inner loop shifts elements backward to make room for the new element. If the array is k-sorted, each element needs to shift backward by at most k positions before it finds its correct spot. This means the inner loop runs at most k times per element instead of up to N times.
Imagine you have a deck of cards that is almost in order — each card is at most 3 positions from where it should be. If you pick up each card and slide it left until it finds its place, you will never need more than 3 slides per card. That is exactly what insertion sort does.
The total work becomes O(N × k) instead of O(N × N). When k is small relative to N, this is a significant improvement over O(N log N).
Step-by-Step Explanation
Let's trace through with arr = [6, 5, 3, 2, 8, 10, 9], k = 3:
Step 1: Start with arr = [6, 5, 3, 2, 8, 10, 9]. Index 0 is trivially sorted as a single element.
Step 2: Process index 1 (value 5).
- key = 5, compare with arr[0] = 6.
- 6 > 5, so shift 6 right: arr = [6, 6, 3, 2, 8, 10, 9].
- Insert 5 at index 0: arr = [5, 6, 3, 2, 8, 10, 9].
- Shifted 1 position (≤ k = 3). ✓
Step 3: Process index 2 (value 3).
- key = 3, compare with arr[1] = 6.
- 6 > 3, shift 6 right: arr = [5, 6, 6, 2, 8, 10, 9].
- Compare with arr[0] = 5. 5 > 3, shift 5 right: arr = [5, 5, 6, 2, 8, 10, 9].
- Insert 3 at index 0: arr = [3, 5, 6, 2, 8, 10, 9].
- Shifted 2 positions (≤ k = 3). ✓
Step 4: Process index 3 (value 2).
- key = 2, compare with arr[2] = 6.
- 6 > 2, shift right: arr = [3, 5, 6, 6, 8, 10, 9].
- Compare with arr[1] = 5. 5 > 2, shift: arr = [3, 5, 5, 6, 8, 10, 9].
- Compare with arr[0] = 3. 3 > 2, shift: arr = [3, 3, 5, 6, 8, 10, 9].
- Insert 2 at index 0: arr = [2, 3, 5, 6, 8, 10, 9].
- Shifted 3 positions (= k = 3). ✓
Step 5: Process index 4 (value 8).
- key = 8, compare with arr[3] = 6.
- 6 < 8, no shift needed. 8 stays at index 4.
- arr = [2, 3, 5, 6, 8, 10, 9].
- Shifted 0 positions. ✓
Step 6: Process index 5 (value 10).
- key = 10, compare with arr[4] = 8.
- 8 < 10, no shift needed. 10 stays at index 5.
- arr = [2, 3, 5, 6, 8, 10, 9].
- Shifted 0 positions. ✓
Step 7: Process index 6 (value 9).
- key = 9, compare with arr[5] = 10.
- 10 > 9, shift right: arr = [2, 3, 5, 6, 8, 10, 10].
- Compare with arr[4] = 8. 8 < 9, stop.
- Insert 9 at index 5: arr = [2, 3, 5, 6, 8, 9, 10].
- Shifted 1 position (≤ k = 3). ✓
Result: arr = [2, 3, 5, 6, 8, 9, 10]. Fully sorted!
Insertion Sort on a K-Sorted Array — Watch how insertion sort efficiently handles a nearly sorted array. Each element shifts at most k positions to reach its correct spot, making the inner loop very short.
Algorithm
- For each index
ifrom 1 to N-1:
a. Storekey = arr[i].
b. Setj = i - 1.
c. Whilej >= 0andarr[j] > key:- Shift
arr[j]toarr[j + 1]. - Decrement
j.
d. Placekeyatarr[j + 1].
- Shift
- The array is now sorted.
Because the array is k-sorted, the inner while loop runs at most k times per element.
Code
#include <vector>
using namespace std;
class Solution {
public:
void nearlySorted(vector<int>& arr, int k) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Shift elements greater than key to the right
// In a k-sorted array, this loop runs at most k times
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
};class Solution:
def nearlySorted(self, arr, k):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
# Shift elements greater than key to the right
# In a k-sorted array, this loop runs at most k times
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = keyclass Solution {
public void nearlySorted(int[] arr, int k) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Shift elements greater than key to the right
// In a k-sorted array, this loop runs at most k times
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
}Complexity Analysis
Time Complexity: O(N × k)
The outer loop runs N times (once per element). The inner loop shifts each element backward by at most k positions because the array is k-sorted. So the total number of shifts across all iterations is at most N × k. When k is a small constant (e.g., k = 3), this is effectively O(N). When k approaches N, it degrades to O(N²).
Space Complexity: O(1)
Insertion sort operates entirely in-place. We only use a few temporary variables (key, j), which is constant extra space regardless of input size.
Why This Approach Is Not Efficient
While insertion sort is a significant improvement over general sorting for small k values, its O(N × k) time complexity can still be problematic. Consider a scenario where N = 10^6 and k = 10^3. The total operations would be 10^9, which exceeds typical time limits.
The fundamental issue is that insertion sort finds the minimum of the next k elements by scanning them one by one. For each position we want to fill, we implicitly search through up to k elements via the shifting process to determine where the current element belongs.
What if we could find the minimum of the next k + 1 candidates in O(log k) time instead of O(k) time? A min heap provides exactly this capability: it can give us the minimum element in O(1) time and can insert/remove elements in O(log k) time.
By maintaining a min heap of size k + 1, we can extract the correct element for each position in O(log k) time, reducing the total from O(N × k) to O(N × log k).
Optimal Approach - Min Heap
Intuition
The key insight is this: in a k-sorted array, the element that belongs at position i in the sorted output must currently be somewhere in the range [i, i + k] of the unsorted array. This is because no element is more than k positions away from where it should be.
So to find the correct element for position 0, we only need to look at elements at indices 0 through k. The smallest among these k + 1 elements is the one that belongs at position 0. For position 1, the candidates are indices 1 through k + 1, and so on.
To efficiently find the minimum in a sliding window of k + 1 elements, we use a min heap (priority queue):
- First, insert the first k + 1 elements into the min heap.
- For each subsequent position in the array, extract the minimum from the heap (this is the correct element for that position) and insert the next unprocessed element.
- After all elements are processed, drain the remaining elements from the heap.
Think of it like a conveyor belt with a small sorting station. The station can hold k + 1 items at a time. Items arrive from the belt, the station always sends out the smallest item it currently holds, and a new item rolls in to replace it. Because no item is more than k spots from its destination, the station always has the correct next item available.
The heap keeps the window of k + 1 candidates organized so that extracting the minimum takes O(log k) instead of O(k). Over N elements, this gives O(N log k) total time.
Step-by-Step Explanation
Let's trace with arr = [6, 5, 3, 2, 8, 10, 9], k = 3:
Step 1: Build initial min heap with first k + 1 = 4 elements: {6, 5, 3, 2}.
- Min heap: [2, 5, 3, 6] (heap-ordered array). The minimum is 2.
- Write index = 0 (where to place the next extracted element).
Step 2: Extract min (2) from heap. Place at arr[0].
- arr[0] = 2. Insert next element arr[4] = 8 into heap.
- Heap: [3, 5, 8, 6]. Write index = 1.
Step 3: Extract min (3) from heap. Place at arr[1].
- arr[1] = 3. Insert next element arr[5] = 10 into heap.
- Heap: [5, 6, 8, 10]. Write index = 2.
Step 4: Extract min (5) from heap. Place at arr[2].
- arr[2] = 5. Insert next element arr[6] = 9 into heap.
- Heap: [6, 9, 8, 10]. Write index = 3.
Step 5: Extract min (6) from heap. Place at arr[3].
- arr[3] = 6. No more elements to insert (all 7 processed).
- Heap: [8, 9, 10]. Write index = 4.
Step 6: Drain remaining heap elements.
- Extract 8, place at arr[4]. Heap: [9, 10].
- Extract 9, place at arr[5]. Heap: [10].
- Extract 10, place at arr[6]. Heap: [].
Step 7: Final result.
- arr = [2, 3, 5, 6, 8, 9, 10]. Fully sorted!
Min Heap Sliding Window — Extracting Sorted Order from K-Sorted Array — Watch how a min heap of size k+1 acts as a sliding window: the minimum is always extracted for the next output position, and the next unseen element is inserted. The heap ensures O(log k) per operation.
Algorithm
- Create a min heap of size k + 1.
- Insert the first
min(k + 1, N)elements from the array into the heap. - Set
writeIdx = 0. - For each remaining element
arr[i](from index k + 1 to N - 1):
a. Extract the minimum from the heap and place it atarr[writeIdx].
b. IncrementwriteIdx.
c. Insertarr[i]into the heap. - While the heap is not empty:
a. Extract the minimum and place it atarr[writeIdx].
b. IncrementwriteIdx. - The array is now sorted.
Code
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
void nearlySorted(vector<int>& arr, int k) {
int n = arr.size();
// Min heap (priority queue with greater comparator)
priority_queue<int, vector<int>, greater<int>> minHeap;
// Insert first k+1 elements into the heap
int limit = min(k + 1, n);
for (int i = 0; i < limit; i++) {
minHeap.push(arr[i]);
}
int writeIdx = 0;
// For remaining elements: extract min, insert next
for (int i = limit; i < n; i++) {
arr[writeIdx++] = minHeap.top();
minHeap.pop();
minHeap.push(arr[i]);
}
// Drain remaining elements from the heap
while (!minHeap.empty()) {
arr[writeIdx++] = minHeap.top();
minHeap.pop();
}
}
};import heapq
class Solution:
def nearlySorted(self, arr, k):
n = len(arr)
# Build a min heap with first k+1 elements
min_heap = arr[:min(k + 1, n)]
heapq.heapify(min_heap)
write_idx = 0
# For remaining elements: extract min, insert next
for i in range(k + 1, n):
arr[write_idx] = heapq.heappop(min_heap)
write_idx += 1
heapq.heappush(min_heap, arr[i])
# Drain remaining elements from the heap
while min_heap:
arr[write_idx] = heapq.heappop(min_heap)
write_idx += 1import java.util.PriorityQueue;
class Solution {
public void nearlySorted(int[] arr, int k) {
int n = arr.length;
// Min heap (default PriorityQueue in Java is min heap)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// Insert first k+1 elements into the heap
int limit = Math.min(k + 1, n);
for (int i = 0; i < limit; i++) {
minHeap.add(arr[i]);
}
int writeIdx = 0;
// For remaining elements: extract min, insert next
for (int i = limit; i < n; i++) {
arr[writeIdx++] = minHeap.poll();
minHeap.add(arr[i]);
}
// Drain remaining elements from the heap
while (!minHeap.isEmpty()) {
arr[writeIdx++] = minHeap.poll();
}
}
}Complexity Analysis
Time Complexity: O(N log k)
We perform N insertions and N extractions on a min heap of maximum size k + 1. Each insertion and extraction takes O(log(k + 1)) = O(log k) time. So the total time is O(N × log k).
Compare this to our previous approaches:
- Brute force sort: O(N log N)
- Insertion sort: O(N × k)
- Min heap: O(N log k)
Since log k ≤ k for all k ≥ 1, the heap approach is never worse than insertion sort. And since log k ≤ log N, it is never worse than general sorting either. When k is much smaller than N, the improvement is dramatic. For example, with N = 10^6 and k = 1000: brute force does ~20 million operations, insertion sort does ~1 billion, but the heap approach does only ~10 million.
Space Complexity: O(k)
The min heap stores at most k + 1 elements at any time. This is optimal because we need to consider k + 1 candidates for each output position, and we cannot do better without storing them.