Interview Preptwo-pointersmediumGoogleAmazonFacebook

Minimum Difference Between K Closest Elements

Choose your preparation mode4 modes available

Try It Solution Trace

▶

Steps

setup

Start with the original array

We begin with the unsorted input array and the given K value. No operations have been performed yet.

💡 Seeing the original array helps you understand why sorting is necessary before sliding the window.

Line:

arr = [10, 12, 10, 7, 5, 22]
k = 3

💡 The array is unsorted, so direct sliding windows won't work correctly.

setup

Sort the array

The array is sorted in ascending order to prepare for sliding window operations.

💡 Sorting groups close values together, making it easier to find minimum differences in windows.

Line:arr.sort()

💡 Sorted array allows us to consider only consecutive elements for minimum difference.

setup

Initialize minimum difference

Set min_diff to infinity to track the smallest difference found during sliding window iterations.

💡 Starting with infinity ensures any real difference found will be smaller and update min_diff.

Line:min_diff = float('inf')

💡 This variable will hold the best answer found so far.

traverse

Start sliding window at i=0

Set pointer i to 0, marking the start of the first window of size K=3.

💡 The window covers elements from index i to i+K-1, which is 0 to 2 initially.

Line:for i in range(len(arr) - k + 1):

💡 We will examine each window of size K in the sorted array.

compare

Calculate difference for window i=0

Calculate current_diff = arr[2] - arr[0] = 10 - 5 = 5 for the window [5,7,10].

💡 Difference between max and min in the window shows how close these elements are.

Line:current_diff = arr[i + k - 1] - arr[i]

💡 This difference is a candidate for minimum difference.

insert

Update min_diff with current_diff=5

Since 5 < infinity, update min_diff to 5.

💡 We keep track of the smallest difference found so far.

Line:

if current_diff < min_diff:
    min_diff = current_diff

💡 min_diff now holds the best answer found after first window.

traverse

Slide window to i=1

Move pointer i to 1, sliding the window to cover elements [7, 10, 10].

💡 Each slide examines a new group of K elements for a potentially smaller difference.

Line:for i in range(len(arr) - k + 1):

💡 We systematically check all windows of size K.

compare

Calculate difference for window i=1

Calculate current_diff = arr[3] - arr[1] = 10 - 7 = 3 for window [7,10,10].

💡 We check if this difference is smaller than the current min_diff.

Line:current_diff = arr[i + k - 1] - arr[i]

💡 This difference is smaller than previous min_diff of 5.

insert

Update min_diff with current_diff=3

Since 3 < 5, update min_diff to 3.

💡 We found a smaller difference, so we update our best answer.

Line:

if current_diff < min_diff:
    min_diff = current_diff

💡 min_diff reflects the smallest difference found so far.

traverse

Slide window to i=2

Move pointer i to 2, sliding the window to cover elements [10, 10, 12].

💡 We continue sliding to check all possible windows of size K.

Line:for i in range(len(arr) - k + 1):

💡 Systematic window movement ensures all candidates are checked.

compare

Calculate difference for window i=2

Calculate current_diff = arr[4] - arr[2] = 12 - 10 = 2 for window [10,10,12].

💡 This difference is smaller than previous min_diff of 3.

Line:current_diff = arr[i + k - 1] - arr[i]

💡 We found an even smaller difference, improving our answer.

insert

Update min_diff with current_diff=2

Since 2 < 3, update min_diff to 2.

💡 We keep track of the smallest difference found so far.

Line:

if current_diff < min_diff:
    min_diff = current_diff

💡 min_diff now holds the smallest difference found in all windows so far.

traverse

Slide window to i=3

Move pointer i to 3, sliding the window to cover elements [10, 12, 22].

💡 We check the last possible window of size K in the array.

Line:for i in range(len(arr) - k + 1):

💡 All windows have now been considered.

compare

Calculate difference for window i=3

Calculate current_diff = arr[5] - arr[3] = 22 - 10 = 12 for window [10,12,22].

💡 This difference is larger than current min_diff, so no update will happen.

Line:current_diff = arr[i + k - 1] - arr[i]

💡 Not all windows improve the minimum difference.

prune

Do not update min_diff since current_diff=12 > 2

Since 12 is greater than current min_diff 2, min_diff remains unchanged.

