Sort an Almost-Sorted Array (K-sorted)

▶

Steps

setup

Initialize min-heap with first k+1 elements

We take the first k+1 = 3 elements [3, 2, 6] from the array and build a min-heap from them.

💡 Building the initial heap sets up the data structure that will help us efficiently find the smallest element among the next k+1 candidates.

Line:

heap = arr[:k+1]
heapq.heapify(heap)

💡 The heap now contains the smallest candidates for the next sorted element.

delete

Extract smallest element from heap and place at arr[0]

Extract the root (smallest element 2) from the heap and place it at index 0 of the array.

💡 Extracting the smallest element ensures the array is sorted from the start, placing the correct element at the first position.

Line:

arr[target_index] = heapq.heappop(heap)
target_index += 1

💡 The smallest element is now fixed in the sorted array at position 0.

insert

Push next element arr[3] = 5 into heap

Insert the next element 5 from the array into the heap to maintain k+1 elements.

💡 Adding the next element keeps the heap size consistent and ensures the next smallest element is among these candidates.

Line:

heapq.heappush(heap, arr[i])

💡 The heap now contains [3, 6, 5], maintaining the min-heap property.

delete

Extract smallest element from heap and place at arr[1]

Extract the root (smallest element 3) and place it at index 1 of the array.

💡 Placing the next smallest element in the array continues the sorting process.

Line:

arr[target_index] = heapq.heappop(heap)
target_index += 1

💡 The array is now sorted up to index 1 with elements [2, 3].

insert

Push next element arr[4] = 4 into heap

Insert the next element 4 into the heap to maintain k+1 elements.

💡 Continuing to add elements keeps the heap ready to provide the next smallest element.

Line:

heapq.heappush(heap, arr[i])

💡 Heap now contains [4, 6, 5] and reorders to maintain min-heap property.

delete

Extract smallest element from heap and place at arr[2]

Extract the root (smallest element 4) and place it at index 2 of the array.

💡 Placing the next smallest element continues sorting the array in order.

Line:

arr[target_index] = heapq.heappop(heap)
target_index += 1

💡 Array is sorted up to index 2: [2, 3, 4].

delete

Extract smallest element from heap and place at arr[3]

Extract the root (smallest element 5) and place it at index 3 of the array.

💡 After all elements are pushed, we extract remaining heap elements to finish sorting.

Line:

arr[target_index] = heapq.heappop(heap)
target_index += 1

💡 Array is sorted up to index 3: [2, 3, 4, 5].

delete

Extract last element from heap and place at arr[4]

Extract the last element 6 from the heap and place it at index 4 of the array.

💡 Final extraction completes the sorted array.

Line:

arr[target_index] = heapq.heappop(heap)
target_index += 1

💡 Array is fully sorted: [2, 3, 4, 5, 6].

reconstruct

Prepare to return the sorted array

The heap is empty and the array is sorted; preparing to return the result.

💡 This step clarifies that the sorting is complete and the algorithm is about to return the sorted array.

Line:

return arr

💡 The array is fully sorted and ready to be returned.

reconstruct

Return the sorted array

Return the fully sorted array as the final output of the algorithm.

💡 Returning the array completes the algorithm and provides the sorted result.

Line:

return arr

💡 The algorithm successfully sorted the k-sorted array using a min-heap.

import heapq

def sort_k_sorted_array(arr, k):
    heap = arr[:k+1]  # STEP 1: Initialize heap with first k+1 elements
    heapq.heapify(heap)  # STEP 1
    target_index = 0
    for i in range(k+1, len(arr)):
        arr[target_index] = heapq.heappop(heap)  # STEP 2,4,6: Extract min and place in array
        target_index += 1
        heapq.heappush(heap, arr[i])  # STEP 3,5: Push next element into heap
    while heap:
        arr[target_index] = heapq.heappop(heap)  # STEP 7,8: Extract remaining elements
        target_index += 1
    return arr  # STEP 9

if __name__ == '__main__':
    arr = [3, 2, 6, 5, 4]
    k = 2
    print(sort_k_sorted_array(arr, k))

📊

Sort an Almost-Sorted Array (K-sorted) - Watch the Algorithm Execute, Step by Step

Watching each heap operation and array update helps you understand how the min-heap maintains the smallest elements and how the array is sorted in-place.

heapifymin-heap

2

0

3

1

6

2

extract_minmin-heap

3

0

6

1

Added: 2

heapify_upmin-heapswap [2↔0]

3

0

6

1

5

2

extract_minmin-heap

5

0

6

1

Added: 3

heapify_upmin-heapswap [2↔0]

4

0

6

1

5

2

extract_minmin-heap

5

0

6

1

Added: 4

extract_minmin-heap

6

0

Added: 5

extract_minmin-heap

empty heap

Added: 6

peekmin-heap

empty heap

peekmin-heap

empty heap

Added: [2,3,4,5,6]

Key Takeaways

✓ Using a min-heap of size k+1 efficiently finds the next smallest element among candidates.

