Find K Closest Elements

▶

Steps

setup

Initialize low and high pointers

Set low to 0 and high to n - k (1 in this case) to define the initial search space for the starting index of the closest elements.

💡 This initialization sets the boundaries for where the k-length subarray can start within the array.

Line:

low, high = 0, len(arr) - k

💡 The search space is limited to valid starting indices for subarrays of length k.

compare

Calculate mid index

Calculate mid as the floor of (low + high) / 2, which is 0, to test if the subarray starting at index 0 is closer to x.

💡 Mid divides the current search space to decide which half to keep.

Line:

mid = (low + high) // 2

💡 Mid is the candidate starting index for the closest elements subarray.

compare

Compare distances at mid and mid + k

Compare distance from x to arr[mid] (3 - 1 = 2) and distance from arr[mid + k] to x (5 - 3 = 2) to decide which side to eliminate.

💡 This comparison determines if the subarray starting at mid is closer or if we should move right.

Line:

if x - arr[mid] > arr[mid + k] - x:

💡 Equal distances mean we prefer the left side, so we reduce high to mid.

shrink

Update high pointer

Since the left side is preferred, update high to mid (0), shrinking the search space to a single index.

💡 Adjusting high narrows the search space to the left half.

Line:

high = mid

💡 The search space is now a single index, so the loop will end.

compare

Check loop condition

Check if low < high (0 < 0), which is false, so exit the loop to finalize the answer.

💡 Loop ends when search space cannot be reduced further.

Line:

while low < high:

💡 The final low pointer is the starting index of the closest elements.

reconstruct

Return the k closest elements subarray

Return the subarray starting at low (0) with length k (4), which is [1, 2, 3, 4].

💡 The final subarray is the answer to the problem.

Line:

return arr[low:low + k]

💡 The algorithm efficiently found the closest elements without scanning the entire array.

reconstruct

Confirm final answer index and value

The answer index is 0 and the answer value is the subarray [1, 2, 3, 4].

💡 This confirms the exact location and content of the closest elements.

Line:

answer = arr[low:low + k]

💡 The final step ties the binary search result to the output format.

prune

Summary of search space reduction

The search space was reduced from indices [0,1] to [0,0] by eliminating the right side based on distance comparison.

💡 This shows the power of binary search in pruning the search space efficiently.

Line:

N/A - conceptual step

💡 Each comparison halves the search space, leading to O(log(n-k)) complexity.

prune

Visualize eliminated indices

Index 1 is grayed out to indicate it was eliminated from the search space after the comparison.

💡 Visualizing eliminated indices helps track which parts of the array are no longer considered.

Line:

N/A - visualization detail

💡 Eliminated indices show the shrinking search space clearly.

reconstruct

End of algorithm

The algorithm ends with low = 0, returning the subarray [1, 2, 3, 4] as the k closest elements to x.

💡 The final step confirms the algorithm's correctness and efficiency.

Line:

return arr[low:low + k]

💡 The binary search approach finds the closest elements in O(log(n-k)) time.

from typing import List

def findClosestElements(arr: List[int], k: int, x: int) -> List[int]:
    low, high = 0, len(arr) - k  # STEP 1
    while low < high:  # STEP 5
        mid = (low + high) // 2  # STEP 2
        if x - arr[mid] > arr[mid + k] - x:  # STEP 3
            low = mid + 1  # STEP 4 (if branch)
        else:
            high = mid  # STEP 4 (else branch)
    return arr[low:low + k]  # STEP 6

if __name__ == '__main__':
    print(findClosestElements([1,2,3,4,5], 4, 3))  # Output: [1,2,3,4]

📊

Find K Closest Elements - Watch the Algorithm Execute, Step by Step

Watching each pointer move and comparison helps you understand how the algorithm efficiently finds the closest elements without scanning the entire array.

Target: 3

lo

1

0

hi

2

1

3

2

4

3

5

4

Next: lo=0 hi=1

Target: 3

lo/mid

1

0

hi

2

1

3

2

4

3

5

4

mid[0]=1

Next: lo=0 hi=1

Target: 3

lo/mid

1

0

hi

2

1

3

2

4

3

5

4

mid[0]=1 - x - arr[mid] (2) <= arr[mid + k] - x (2), move high to mid

Next: lo=0 hi=0

Target: 3

lo/mid/hi

1

0

2

1

3

2

4

3

5

4

mid[0]=1 - high updated to mid

Next: lo=0 hi=0

Target: 3

lo/hi

1

0

2

1

3

2

4

3

5

4

Next: lo=0 hi=0

Target: 3

lo/hi

1

0

2

1

3

2

4

3

5

4

Next: lo=0 hi=0

Target: 3

lo/hi

1

0

2

1

3

2

4

3

5

4

Next: lo=0 hi=0

Target: 3

lo/hi

1

0

2

1

3

2

4

3

5

4

Next: lo=0 hi=0

Target: 3

lo/hi

1

0

2

1

3

2

4

3

5

4

Next: lo=0 hi=0

Target: 3

lo/hi

1

0

2

1

3

2

4

3

5

4

Next: lo=0 hi=0

Key Takeaways

✓ Binary search efficiently finds the starting index of the k closest elements by comparing distances at mid and mid + k.

This insight is hard to see from code alone because it requires understanding how the search space represents subarray start indices.