💡 We only update min_diff when a smaller difference is found.

Line:

if current_diff < min_diff:
    min_diff = current_diff

💡 The algorithm efficiently ignores worse candidates.

reconstruct

End of sliding window loop

All windows have been checked; min_diff holds the smallest difference found.

💡 The final min_diff is the answer to the problem.

Line:return min_diff

💡 The algorithm returns the minimum difference found after full scan.

def min_diff_early_stop(arr, k):  # STEP 1-2
    arr.sort()  # STEP 2
    min_diff = float('inf')  # STEP 3
    for i in range(len(arr) - k + 1):  # STEP 4,7,10,13
        current_diff = arr[i + k - 1] - arr[i]  # STEP 5,8,11,14
        if current_diff == 0:  # (not triggered in this example)
            return 0
        if current_diff < min_diff:  # STEP 6,9,12,15
            min_diff = current_diff
    return min_diff  # STEP 16

📊

Minimum Difference Between K Closest Elements - Watch the Algorithm Execute, Step by Step

Watching each step helps you understand how sorting and sliding windows work together to efficiently find the minimum difference among K elements without checking all subsets.

Step 1/16

·Active fill★Answer cell

setup

Result: "∞"

setup

Result: "∞"

setup

Result: "∞"

traverse

Result: "∞"

compare

Result: "∞"

insert

Result: 5

move_right

Result: 5

compare

Result: 5

insert

Result: 3

move_right

Result: 3

compare

Result: 3

insert

Result: 2

move_right

Result: 2

compare

Result: 2

prune

Result: 2

reconstruct

Result: 2

Key Takeaways

✓ Sorting the array is essential to efficiently find the minimum difference among K elements.

Without sorting, you'd have to check all subsets, which is much slower and harder to visualize.

✓ Sliding a fixed-size window over the sorted array lets us consider only consecutive elements, reducing complexity.

This approach leverages the sorted order to avoid redundant checks and find the answer quickly.

✓ Tracking and updating the minimum difference at each step shows how the algorithm narrows down the best candidate.

Seeing min_diff update visually helps understand the pruning of worse candidates.

Practice

(1/5)

1. Consider the following Python function implementing the optimal approach for counting triplets with sum smaller than target. What is the returned value when calling threeSumSmaller([-2, 0, 1, 3], 2)?

easy

A. 2

B. 3

C. 1

D. 4

Solution

Step 1: Sort input and initialize variables
Sorted array is [-2, 0, 1, 3], count=0, n=4.
Step 2: Iterate and count triplets
For i=0 (-2), check if sum of first three elements >= 2? -2+0+1= -1 < 2, continue. Use two pointers left=1, right=3. - curr_sum = -2 + 0 + 3 = 1 < 2 -> count += 3-1=2, left=2 - curr_sum = -2 + 1 + 3 = 2 not < 2 -> right=2 Now left=2, right=2 ends loop. For i=1 (0), sum of nums[1]+nums[2]+nums[3] = 0+1+3=4 >= 2 -> break loop. Total count=2.
Final Answer:
Option A -> Option A
Quick Check:
Matches expected output from example [OK]

Hint: Count increments by right-left when sum < target [OK]

Common Mistakes:

Off-by-one in counting pairs
Not breaking early when minimal sum >= target
Misusing pointers leading to wrong counts

2. Consider the following code snippet implementing the Dutch National Flag algorithm. Given the input array [2, 0, 1], what is the value of mid after the first swap operation inside the while loop?

easy

A. 3

B. 2

C. 0

D. 1

Solution

Step 1: Trace initial pointers and first iteration
Initially, low=0, mid=0, high=2, nums=[2,0,1]. Since nums[mid]=2, swap nums[mid] and nums[high]: swap nums[0] and nums[2]. Array becomes [1,0,2], high=1, mid remains 0.
Step 2: Value of mid after first swap
After swapping 2 and 1, mid is not incremented and remains 0.
Final Answer:
Option C -> Option C
Quick Check:
mid does not increment after swapping 2, so mid=0 after first swap [OK]

Hint: mid increments only after swapping 0 [OK]

Common Mistakes:

Assuming mid increments after swapping 2
Off-by-one on mid pointer
Confusing low and mid increments

