k-sorted

Problem Link

Problem: Nearly Sorted

Problem Statement

Given an array of n elements, where each element is at most k positions away from its target position in the sorted array (i.e., the array is nearly sorted), your task is to sort the array efficiently.

Examples

Example 1
Input: arr = [6,5,3,2,8,10,9], n = 7, k = 3
Output: [2,3,5,6,8,9,10]

Example 2
Input: arr = [10,9,8,7,4,70,60,50], n = 8, k = 4
Output: [4,7,8,9,10,50,60,70]

Constraints

1 <= n <= 10⁶
1 <= k <= n
1 <= arr[i] <= 10⁷

Intuition

In a nearly sorted array, the element which should be at position i can be found between indices i-k and i+k. Thus, for each index, we only need to consider a window of size k+1. This makes it ideal to use a min-heap of size k+1 to always get the next minimum element efficiently.

Approach

Initialize a min-heap and insert the first k+1 elements into it.
Starting from index k+1 to n-1, do the following:
- Extract the minimum from the heap and append it to the result array.
- Add the next element from the array to the heap.
Once all elements have been processed, extract and append all remaining elements from the heap.

Code (Java)

import java.util.*;

class Solution {
    ArrayList<Integer> nearlySorted(int arr[], int n, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        ArrayList<Integer> result = new ArrayList<>();

        // Step 1: Add first k+1 elements to the heap
        for (int i = 0; i <= k && i < n; i++) {
            pq.add(arr[i]);
        }

        // Step 2: Process the remaining elements
        for (int i = k + 1; i < n; i++) {
            result.add(pq.poll());
            pq.add(arr[i]);
        }

        // Step 3: Extract remaining elements
        while (!pq.isEmpty()) {
            result.add(pq.poll());
        }

        return result;
    }
}

Time and Space Complexity

Time Complexity: O(n log k)
- Inserting and polling from a heap of size k takes O(log k).
- We do this n times.
Space Complexity: O(k)
- The heap stores at most k+1 elements at a time.
- The output array uses O(n) space, which is required anyway.

Dry Run

Input: `arr = [6,5,3,2,8,10,9]`, `k = 3`

Initial heap with first 4 elements: [3,5,6,2] → heap becomes [2,3,6,5]
Pop 2 → result: [2], push 8 → heap = [3,5,6,8]
Pop 3 → result: [2,3], push 10 → heap = [5,8,6,10]
Pop 5 → result: [2,3,5], push 9 → heap = [6,8,10,9]
Pop 6 → result: [2,3,5,6]
Pop 8 → result: [2,3,5,6,8]
Pop 9 → result: [2,3,5,6,8,9]
Pop 10 → result: [2,3,5,6,8,9,10]

Conclusion

This problem efficiently demonstrates how a min-heap can be leveraged to sort a nearly sorted array in O(n log k) time instead of O(n log n). It’s a common technique used in external sorting and real-time streaming data where elements are only slightly out of order.