Sort an Almost-Sorted Array (K-sorted)

📋

Problem

Imagine you receive a nearly sorted shipment of books where each book is at most k positions away from its correct place. Your task is to quickly reorder them perfectly.

Given an array where each element is at most k positions away from its target position in the sorted array, sort the array efficiently. Input: An integer array arr and an integer k. Output: The sorted array.

1 ≤ n ≤ 10^50 ≤ k < n-10^9 ≤ arr[i] ≤ 10^9

Edge cases: k = 0 → array is already sortedk = n-1 → array can be completely unsortedarray with all identical elements → output same array

</>

IDE

def sort_k_sorted_array(arr: list[int], k: int) -> list[int]:public int[] sortKSortedArray(int[] arr, int k)vector<int> sortKSortedArray(vector<int> arr, int k)function sortKSortedArray(arr, k)

def sort_k_sorted_array(arr, k):
    # Write your solution here
    pass

class Solution {
    public int[] sortKSortedArray(int[] arr, int k) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> sortKSortedArray(vector<int> arr, int k) {
    // Write your solution here
    return {};
}

function sortKSortedArray(arr, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [3, 2, 4, 5, 6]Heap size less than k+1 causing incorrect ordering and missing smallest elements.✅ Ensure the min-heap size is exactly k+1 and push the next element after each pop.

Wrong: [10, 9, 8, 7, 4, 70, 60, 50]No sorting or heap used; returns input as is.✅ Implement min-heap extraction or full sort to reorder array.

Wrong: [5, 4, 3, 2, 1]Fails to handle maximum k boundary; heap size or logic incorrect.✅ Allow heap size k+1 up to n and process all elements correctly.

Wrong: [2, 1, 3, 5, 4]Greedy local swaps instead of global heap-based sorting.✅ Use min-heap of size k+1 to extract smallest elements globally.

Wrong: Timeout or crash on large inputUsing full sort O(n log n) or brute force approach causing TLE.✅ Implement min-heap of size k+1 for O(n log k) time complexity.

✓

Test Cases

Focus on handling empty arrays, single elements, and boundary values of k correctly.

Beware of greedy approaches that only swap adjacent elements; think globally with a heap.

Optimize your solution to O(n log k) using a min-heap to handle large inputs efficiently.

t1_01basic

Input{"arr":[3,2,6,5,4],"k":2}

Expected[2,3,4,5,6]

⏱ Performance - must finish in 2000ms

Each element is at most 2 positions away from its sorted position. Using a min-heap of size k+1, we extract the smallest element step-by-step to get the sorted array.

💡 Consider using a min-heap to efficiently track the smallest elements within a sliding window.

💡 Maintain a min-heap of size k+1 to always extract the next smallest element in order.

💡 Push first k+1 elements into the heap, then for each remaining element, pop the smallest and push the next element.

Why it failed: Incorrect output means heap size or extraction logic is wrong. Fix by ensuring heap size is exactly k+1 and always push next element after popping.

✓ Correctly uses min-heap of size k+1 to sort the array.

t1_02basic

Input{"arr":[10,9,8,7,4,70,60,50],"k":4}

Expected[4,7,8,9,10,50,60,70]

⏱ Performance - must finish in 2000ms

Each element is at most 4 positions away from its sorted position. Using a min-heap of size 5, we extract elements in sorted order.

💡 Use a min-heap of size k+1 to handle elements up to k positions away.

💡 Push first k+1 elements, then pop smallest and push next element until done.

💡 This ensures the smallest element in the current window is always extracted next.

Why it failed: If output is unsorted or incorrect, likely heap size or push/pop order is wrong. Fix by maintaining heap size k+1 and pushing elements in correct order.

✓ Correctly sorts array using min-heap of size k+1.

t2_01edge

Input{"arr":[],"k":0}

Expected[]

⏱ Performance - must finish in 2000ms

Empty array input should return empty array.

💡 Check if input array is empty and handle gracefully.

💡 No elements means no sorting needed; return empty array immediately.

💡 Add a condition to return early if array length is zero.

Why it failed: Code crashes or returns non-empty output on empty input. Fix by adding a check for empty array before processing.

✓ Handles empty input correctly by returning empty array.

t2_02edge

Input{"arr":[42],"k":0}

Expected[42]

⏱ Performance - must finish in 2000ms

Single element array with k=0 is already sorted.

💡 Single element arrays are trivially sorted.

💡 Ensure code handles arrays of length 1 without errors.

💡 Return the array as is if length is 1.

Why it failed: Code fails or modifies single element array unnecessarily. Fix by returning input directly if length is 1.

✓ Correctly returns single element array unchanged.

t2_03edge

Input{"arr":[5,4,3,2,1],"k":4}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

k equals n-1 means array can be completely unsorted; full sorting needed.

💡 When k = n-1, the array can be fully unsorted.

💡 Min-heap approach still works but heap size is large (k+1 = n).

💡 Ensure algorithm handles this boundary without errors.

Why it failed: Fails or times out on max k boundary. Fix by allowing heap size k+1 up to n and handling full unsorted input.

✓ Handles maximum k boundary correctly.

t3_01corner

Input{"arr":[1,2,3,4,5],"k":0}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

Array already sorted with k=0; tests if code unnecessarily modifies sorted arrays.

💡 If k=0, array is already sorted.

💡 Check if code avoids unnecessary heap operations when k=0.

💡 Return input directly or handle k=0 as special case.

Why it failed: Code modifies or reorders already sorted array incorrectly. Fix by adding condition to return input if k=0.

✓ Correctly returns already sorted array unchanged for k=0.

t3_02corner

Input{"arr":[2,1,3,5,4],"k":1}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

Tests greedy approach trap: sorting only local pairs instead of using heap.

💡 Local swaps are not sufficient; need global ordering within k distance.

💡 Use min-heap of size k+1 to ensure correct order extraction.

💡 Avoid greedy swaps; implement heap-based extraction.

Why it failed: Greedy local swaps produce incorrect output. Fix by using min-heap of size k+1 to extract smallest elements globally.

✓ Correctly sorts array using min-heap, avoiding greedy trap.

t3_03corner

Input{"arr":[4,3,2,1,5,6,7],"k":3}

Expected[1,2,3,4,5,6,7]

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 and unbounded constraints: each element appears once but must be handled correctly.

💡 Each element appears once; no duplicates to merge multiple times.

💡 Ensure heap operations do not assume multiple occurrences.

💡 Maintain heap size k+1 and extract elements correctly.

Why it failed: Code incorrectly merges duplicates or mishandles unique elements. Fix by treating each element individually and maintaining heap size k+1.

✓ Correctly handles unique elements with heap extraction.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

n=100000 with k up to n-1; O(n log k) algorithm must complete within 2 seconds.

💡 Use a min-heap of size k+1 for O(n log k) time complexity.

💡 Avoid full sorting O(n log n) to pass time limits.

💡 Efficient heap operations and input/output handling are critical.

Why it failed: Brute force or full sort causes TLE. Fix by implementing min-heap of size k+1 for O(n log k) complexity.

✓ Algorithm runs within time limits using O(n log k) complexity.

Practice

1. Consider the following Python code implementing the optimal binary search approach to find the median of K sorted arrays. Given arrays = [[1,3,5], [2,4,6], [0,7,8]], what is the value of median1 after the binary search loop completes?

easy

A. 6

B. 3

C. 5

D. 4

Solution

1. Step 1: Calculate total length and median indices

   Total length = 3 + 3 + 3 = 9, so mid1 = (9-1)//2 = 4.

2. Step 2: Perform binary search on value range [0,8]

   Counting elements ≤ mid at each step narrows down to the smallest number with count > 4, which is 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Median of combined sorted array [0,1,2,3,4,5,6,7,8] is 4 [OK]

Hint: Median index 4 corresponds to value 4 in combined arrays [OK]

Common Mistakes:

• Off-by-one in median index
• Miscounting elements ≤ mid
• Confusing median1 and median2

2. You are given two sorted arrays and need to find the k-th smallest sum formed by adding one element from each array. Which approach guarantees an optimal solution in terms of time complexity for large input sizes?

easy

A. Use binary search on the sum range combined with a counting function to find how many pairs have sums less than or equal to mid.

B. Use dynamic programming to build a table of sums and select the k-th smallest.

C. Use a greedy approach by always picking the smallest available sum without revisiting pairs.

D. Generate all possible sums, sort them, and pick the k-th smallest sum.

Solution

1. Step 1: Understand problem constraints

   Brute force (generating all sums) is too slow for large inputs.

2. Step 2: Identify efficient approach

   Binary search on sum range with counting pairs ≤ mid efficiently narrows down the k-th smallest sum.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search reduces search space logarithmically [OK]

Hint: Binary search on sums beats brute force for large inputs [OK]

Common Mistakes:

• Assuming greedy approach always works
• Using DP which is inefficient here

3. You have K identical machines and a list of jobs, each with a start time and duration. You want to assign each job to a machine so that each machine processes jobs sequentially without overlap, always choosing the earliest available machine with the smallest index. Which algorithmic approach guarantees an optimal assignment minimizing waiting times and correctly handles job scheduling in chronological order?

easy

A. Greedy approach that assigns each job to the first machine found free by scanning all machines linearly.

B. Use a min-heap to track available machines by their next free time and assign jobs in order of start time, updating machine availability accordingly.

C. Dynamic programming that tries all possible assignments and picks the minimum total completion time.

D. Sort jobs by duration and assign them to machines in that order to minimize total processing time.

Solution

1. Step 1: Understand the problem constraints

   The problem requires assigning jobs to machines so that each job starts no earlier than its start time, machines process jobs sequentially, and the earliest available machine with the smallest index is chosen.

2. Step 2: Identify the correct approach

   Using a min-heap to track machine availability by next free time allows efficient retrieval of the earliest available machine. Sorting jobs by start time ensures chronological processing. This approach guarantees optimal scheduling and respects machine indices.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Min-heap + sorting jobs by start time -> optimal scheduling [OK]

Hint: Min-heap tracks earliest available machine efficiently [OK]

Common Mistakes:

• Using linear search for machine availability leads to O(nK) time
• Sorting by duration ignores job start times and causes conflicts
• DP approach is infeasible due to large state space

4. Consider the following Python code that merges k sorted arrays using divide and conquer. Given the input arrays [[1,4,5],[1,3,4],[2,6]], what is the value of merged_arrays after the first iteration of the while loop inside merge_k_sorted_arrays?

easy

A. [[1,1,3,4,4,5,2,6]]

B. [[1,1,3,4,4,5],[2,6]]

C. [[1,3,4,5],[1,2,4,6]]

D. [[1,1,3,4,4,5],[2,6]]

Solution

1. Step 1: Trace merging pairs in first iteration

   Arrays are [[1,4,5],[1,3,4],[2,6]]. Merge first two: merge_two_arrays([1,4,5],[1,3,4]) -> [1,1,3,4,4,5]. The last array [2,6] remains as is because no pair.

2. Step 2: Form merged_arrays after first iteration

   merged_arrays = [[1,1,3,4,4,5],[2,6]]

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   First pair merged correctly, last array unchanged -> matches [[1,1,3,4,4,5],[2,6]] [OK]

Hint: Merge pairs left to right, last array unchanged if odd count [OK]

Common Mistakes:

• Merging last array incorrectly
• Off-by-one in loop
• Appending arrays instead of merging

5. Suppose the problem is modified so that elements from nums2 can be reused multiple times in pairs (i.e., pairs can reuse the same element from nums2 multiple times). Which modification to the min-heap approach correctly handles this variant?

hard

A. Push all pairs (nums1[i] + nums2[j]) for all i, j into the heap initially and pop k times.

B. After popping a pair (i, j), push (i, j+1) and also push (i+1, j) if within bounds, allowing reuse of nums2 elements.

C. After popping a pair (i, j), push (i, j) again to allow reuse of nums2[j].

D. Modify the heap to store sums with counts of usage and only push new pairs when usage count is less than k.

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse of nums2 elements means after using nums2[j], we can also try nums2[j+1] and nums2[j] again with next nums1 element.

2. Step 2: Modify heap push logic

   After popping (i, j), pushing (i, j+1) continues along nums2, and pushing (i+1, j) allows pairing next nums1 element with the same nums2[j], enabling reuse.

3. Step 3: Reject other options

   Push all pairs (nums1[i] + nums2[j]) for all i, j into the heap initially and pop k times. is brute force and inefficient. After popping a pair (i, j), push (i, j) again to allow reuse of nums2[j]. causes infinite loops by pushing same pair repeatedly. Modify the heap to store sums with counts of usage and only push new pairs when usage count is less than k. is unnecessarily complex and not standard.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   After popping a pair (i, j), push (i, j+1) and also push (i+1, j) if within bounds, allowing reuse of nums2 elements. correctly expands pairs to allow reuse without infinite loops [OK]

Hint: Push next nums1 with same nums2 to allow reuse [OK]

Common Mistakes:

• Pushing same pair repeatedly causing infinite loops
• Brute forcing all pairs initially
• Overcomplicating usage counts