Log inSign up
mediumGeeksforGeeksNot Started

Sort a Nearly Sorted Array

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array of N elements, where each element is at most k positions away from its correct sorted position, sort the array efficiently.

Achieve an optimal time complexity of O(N log k) using a Min-Heap of size k + 1.

Example 1 · Example 1: k = 3:

Input: arr = [6, 5, 3, 2, 8, 10, 9], k = 3
Output: [2, 3, 5, 6, 8, 9, 10]
Explanation: First k + 1 = 4 elements: [6, 5, 3, 2]. Min-Heap: [2, 3, 5, 6]. Pop 2 -> placed at index 0. Push 8 -> [3, 5, 6, 8]. Pop 3 -> index 1. Push 10 -> [5, 6, 8, 10]. Pop 5 -> index 2. Push 9 -> [6, 8, 9, 10]. Remaining pops: 6, 8, 9, 10. Result: [2, 3, 5, 6, 8, 9, 10]. Min-Heap Structure (Initial Size 4): (2) / \ (3) (5) / (6)

Constraints:

  • 1 <= N <= 105
  • 1 <= k < N
  • -106 <= arr[i] <= 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Exploit the k-sorted property to bound search windows.
  • Implement the sliding priority queue pattern.
  • Analyze the asymptotic difference between O(N log N), O(N*k), and O(N log k).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Array is nearly sorted / k-sorted.
  • Every element is within k distance of its sorted location.
  • Target complexity is O(N log K) rather than O(N log N).

Algorithmic Decision Tree:

  • Quicksort/Mergesort takes O(N log N), ignoring the k-sorted constraint.
  • Insertion Sort takes O(N * k), which is slow when k is large.
  • Min-Heap of size k + 1 achieves optimal O(N log K) time and O(K) space.

Connected Patterns:

Merge k Sorted ListsKth Largest Element in an Array

1. Brute Force — Full Comparison Sort

Intuition

Call standard library sort on the array in O(N log N) time.

When to apply: When simplicity is preferred and k is close to N.