✓ The algorithm eliminates half of the search space each iteration by comparing which boundary is farther from x.

Visualizing eliminated indices clarifies how the search space shrinks, which is not obvious from reading code.

✓ When distances are equal, the algorithm prefers the left side, ensuring the closest elements are chosen with a stable tie-break.

This subtle decision is critical for correctness and is easier to grasp when watching the step-by-step comparison.

Practice

1. Consider the following code snippet implementing the binary search on value range approach to find the median of two sorted arrays. Given nums1 = [1, 3] and nums2 = [2, 4], what is the final returned median?

easy

A. 2.0

B. 2.5

C. 3.0

D. 2.25

Solution

1. Step 1: Trace binary search iterations

   Initial left=1, right=4. Mid=2, countLessEqual(2)=3 ≥ 2.5 so right=2. Next mid=1, countLessEqual(1)=1 < 2.5 so left=2.

2. Step 2: Compute median for even total length

   Left=2, total length=4 (even). Candidates before 2 are nums1[0]=1 and nums2[0]=2, max=2. Median=(2+3)/2=2.5 is correct median of combined sorted array [1,2,3,4]. The code snippet's logic is incomplete but assuming correct logic, median is 2.5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Median of combined sorted array [1,2,3,4] is 2.5 [OK]

Hint: Median of [1,2,3,4] is average of 2 and 3 [OK]

Common Mistakes:

• Off-by-one in bisect boundaries
• Confusing left with median
• Ignoring even length median averaging

2. What is the time complexity of the optimal binary search with early stopping feasibility check approach for the Capacity to Ship Packages problem, where n is the number of packages and S is the sum of all package weights?

medium

A. O(n * S) because we check all capacities from max weight to sum weights

B. O(n log S) because binary search reduces capacity range and feasibility check is linear

C. O(n^2) because feasibility check may scan packages multiple times

D. O(log n * S) because binary search is on number of packages and capacity sum

Solution

1. Step 1: Identify binary search iterations

   Binary search on capacity range S takes O(log S) steps.

2. Step 2: Analyze feasibility check cost

   Feasibility check scans all n packages once per binary search iteration -> O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search x linear feasibility check -> O(n log S) [OK]

Hint: Binary search log factor times linear feasibility check [OK]

Common Mistakes:

• Confusing linear scan with quadratic
• Thinking feasibility check is O(log S)
• Assuming binary search on packages not capacity

3. What is the worst-case time complexity of the optimal modified binary search algorithm to find the minimum in a rotated sorted array with duplicates?

medium

A. O(n log n)

B. O(log n)

C. O(n)

D. O(1)

Solution

1. Step 1: Understand binary search with duplicates

   Duplicates can cause the algorithm to reduce high by one each iteration when nums[mid] == nums[high], leading to linear scan behavior.

2. Step 2: Analyze worst-case scenario

   In worst case (all elements equal), the algorithm degrades to O(n) because it may shrink high by one each time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Duplicates cause worst-case linear time [OK]

Hint: Duplicates cause worst-case linear time despite binary search [OK]

Common Mistakes:

• Assuming always O(log n)
• Confusing average and worst case

4. What is the time complexity of the optimal binary search solution for finding the minimum speed to arrive on time, given n distances and a precision epsilon for floating point speed search?

medium

A. O(log n * (maxSpeed / epsilon))

B. O(n * maxSpeed)

C. O(n^2 * log(maxSpeed))

D. O(n * log((maxSpeed - minSpeed) / epsilon))

Solution

1. Step 1: Identify the binary search iterations

   Binary search on speed range [minSpeed, maxSpeed] with precision epsilon takes O(log((maxSpeed - minSpeed)/epsilon)) steps.

2. Step 2: Calculate per-iteration cost

   Each feasibility check sums over n distances, so O(n) per iteration.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Combining steps yields O(n log((maxSpeed - minSpeed)/epsilon)) [OK]

Hint: Binary search iterations times linear feasibility check [OK]

Common Mistakes:

• Confusing maxSpeed with n
• Ignoring epsilon precision in log factor

5. Suppose the problem is modified so that packages can be shipped in any order (not necessarily the given order) within the given days. Which of the following approaches correctly finds the minimal ship capacity under this new constraint?

hard

A. Use dynamic programming to assign packages to days minimizing maximum load per day, combined with binary search on capacity

B. Sort packages in descending order and use a greedy bin-packing heuristic combined with binary search on capacity

C. Use a simple greedy approach assigning packages to days in any order without binary search

D. Use the same binary search on capacity with the original feasibility check since order doesn't matter

Solution

1. Step 1: Understand the relaxed constraint

   Packages can be shipped in any order, so the problem becomes a variant of multi-way partition or bin packing minimizing max load.

2. Step 2: Identify correct approach

   Binary search on capacity still applies, but feasibility check requires DP or backtracking to assign packages optimally to days, as greedy heuristics may fail.

3. Step 3: Why other options fail

   Original feasibility check assumes fixed order; greedy heuristics are approximate and may not find minimal capacity.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP feasibility check with binary search needed for unordered assignment [OK]

Hint: Order relaxation requires DP feasibility check, not simple greedy [OK]

Common Mistakes:

• Using original feasibility check ignoring order change
• Assuming greedy suffices
• Ignoring complexity increase