Sort an Almost-Sorted Array (K-sorted)

🎯

Sort an Almost-Sorted Array (K-sorted)

mediumHEAPAmazonGoogle

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.

💡 This problem involves sorting an array where elements are almost sorted except for small displacements. Beginners often struggle because a full sort seems necessary, but exploiting the 'almost sorted' property leads to more efficient solutions.

📋

Problem Statement

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

💡

Example

Input"arr = [3, 2, 6, 5, 4], k = 2"

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

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.

• k = 0 → array is already sorted
• k = n-1 → array can be completely unsorted
• array with all identical elements → output same array
• array with negative and positive integers mixed

⚠️

Common Mistakes

Using a min-heap of size n instead of k+1

Time complexity degrades to O(n log n), losing efficiency

✅ Maintain heap size exactly k+1 to leverage problem property

Not handling edge case when k >= n

Index out of range errors or incorrect output

✅ Add condition to limit heap initialization to min(k+1, n)

Forgetting to extract remaining elements after main loop

Output array is incomplete or missing elements

✅ Add a final loop to pop all remaining elements from the heap

Using max-heap instead of min-heap

Incorrect ordering of elements, wrong output

✅ Use min-heap to always extract the smallest element next

🧠

Brute Force (Full Sort)

💡 This approach exists to establish a baseline: sorting the entire array without leveraging the k-sorted property. It helps beginners understand the problem's nature before optimizing.

Intuition

Since the array is almost sorted, one could ignore that fact and just sort the entire array using any standard sorting algorithm.

Algorithm

1. Take the input array.
2. Use a standard sorting algorithm (like quicksort or mergesort) to sort the entire array.
3. Return the sorted array.

💡 This algorithm is straightforward but ignores the problem's special property, making it inefficient for large inputs.

</>

Code

def sort_k_sorted_array(arr, k):
    return sorted(arr)

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

Line Notes

def sort_k_sorted_array(arr, k):Defines the function signature with inputs array and k

return sorted(arr)Uses Python's built-in sort ignoring k, simplest solution

if __name__ == '__main__':Ensures driver code runs only when script is executed directly

print(sort_k_sorted_array(arr, k))Prints the sorted array for given input

import java.util.*;
public class Main {
    public static int[] sortKSortedArray(int[] arr, int k) {
        Arrays.sort(arr);
        return arr;
    }
    public static void main(String[] args) {
        int[] arr = {3, 2, 6, 5, 4};
        int k = 2;
        int[] sorted = sortKSortedArray(arr, k);
        System.out.println(Arrays.toString(sorted));
    }
}

Line Notes

