Nearly sorted

The guarantee that every item is at most k steps away means the true global minimum cannot hide in the distant tail; it must sit somewhere in the first k + 1 items. By maintaining a sliding window of size k + 1 in a min-heap, extracting the minimum always produces the definitive next element of the sorted output.

Full solution

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

vector<int> nearlySorted(vector<int>& arr, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;
    vector<int> out;
    out.reserve(arr.size());
    for (int i = 0; i <= k && i < (int)arr.size(); i++) {
        pq.push(arr[i]);
    }
    for (int i = k + 1; i < (int)arr.size(); i++) {
        out.push_back(pq.top());
        pq.pop();
        pq.push(arr[i]);
    }
    while (!pq.empty()) {
        out.push_back(pq.top());
        pq.pop();
    }
    return out;
}

import java.util.*;

public class Main {
    static int[] nearlySorted(int[] arr, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int[] out = new int[arr.length];
        int idx = 0;
        for (int i = 0; i <= k && i < arr.length; i++) {
            pq.offer(arr[i]);
        }
        for (int i = k + 1; i < arr.length; i++) {
            out[idx++] = pq.poll();
            pq.offer(arr[i]);
        }
        while (!pq.isEmpty()) {
            out[idx++] = pq.poll();
        }
        return out;
    }
}

def nearly_sorted(arr, k):
    import heapq
    heap = arr[:k + 1]
    heapq.heapify(heap)
    out = []
    for value in arr[k + 1:]:
        out.append(heapq.heappop(heap)); heapq.heappush(heap, value)
    while heap: out.append(heapq.heappop(heap))
    return out

function nearlySorted(arr) {
  return [...arr].sort((a, b) => a - b);
}

The theory behind it

Sorting — the ground this problem stands on. All Sorting problems

What Sorting is

Sorting is the act of arranging a scrambled hand of playing cards into ascending rank from left to right. It reorganizes scattered data according to a consistent comparison rule, like numbering index cards or alphabetizing names. While unsorted data requires searching every single entry to verify whether an item exists, ordered data establishes predictable relationships that make duplicates, clusters, and extreme values immediately visible.

When to reach for it

Reach for sorting when a problem asks to group identical items, detect overlaps among intervals, find rank percentiles, or pair values matching a target sum. If an unordered problem appears intractable in polynomial time, sorting the input frequently unlocks linear scans or two-pointer sweeps. When an O(n log n) preprocessing step simplifies downstream matching logic, sorting is usually the right opening move.

How the pattern works

Think of sorting as a trade: invest logarithmic overhead upfront to make subsequent queries direct and orderly. Compare adjacent elements to uncover duplicate entries, or march inward from outer boundaries once elements stand in monotonic sequence. When designing custom comparators, confirm strict weak ordering by verifying reflexivity, antisymmetry, and transitivity; inconsistent comparison logic breaks internal pivot partitions or produces corrupted outputs.