Algorithm

  1. Step 1: Sort arr ascending using standard library sort.
  2. Step 2: Return arr.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 void nearlySorted(vector<int>& arr, int k) {
9 sort(arr.begin(), arr.end());
10 }
11};
12
13int main() {
14 Solution sol;
15 vector<int> arr = {6, 5, 3, 2, 8, 10, 9};
16 sol.nearlySorted(arr, 3);
17 cout << "Sorted (Brute Force): ";
18 for (int x : arr) cout << x << " ";
19 cout << endl;
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(N log N) — O(N log N) full sorting.
  • Space complexity: O(1) auxiliary — O(1) auxiliary space.

Why Brute Force Doesn't Scale:

When k = 10 and N = 106, O(N log N) takes ~2 * 107 comparisons. O(N log k) takes ~3.3 * 106 comparisons (6x faster).

Min-Heap sorts 1,000,000 items with k = 10 in ~25ms.

2. Better — Insertion Sort

Intuition

Because every element is at most k positions away from its sorted index, the inner loop of insertion sort runs at most k times. Total time is O(N * k).

When to apply: When k is extremely small (e.g. k <= 3) and zero extra memory is permitted.

Algorithm

  1. Step 1: Loop i from 1 to N - 1.
  2. Step 2: key = arr[i], j = i - 1.
  3. Step 3: While j >= 0 and arr[j] > key: shift arr[j] right; j--.
  4. Step 4: Place key at arr[j + 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7 void nearlySorted(vector<int>& arr, int k) {
8 int n = arr.size();
9 for (int i = 1; i < n; i++) {
10 int key = arr[i];
11 int j = i - 1;
12 while (j >= 0 && arr[j] > key) {
13 arr[j + 1] = arr[j];
14 j--;
15 }
16 arr[j + 1] = key;
17 }
18 }
19};
20
21int main() {
22 Solution sol;
23 vector<int> arr = {6, 5, 3, 2, 8, 10, 9};
24 sol.nearlySorted(arr, 3);
25 cout << "Sorted (Insertion Sort): ";
26 for (int x : arr) cout << x << " ";
27 cout << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N * k) — O(N * k) time bound.
  • Space complexity: O(1) — O(1) in-place auxiliary space.

3. Optimal — Min-Heap of Capacity K + 1

Intuition

Initialize a Min-Heap with the first min(N, k + 1) elements. The root of this heap is guaranteed to be the overall minimum element for index 0. Pop it and set arr[0]. For i from k + 1 to N - 1, push arr[i] into the heap, pop the minimum, and assign it to the next index. Finally, empty the remaining heap.

When to apply: Standard optimal algorithm for k-sorted arrays.

Algorithm

  1. Step 1: Push first min(N, k + 1) elements into Min-Heap.
  2. Step 2: Initialize targetIdx = 0.
  3. Step 3: Loop i from k + 1 to N - 1: arr[targetIdx++] = heap.pop(); heap.push(arr[i]).
  4. Step 4: While heap not empty: arr[targetIdx++] = heap.pop().
  5. Step 5: Array is sorted in O(N log k) time.

Interactive Trace for Sort a Nearly Sorted Array

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: First k+1 = 4 elements pushed: [6, 5, 3, 2]
Visual state
Values and pointers at this exact step
tree
Root: 2
2
Child: 3
3
Child: 5
5
Leaf: 6
6

Node order shown; add connections to display explicit tree edges.

placed: h1
Check / comparison
Root 2 is global minimum for index 0.
Decision / next transition
Set arr[0] = 2. Push next element 8.
Why this step matters

Step 1: First k+1 = 4 elements pushed: [6, 5, 3, 2]. Root is 2.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void nearlySorted(vector<int>& arr, int k) {
10 int n = arr.size();
11 priority_queue<int, vector<int>, greater<int>> minHeap;
12
13 int limit = min(n, k + 1);
14 for (int i = 0; i < limit; i++) {
15 minHeap.push(arr[i]);
16 }
17
18 int targetIdx = 0;
19 for (int i = k + 1; i < n; i++) {
20 arr[targetIdx++] = minHeap.top();
21 minHeap.pop();
22 minHeap.push(arr[i]);
23 }
24
25 while (!minHeap.empty()) {
26 arr[targetIdx++] = minHeap.top();
27 minHeap.pop();
28 }
29 }
30};
31
32int main() {
33 Solution sol;
34 vector<int> arr = {6, 5, 3, 2, 8, 10, 9};
35 sol.nearlySorted(arr, 3);
36 cout << "Sorted (Optimal Min-Heap): ";
37 for (int x : arr) cout << x << " ";
38 cout << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N log K) — O(N log k) heap operations.
  • Space complexity: O(K) — O(k) auxiliary space for the Min-Heap.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Full Comparison SortO(N log N)O(1) auxiliarySort the array using standard sorting algorithm.Comparison sort lower bound.
2.Better — Insertion SortO(N * k)O(1) auxiliaryRun insertion sort. Since each element moves at most k spots, inner loop runs at most k times.Linear shifting per element.
3.Optimal — Min-Heap of Size K + 1OptimalO(N log K)O(K)Maintain a Min-Heap of size k + 1. Pop min and assign to target index, then push next element.None. Optimal.

Common Pitfalls & Crucial Edge Cases

Heap size k instead of k + 1

If an element can be at most k positions away, the candidates for index 0 are indices [0, k], which is k + 1 elements.

Forgetting to empty remaining heap

After pushing all array elements, the heap still contains k + 1 items that must be placed into the array.

Overwriting array elements before reading

Use targetIdx and advance carefully.

Crucial Edge Cases to Validate:

  • k == 0 — Array is already fully sorted; no swaps occur.
  • k >= N — Equivalent to standard sorting; heap grows to size N in O(N log N).
  • All identical elements — Order preserved; runs in O(N log k).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Emphasize the k + 1 heap size window size reasoning.
  2. Explain why insertion sort is O(N*k) and why Min-Heap improves it to O(N log k).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must the initial Min-Heap contain k + 1 elements rather than k elements?

Back to DSA Sheet