public static int[] sortKSortedArray(int[] arr, int k) {Function signature with array and k parameters

Arrays.sort(arr);Sorts entire array ignoring k, baseline approach

public static void main(String[] args) {Main method entry point

System.out.println(Arrays.toString(sorted));Prints sorted array to console

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> sortKSortedArray(vector<int>& arr, int k) {
    sort(arr.begin(), arr.end());
    return arr;
}

int main() {
    vector<int> arr = {3, 2, 6, 5, 4};
    int k = 2;
    vector<int> sorted = sortKSortedArray(arr, k);
    for (int num : sorted) cout << num << " ";
    cout << endl;
    return 0;
}

Line Notes

vector<int> sortKSortedArray(vector<int>& arr, int k) {Function signature with vector reference and k

sort(arr.begin(), arr.end());Standard library sort ignoring k

int main() {Program entry point

for (int num : sorted) cout << num << " ";Prints sorted array elements

function sortKSortedArray(arr, k) {
    return arr.sort((a, b) => a - b);
}

// Driver code
const arr = [3, 2, 6, 5, 4];
const k = 2;
console.log(sortKSortedArray(arr, k));

Line Notes

function sortKSortedArray(arr, k) {Defines function with array and k parameters

return arr.sort((a, b) => a - b);Uses built-in sort ignoring k, baseline solution

const arr = [3, 2, 6, 5, 4];Sample input array

console.log(sortKSortedArray(arr, k));Outputs sorted array to console

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sorting implementation

Sorting the entire array takes O(n log n) time regardless of k, which is inefficient for large n when k is small.

💡 For n=100000, this means about 1.5 million operations, which can be slow compared to optimized methods.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but doesn't leverage the problem's special property, so it's rarely optimal in interviews.

🧠

Min-Heap of Size k+1

💡 This approach leverages the k-sorted property by maintaining a min-heap of size k+1 to efficiently extract the next smallest element, improving time complexity.

Intuition

Since any element is at most k positions away from its sorted position, the smallest element in the current window of size k+1 must be in that window. Using a min-heap of size k+1 allows extracting the smallest element in O(log k) time.

Algorithm

1. Create a min-heap and insert the first k+1 elements.
2. For each remaining element in the array, extract the smallest element from the heap and add the next element from the array to the heap.
3. After processing all elements, extract all remaining elements from the heap.
4. Return the collected elements as the sorted array.

💡 This algorithm slides a window of size k+1 over the array, maintaining the smallest elements in a heap for efficient extraction.

</>

Code

import heapq

def sort_k_sorted_array(arr, k):
    heap = arr[:k+1]
    heapq.heapify(heap)
    result = []
    for i in range(k+1, len(arr)):
        smallest = heapq.heappop(heap)
        result.append(smallest)
        heapq.heappush(heap, arr[i])
    while heap:
        result.append(heapq.heappop(heap))
    return result

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

Line Notes

import heapqImports Python's heapq module for min-heap operations

heap = arr[:k+1]Initializes heap with first k+1 elements, the window size

heapq.heapify(heap)Transforms list into a valid min-heap

for i in range(k+1, len(arr))Iterates over remaining elements beyond initial window

smallest = heapq.heappop(heap)Extracts smallest element from heap to append to result

heapq.heappush(heap, arr[i])Adds next element from array into heap maintaining size

while heap:Extracts remaining elements after main loop finishes

import java.util.*;
public class Main {
    public static int[] sortKSortedArray(int[] arr, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int n = arr.length;
        int[] result = new int[n];
        int index = 0;
        for (int i = 0; i <= k && i < n; i++) {
            minHeap.add(arr[i]);
        }
        for (int i = k + 1; i < n; i++) {
            result[index++] = minHeap.poll();
            minHeap.add(arr[i]);
        }
        while (!minHeap.isEmpty()) {
            result[index++] = minHeap.poll();
        }
        return result;
    }
    public static void main(String[] args) {
        int[] arr = {3, 2, 6, 5, 4};
        int k = 2;
        int[] sorted = sortKSortedArray(arr, k);
        System.out.println(Arrays.toString(sorted));
    }
}

Line Notes

PriorityQueue<Integer> minHeap = new PriorityQueue<>();Creates a min-heap using Java's PriorityQueue

int n = arr.length;Stores array length for boundary checks

for (int i = 0; i <= k && i < n; i++) {Adds first k+1 elements to heap, handling array length

result[index++] = minHeap.poll();Extracts smallest element from heap to result array

minHeap.add(arr[i]);Adds next element from array to heap maintaining size

while (!minHeap.isEmpty()) {Extracts remaining elements after main loop

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

int main() {
    vector<int> arr = {3, 2, 6, 5, 4};
    int k = 2;
    vector<int> sorted = sortKSortedArray(arr, k);
    for (int num : sorted) cout << num << " ";
    cout << endl;
    return 0;
}

Line Notes

priority_queue<int, vector<int>, greater<int>> minHeap;Defines a min-heap using priority_queue with greater comparator

for (int i = 0; i <= k && i < n; i++) {Pushes first k+1 elements into min-heap

result.push_back(minHeap.top());Extracts smallest element from heap to result

minHeap.push(arr[i]);Adds next element from array to heap

while (!minHeap.empty()) {Extracts remaining elements after main loop

function sortKSortedArray(arr, k) {
    const minHeap = [];
    const result = [];
    function heapPush(val) {
        minHeap.push(val);
        let i = minHeap.length - 1;
        while (i > 0) {
            let parent = Math.floor((i - 1) / 2);
            if (minHeap[parent] <= minHeap[i]) break;
            [minHeap[parent], minHeap[i]] = [minHeap[i], minHeap[parent]];
            i = parent;
        }
    }
    function heapPop() {
        const top = minHeap[0];
        const end = minHeap.pop();
        if (minHeap.length > 0) {
            minHeap[0] = end;
            let i = 0;
            while (true) {
                let left = 2 * i + 1;
                let right = 2 * i + 2;
                let smallest = i;
                if (left < minHeap.length && minHeap[left] < minHeap[smallest]) smallest = left;
                if (right < minHeap.length && minHeap[right] < minHeap[smallest]) smallest = right;
                if (smallest === i) break;
                [minHeap[i], minHeap[smallest]] = [minHeap[smallest], minHeap[i]];
                i = smallest;
            }
        }
        return top;
    }
    for (let i = 0; i <= k && i < arr.length; i++) {
        heapPush(arr[i]);
    }
    for (let i = k + 1; i < arr.length; i++) {
        result.push(heapPop());
        heapPush(arr[i]);
    }
    while (minHeap.length > 0) {
        result.push(heapPop());
    }
    return result;
}

// Driver code
const arr = [3, 2, 6, 5, 4];
const k = 2;
console.log(sortKSortedArray(arr, k));

Line Notes

const minHeap = [];Initializes empty array to implement min-heap

function heapPush(val) {Defines function to insert element maintaining heap property

function heapPop() {Defines function to extract smallest element maintaining heap property

for (let i = 0; i <= k && i < arr.length; i++) {Pushes first k+1 elements into heap

result.push(heapPop());Extracts smallest element to result array

⏱

Complexity

TimeO(n log k)

SpaceO(k)

Building and maintaining a min-heap of size k+1 leads to O(n log k) time, which is efficient when k << n.

💡 For n=100000 and k=10, this means about 1 million operations, much faster than full sort.

Interview Verdict: Accepted and efficient for typical interview constraints

This approach is optimal for this problem and expected in interviews.

🧠

Optimized Min-Heap with In-place Output

💡 This approach improves space usage by writing the sorted elements back into the original array instead of using a separate result array.

Intuition

Since we extract elements in sorted order from the min-heap, we can overwrite the input array from the start, saving extra space.

Algorithm

1. Build a min-heap with the first k+1 elements.
2. Iterate over the array from index k+1 to end, extracting the smallest element from the heap and placing it at the correct position in the array.
3. After processing all elements, extract remaining elements from the heap and place them in the array.
4. Return the modified array.

💡 This algorithm modifies the input array in-place, reducing space complexity while maintaining time efficiency.

</>

Code

import heapq

def sort_k_sorted_array(arr, k):
    heap = arr[:k+1]
    heapq.heapify(heap)
    target_index = 0
    for i in range(k+1, len(arr)):
        arr[target_index] = heapq.heappop(heap)
        target_index += 1
        heapq.heappush(heap, arr[i])
    while heap:
        arr[target_index] = heapq.heappop(heap)
        target_index += 1
    return arr

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

Line Notes

heap = arr[:k+1]Initialize heap with first k+1 elements

heapq.heapify(heap)Convert list to min-heap

target_index = 0Index to overwrite in original array

arr[target_index] = heapq.heappop(heap)Place smallest element at correct position

heapq.heappush(heap, arr[i])Add next element to heap maintaining size

while heap:Extract remaining elements to array

import java.util.*;
public class Main {
    public static int[] sortKSortedArray(int[] arr, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int n = arr.length;
        int targetIndex = 0;
        for (int i = 0; i <= k && i < n; i++) {
            minHeap.add(arr[i]);
        }
        for (int i = k + 1; i < n; i++) {
            arr[targetIndex++] = minHeap.poll();
            minHeap.add(arr[i]);
        }
        while (!minHeap.isEmpty()) {
            arr[targetIndex++] = minHeap.poll();
        }
        return arr;
    }
    public static void main(String[] args) {
        int[] arr = {3, 2, 6, 5, 4};
        int k = 2;
        int[] sorted = sortKSortedArray(arr, k);
        System.out.println(Arrays.toString(sorted));
    }
}

Line Notes

PriorityQueue<Integer> minHeap = new PriorityQueue<>();Create min-heap

int n = arr.length;Stores array length for boundary checks

int targetIndex = 0;Index to overwrite in original array

arr[targetIndex++] = minHeap.poll();Overwrite array with smallest element

minHeap.add(arr[i]);Add next element to heap

while (!minHeap.isEmpty()) {Extract remaining elements to array

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> sortKSortedArray(vector<int>& arr, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap;
    int n = arr.size();
    for (int i = 0; i <= k && i < n; i++) {
        minHeap.push(arr[i]);
    }
    int targetIndex = 0;
    for (int i = k + 1; i < n; i++) {
        arr[targetIndex++] = minHeap.top();
        minHeap.pop();
        minHeap.push(arr[i]);
    }
    while (!minHeap.empty()) {
        arr[targetIndex++] = minHeap.top();
        minHeap.pop();
    }
    return arr;
}

int main() {
    vector<int> arr = {3, 2, 6, 5, 4};
    int k = 2;
    vector<int> sorted = sortKSortedArray(arr, k);
    for (int num : sorted) cout << num << " ";
    cout << endl;
    return 0;
}

Line Notes

int targetIndex = 0;Index to overwrite in original array

arr[targetIndex++] = minHeap.top();Overwrite array with smallest element

minHeap.push(arr[i]);Add next element to heap

while (!minHeap.empty()) {Extract remaining elements to array

return arr;Return sorted array in-place

function sortKSortedArray(arr, k) {
    const minHeap = [];
    let targetIndex = 0;
    function heapPush(val) {
        minHeap.push(val);
        let i = minHeap.length - 1;
        while (i > 0) {
            let parent = Math.floor((i - 1) / 2);
            if (minHeap[parent] <= minHeap[i]) break;
            [minHeap[parent], minHeap[i]] = [minHeap[i], minHeap[parent]];
            i = parent;
        }
    }
    function heapPop() {
        const top = minHeap[0];
        const end = minHeap.pop();
        if (minHeap.length > 0) {
            minHeap[0] = end;
            let i = 0;
            while (true) {
                let left = 2 * i + 1;
                let right = 2 * i + 2;
                let smallest = i;
                if (left < minHeap.length && minHeap[left] < minHeap[smallest]) smallest = left;
                if (right < minHeap.length && minHeap[right] < minHeap[smallest]) smallest = right;
                if (smallest === i) break;
                [minHeap[i], minHeap[smallest]] = [minHeap[smallest], minHeap[i]];
                i = smallest;
            }
        }
        return top;
    }
    for (let i = 0; i <= k && i < arr.length; i++) {
        heapPush(arr[i]);
    }
    for (let i = k + 1; i < arr.length; i++) {
        arr[targetIndex++] = heapPop();
        heapPush(arr[i]);
    }
    while (minHeap.length > 0) {
        arr[targetIndex++] = heapPop();
    }
    return arr;
}

// Driver code
const arr = [3, 2, 6, 5, 4];
const k = 2;
console.log(sortKSortedArray(arr, k));

Line Notes

let targetIndex = 0;Index to overwrite in original array

arr[targetIndex++] = heapPop();Overwrite array with smallest element extracted

heapPush(arr[i]);Add next element to heap

while (minHeap.length > 0) {Extract remaining elements to array

return arr;Return sorted array in-place

⏱

Complexity

TimeO(n log k)

SpaceO(k)

Same time complexity as previous approach but reduces space by overwriting input array instead of using extra output array.

💡 This saves memory which can be important for large inputs.

Interview Verdict: Accepted and optimal with reduced space

This is the best practical approach combining time and space efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, approach 2 or 3 is expected. Approach 1 is only for initial discussion.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Full Sort)	O(n log n)	O(1) or O(n)	No	N/A	Mention only - never code
2. Min-Heap of Size k+1	O(n log k)	O(k)	No	Yes	Code this approach
3. Optimized Min-Heap with In-place Output	O(n log k)	O(k)	No	Yes	Code if asked for space optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach and its inefficiency.Step 3: Introduce the min-heap approach leveraging the k-sorted property.Step 4: Code the min-heap solution with in-place optimization if time permits.Step 5: Test your code with edge cases and discuss complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your ability to recognize the k-sorted property, choose appropriate data structures (min-heap), and optimize space/time complexity.

Common Follow-ups

• What if k is very large (close to n)? → Use full sort or discuss tradeoffs.
• Can you do this in-place without extra space? → Discuss heapify and in-place heap operations.

💡 These follow-ups test your understanding of constraints and ability to optimize further.

🔍

Pattern Recognition

When to Use

1) Array is nearly sorted with elements close to correct position, 2) k is given as max displacement, 3) Need efficient sorting better than O(n log n), 4) Min-heap or priority queue is allowed.

Signature Phrases

'each element is at most k positions away from its sorted position''almost sorted array''k-sorted array'

NOT This Pattern When

Full sorting problems without displacement constraints or problems requiring different data structures like segment trees.

Similar Problems

Merge k Sorted Lists - uses min-heap to merge multiple sorted sequencesFind K Closest Elements - uses heap to find closest elements efficiently

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. Consider the following Python code implementing the optimal approach for the smallest range covering k lists. Given the input nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]], what is the final returned range?

easy

A. [20, 24]

B. [5, 20]

C. [0, 24]

D. [4, 20]

Solution

1. Step 1: Initialize heap and current_max

   Heap contains (4,0,0), (0,1,0), (5,2,0); current_max = 5.

2. Step 2: Iterate popping min and pushing next elements

   Pop (0,1,0), push (9,1,1), current_max=9; range = 9-0=9. Pop (4,0,0), push (10,0,1), current_max=10; range=10-4=6. Pop (5,2,0), push (18,2,1), current_max=18; range=18-5=13. Pop (9,1,1), push (12,1,2), current_max=18; range=18-9=9. Pop (10,0,1), push (15,0,2), current_max=18; range=18-10=8. Pop (12,1,2), push (20,1,3), current_max=20; range=20-12=8. Pop (15,0,2), push (24,0,3), current_max=24; range=24-15=9. Pop (18,2,1), push (22,2,2), current_max=24; range=24-18=6. Pop (20,1,3), no next element, break.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Final minimal range is [4,20] covering all lists [OK]

Hint: Track min and max updates carefully [OK]

Common Mistakes:

• Forgetting to update current_max after pushing new element
• Stopping too early before all lists exhausted
• Miscomputing range after each pop

3. Given the following code to find the 7th super ugly number with primes [2,3,5], what is the returned value?

easy

A. 8

B. 9

C. 10

D. 12

Solution

1. Step 1: Trace initial heap and ugly list

   Start with ugly=[1], heap=[(2,0,0),(3,1,0),(5,2,0)]. Pop smallest val=2, append 2 -> ugly=[1,2]. Push (2*ugly[1])=4.

2. Step 2: Continue popping and pushing

   Sequence generated: 1,2,3,4,5,6,8,10,... The 7th super ugly number is 10.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Manual heap trace confirms 7th number is 10 [OK]

Hint: Trace heap pops and pushes carefully to avoid off-by-one errors [OK]

Common Mistakes:

• Off-by-one in counting ugly numbers
• Confusing index for ugly array
• Skipping duplicates incorrectly

4. Consider the following buggy code for finding k pairs with smallest sums. Which line contains the subtle bug that can cause incorrect results or runtime errors?

medium

A. Line 16: Condition 'if j + 1 <= n2' before pushing new pair

B. Line 11: Looping up to min(k, n1) to initialize heap

C. Line 14: Popping from the min-heap

D. Line 7: Checking if nums1 or nums2 is empty

Solution

1. Step 1: Analyze boundary condition in line 16

   The condition 'if j + 1 <= n2' allows j+1 to be equal to n2, which is out of bounds for nums2 indexing.

2. Step 2: Correct condition

   It should be 'if j + 1 < n2' to prevent index out of range errors and missing pairs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Off-by-one error in boundary check causes runtime or logic errors [OK]

Hint: Check array index boundaries carefully [OK]

Common Mistakes:

• Off-by-one in array indexing
• Incorrect heap initialization
• Ignoring empty input checks

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

hard

A. Continue using the min-heap approach but do not advance the index in the list after pushing the next element, allowing reuse of the same element.

B. Use a min-heap but track counts of elements used per list and only advance indices when all elements have been used once.

C. Modify the algorithm to allow pushing the same element multiple times without advancing the index, but update current_max accordingly to avoid infinite loops.

D. The min-heap approach cannot be adapted; instead, use a dynamic programming approach to handle reuse.

Solution

1. Step 1: Understand reuse implications

   Allowing reuse means the same element can be counted multiple times, so indices alone do not track usage.

2. Step 2: Modify tracking mechanism

   Tracking counts of usage per list and advancing indices only after all elements are used once prevents infinite loops and ensures coverage.

3. Step 3: Why other options fail

   Not advancing indices leads to infinite loops; pushing same element multiple times without control breaks correctness; DP is inefficient here.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Tracking usage counts ensures correct reuse handling [OK]

Hint: Track usage counts per list to handle reuse correctly [OK]

Common Mistakes:

• Not advancing indices causing infinite loops
• Pushing duplicates without control
• Switching to DP unnecessarily