This insight is hard to see from code alone because the heap operations are abstract; visualization shows the heap content and root clearly.

✓ The array is sorted in-place by replacing elements from left to right as the heap extracts minimums.

Watching the array update step-by-step clarifies how the algorithm maintains sorted order without extra space.

✓ Heap insertions and extractions maintain the min-heap property, ensuring the smallest element is always accessible.

Seeing the heap reorder after each insertion or extraction helps understand why the algorithm is efficient.

Practice

1. 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

2. You need to generate the nth number whose prime factors only include 2, 3, and 5. Which approach guarantees an optimal solution that efficiently merges multiple sorted sequences generated by multiplying previously found numbers by these primes?

easy

A. Use a min-heap to merge multiple sorted sequences generated by multiplying known ugly numbers by 2, 3, and 5, while avoiding duplicates.

B. Use a greedy approach that picks the smallest next candidate without tracking duplicates or previously generated numbers.

C. Use a brute force check for each number to test if it only has 2, 3, and 5 as prime factors.

D. Use a dynamic programming approach with three pointers to merge sequences but without a heap.

Solution

1. Step 1: Understand the problem structure

   The problem requires generating numbers whose prime factors are only 2, 3, and 5, which can be seen as merging three sorted sequences: multiples of 2, 3, and 5 of previously found ugly numbers.

2. Step 2: Identify the optimal merging technique

   A min-heap efficiently merges these sequences by always extracting the smallest next candidate and avoids duplicates by tracking seen numbers, ensuring optimal time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min-heap merges k sorted sequences optimally [OK]

Hint: Min-heap merges multiple sorted sequences efficiently [OK]

Common Mistakes:

• Assuming brute force is efficient enough
• Ignoring duplicates in merging
• Using greedy without tracking duplicates

3. What is the time complexity of the optimal approach that assigns n jobs to K machines using event sorting and a single min-heap to track running jobs?

medium

A. O(n * K) because each job may check all machines for availability.

B. O(n log n) because sorting jobs dominates and heap operations are constant time.

C. O(n log K) because jobs are sorted and each heap operation on K machines costs log K.

D. O(n + K) because heap operations are amortized to constant time.

Solution

1. Step 1: Analyze sorting step

   Sorting jobs by start time takes O(n log n).

2. Step 2: Analyze heap operations

   Each job causes at most one pop and one push on the min-heap of size at most K, costing O(log K) per job.

3. Step 3: Combine complexities

   Since K ≤ n generally, O(n log n) sorting and O(n log K) heap operations combine to O(n log n). But since K ≤ n, and the problem emphasizes K machines, the heap operations dominate as O(n log K).

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Heap operations scale with log K, sorting with log n; overall O(n log K) [OK]

Hint: Heap operations cost log K, not linear K [OK]

Common Mistakes:

• Confusing heap size as n instead of K
• Ignoring sorting cost or assuming heap ops are constant time
• Assuming linear scan per job leads to O(nK)

4. Consider this modified code snippet for nth super ugly number. Which line contains a subtle bug that can cause incorrect results?

medium

A. Line where val is appended to ugly without checking duplicates

B. Line where initial primes are pushed into the heap

C. Line where heap is initialized as an empty list

D. Line where new heap element is pushed with updated index

Solution

1. Step 1: Identify difference from correct code

   The original code checks if val != ugly[-1] before appending to avoid duplicates.

2. Step 2: Understand impact of missing duplicate check

   Appending duplicates causes the sequence to have repeated numbers, leading to incorrect nth number.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Duplicate values break the strictly increasing sequence [OK]

Hint: Check for duplicate filtering when appending new ugly numbers [OK]

Common Mistakes:

• Forgetting to skip duplicates when popping from heap
• Incorrect heap push indices
• Misinitializing heap elements

5. Suppose you want to merge k sorted arrays but now each array can contain duplicate elements that can be reused multiple times in the final merged array. Which modification to the divide and conquer approach correctly handles this scenario?

hard

A. Use a min heap to repeatedly extract the smallest element and reinsert it if duplicates can be reused.

B. Modify merge_two_arrays to allow unlimited reuse by appending elements multiple times without advancing indices.

C. No change needed; the existing divide and conquer merge works correctly with duplicates and reuse.

D. Switch to a dynamic programming approach to track counts of duplicates and reuse them optimally.

Solution

1. Step 1: Understand reuse of duplicates

   Reusing duplicates means elements can appear multiple times beyond their original count, which standard merging does not support.

2. Step 2: Evaluate approaches

   Divide and conquer merges fixed arrays once, so it cannot handle reuse. Modifying merge_two_arrays to append without advancing indices causes infinite loops. Dynamic programming is not suitable here. Using a min heap allows extracting smallest elements and reinserting them if reuse is allowed, correctly handling duplicates and reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min heap supports repeated extraction and reinsertion -> handles reuse [OK]

Hint: Reuse requires dynamic extraction and reinsertion, not fixed merges [OK]

Common Mistakes:

• Assuming divide and conquer handles reuse
• Infinite loops by not advancing indices
• Using DP unnecessarily