What is the brute force approach and complexity for Sort a Nearly Sorted (K-sorted) Array?

Use a normal sort and ignore k with time complexity O(n log n) and space complexity O(log n).

What is the optimal approach and complexity for Sort a Nearly Sorted (K-sorted) Array?

Keep k + 1 candidates in a min-heap; each step writes the smallest one into the next slot with optimal time complexity O(n log k) and space complexity O(k).

How do you identify the pattern for Sort a Nearly Sorted (K-sorted) Array?

Look for key signals in the prompt: "every element is at most k positions away" indicates Each value is close to its final place, so only a window of k + 1 values can compete for the next slot.; "sort it in place" indicates The output is written into arr from the front, one slot at a time.; "k is an input, separate from n" indicates The window size comes from k, not from n. A heap of k + 1 is cheaper than sorting all n values..

Sort a Nearly Sorted (K-sorted) Array

Medium·GeeksforGeeks Pro OnlySlight Variation

GeeksforGeeks

Problem Statement

You get an array arr and a number k. Every element is at most k positions away from its place in the sorted order.

Sort arr in place, so it ends up in ascending order. Change arr itself. Nothing is returned.

Input

arr: an array of integers. k: the largest distance any element is from its sorted place.

Output

No return value. arr itself is sorted in ascending order.

Example 1

Input: arr = [2, 3, 1, 4], k = 2

Output: [1, 2, 3, 4]

1 sits at index 2 but belongs at index 0. That is 2 places away, which is allowed.

Example 2

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

Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

4 and 5 sit 2 places too early, and 2 and 3 sit 2 places too late. Nothing is farther than k.

Constraints

• Every element is at most k places away from its place in the sorted order.
• The problem page gives no other limits on n, k or the values.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“every element is at most k positions away”

→ Each value is close to its final place, so only a window of k + 1 values can compete for the next slot.

“sort it in place”

→ The output is written into arr from the front, one slot at a time.

“k is an input, separate from n”

→ The window size comes from k, not from n. A heap of k + 1 is cheaper than sorting all n values.

Approach Complexity Ladder

Brute Force — sort the whole arrayO(n log n)O(log n)

Use a normal sort and ignore k

Better — insertion sortO(n · k)O(1)

Slide each element left into place; each one only passes about k neighbours

Optimal — min-heap of k + 1O(n log k)O(k)

Keep k + 1 candidates in a min-heap; each step writes the smallest one into the next slot

Brute Force Intuition

The output has to be sorted, so a standard sort gives the right answer. It costs O(n log n). It does not use the fact that every element is already near its place.

Recognition rule for this sub-pattern:

Push the head of each list; pop the smallest, push its successor.

Remember this · K-way Merge

Trigger

K sorted lists/arrays, kth smallest across sorted rows, smallest range covering all lists.

Think

The next smallest item overall must be the front of some list — which one?

Key question

What do I push back into the heap after popping?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like K-way Merge translate into production architectures and low-level memory mechanics.

LLD Architecture