3. The following code attempts to implement the Dutch National Flag algorithm but contains a subtle bug. Identify the line causing the bug.

medium

A. Line where mid is incremented after swapping 0

B. Line where low is incremented

C. Line where mid is incremented after encountering 1

D. Line where high is decremented after swapping 2

Solution

Step 1: Identify pointer updates after swapping 0
After swapping nums[low] and nums[mid] when nums[mid]==0, both low and mid must be incremented to avoid infinite loops or incorrect ordering.
Step 2: Locate missing increment
The code increments low but does not increment mid after swapping 0, causing mid to stay at the same index and potentially reprocessing the same element indefinitely.
Final Answer:
Option A -> Option A
Quick Check:
Missing mid increment after swapping 0 causes infinite loop or wrong output [OK]

Hint: mid must increment after swapping 0 to progress [OK]

Common Mistakes:

Forgetting mid increment after swap
Confusing pointer roles
Incrementing mid after swapping 2

4. Suppose the 4Sum problem is modified so that elements can be reused multiple times in quadruplets (i.e., indices can repeat). Which modification to the optimal hash map approach correctly handles this variant?

hard

A. Remove the index overlap check and allow all pairs to combine freely.

B. Use the same hash map approach but skip sorting the array to allow duplicates.

C. Modify the pair combination step to allow pairs with overlapping indices and remove index checks, but ensure quadruplets are sorted and unique.

D. Switch to brute force four nested loops since hash map approach cannot handle reuse.

Solution

Step 1: Understand reuse means indices can repeat
Index overlap check must be removed or relaxed to allow repeated elements.
Step 2: Adjust pair combination logic
Allow pairs with overlapping indices but still sort quadruplets and use a set to avoid duplicates.
Step 3: Evaluate other options
Removing sorting breaks duplicate handling; brute force is inefficient; simply removing checks without sorting leads to duplicates.
Final Answer:
Option C -> Option C
Quick Check:
Allow index overlap but keep sorting and deduplication [OK]

Hint: Allow index overlap but keep sorting and deduplication [OK]

Common Mistakes:

Removing sorting causes duplicates
Assuming brute force is only solution

5. Suppose the input array is no longer sorted but you still need to return the squares of each number in sorted order. Which of the following approaches is correct and efficient?

hard

A. Square each element and then sort the resulting array using a standard sorting algorithm.

B. Use a max-heap to insert squares and extract them in sorted order.

C. Use the two-pointer approach from ends, as it works regardless of input order.

D. Modify the input array in place by squaring and then perform an in-place merge sort.

Solution

Step 1: Recognize input is unsorted
Two-pointer approach relies on sorted input; it fails if input is unsorted.
Step 2: Choose a correct approach
Squaring then sorting with a standard sort is correct and efficient (O(n log n)) for unsorted input.
Final Answer:
Option A -> Option A
Quick Check:
Sorting after squaring handles unsorted input correctly [OK]

Hint: Two-pointer requires sorted input; else sort after squaring [OK]

Common Mistakes:

Applying two-pointer on unsorted input
Using complex data structures unnecessarily
Assuming in-place modifications preserve order

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Start with the original array

Sort the array

Initialize minimum difference

Start sliding window at i=0

Calculate difference for window i=0

Update min_diff with current_diff=5

Slide window to i=1

Calculate difference for window i=1

Update min_diff with current_diff=3

Slide window to i=2

Calculate difference for window i=2

Update min_diff with current_diff=2

Slide window to i=3

Calculate difference for window i=3

Do not update min_diff since current_diff=12 > 2

End of sliding window loop

Key Takeaways

Practice

Solution

Step 1: Sort input and initialize variables

Step 2: Iterate and count triplets

Final Answer:

Quick Check:

Solution

Step 1: Trace initial pointers and first iteration

Step 2: Value of mid after first swap

Final Answer:

Quick Check:

Solution

Step 1: Identify pointer updates after swapping 0

Step 2: Locate missing increment

Final Answer:

Quick Check:

Solution

Step 1: Understand reuse means indices can repeat

Step 2: Adjust pair combination logic

Step 3: Evaluate other options

Final Answer:

Quick Check:

Solution

Step 1: Recognize input is unsorted

Step 2: Choose a correct approach

Final Answer:

Quick Check:

Ready to prove it?