Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Heap & Priority Queue

Sort a K-Sorted Array

Medium · Heap & Priority Queue · Asked at Amazon, Microsoft, Flipkart

Every element is at most k positions away from where it would be in the sorted array. Sort the array in O(n log k).

Input

First line: n k. Second line: n integers.

Output

The sorted array.

Constraints

The smallest element must be among the first k + 1. Keep a min-heap of k + 1 elements; pop the minimum, push the next element.

Example 1

Input

7 3
6 5 3 2 8 10 9

Output

2 3 5 6 8 9 10

Example 2

Input

5 0
1 2 3 4 5

Output

1 2 3 4 5

Hints

  1. The smallest element of the whole array must be among the first k + 1 elements.
  2. Slide a min-heap of size k + 1 along the array: pop the minimum into the output, push the next element.

Approach

Fill a min-heap with the first k + 1 elements. Then for each remaining element: pop the minimum (it is the next element of the sorted order, since nothing further away can be smaller) and push the new element. Finally pop everything left. Each heap operation is O(log k).

Complexity: O(n log k) time · O(k) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    vector<long long> out;
    for (int i = 0; i < n; i++) {
        pq.push(a[i]);
        if ((int)pq.size() > k) out.push_back(pq.top()), pq.pop();
    }
    while (!pq.empty()) out.push_back(pq.top()), pq.pop();
    for (int i = 0; i < n; i++) cout << out[i] << (i + 1 < n ? " " : "\n");
    return 0;
}

Python solution

import sys
import heapq

data = list(map(int, sys.stdin.read().split()))
n, k, a = data[0], data[1], data[2:]
heap, out = [], []
for x in a:
    heapq.heappush(heap, x)
    if len(heap) > k:
        out.append(heapq.heappop(heap))
while heap:
    out.append(heapq.heappop(heap))
print(*out)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        PriorityQueue<Long> pq = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();
        int printed = 0;
        for (int i = 0; i < n; i++) {
            pq.add(sc.nextLong());
            if (pq.size() > k) sb.append(printed++ > 0 ? " " : "").append(pq.poll());
        }
        while (!pq.isEmpty()) sb.append(printed++ > 0 ? " " : "").append(pq.poll());
        System.out.println(sb);
    }
}

Solve Sort a K-Sorted Array online · All practice problems