Find K Closest Elements

📋

Find K Closest Elements

Edge cases:

</>

IDE

def findClosestElements(arr: list[int], k: int, x: int) -> list[int]:public List<Integer> findClosestElements(int[] arr, int k, int x)vector<int> findClosestElements(vector<int>& arr, int k, int x)function findClosestElements(arr, k, x)

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

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

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

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

Common Bugs to Avoid

Wrong: [2,3,4,5]Incorrect tie-break logic when distances are equal, choosing wrong window.✅ Compare distances at window edges and if equal, choose window with smaller left element.

Wrong: [5,6,7]Greedy approach picking closest elements individually instead of contiguous window.✅ Use binary search to find left boundary of window of size k instead of picking elements one by one.

Wrong: [2,2,3]Fails to handle duplicates properly, returning wrong elements or order.✅ Respect tie-break condition a < b when distances equal and include duplicates correctly.

Wrong: [4,5,6,7,8]Off-by-one error in binary search causing wrong window start index.✅ Adjust mid calculation and loop conditions to correctly find left boundary.

Wrong: Timeout or no outputBrute force or sliding window approach with O(n*k) complexity on large input.✅ Implement binary search on left boundary for O(log(n-k) + k) complexity.

✓

Test Cases

Focus on handling edge cases like empty arrays and single elements correctly.

Watch out for common pitfalls like greedy traps and off-by-one errors.

Optimize your solution to use binary search on the left boundary for best performance.

t1_01basic

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

Expected[1,2,3,4]

⏱ Performance - must finish in 2000ms

The four closest elements to 3 are 1, 2, 3, and 4.

💡 Consider using binary search to find the left boundary of the closest window.

💡 Check the distances between x and elements at window edges to decide which window is closer.

💡 Use binary search on the range [0, n-k] to find the best start index for the k elements.

Why it failed: Failed basic case: likely incorrect boundary search or distance comparison. Fix by ensuring binary search compares abs(arr[mid] - x) and abs(arr[mid+k] - x) correctly.

✓ Correctly finds the closest k elements using binary search on left boundary.

t1_02basic

Input{"arr":[1,3,5,7,9],"k":3,"x":6}

Expected[3,5,7]

⏱ Performance - must finish in 2000ms

The three closest elements to 6 are 3, 5, and 7.

💡 Try to find the left boundary of the window of size k that is closest to x.

💡 Compare distances at mid and mid+k elements during binary search.

💡 Return the subarray starting at the found left boundary of length k.

Why it failed: Incorrect output due to off-by-one error in binary search window boundaries. Fix by adjusting mid calculation and comparison conditions.

✓ Correctly identifies the window of closest elements around x.

t2_01edge

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

Expected[]

⏱ Performance - must finish in 2000ms

Empty array input returns empty list regardless of k and x.

💡 Check for empty input array as a base case.

💡 Return empty list immediately if arr is empty or k is zero.

💡 Avoid running binary search or window logic on empty input.

Why it failed: Fails on empty input by not handling zero-length array or k=0. Fix by adding base case to return empty list if arr is empty or k=0.

✓ Handles empty input gracefully by returning empty list.

t2_02edge

Input{"arr":[10],"k":1,"x":5}

Expected[10]

⏱ Performance - must finish in 2000ms

Single element array returns that element regardless of x.

💡 Test behavior when arr has only one element.

💡 The closest k elements when k=1 is the single element itself.

💡 Return arr directly if length equals k.

Why it failed: Fails single element case by overcomplicating or indexing out of range. Fix by returning arr if length equals k.

✓ Correctly returns single element array as closest elements.

t2_03edge

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

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

⏱ Performance - must finish in 2000ms

When k equals array length, return entire array.

💡 Check if k equals arr length as a boundary condition.

💡 Return arr immediately if k == len(arr).

💡 Avoid unnecessary binary search in this case.

Why it failed: Fails boundary condition where k equals array length by performing unnecessary search or slicing. Fix by returning arr if k == len(arr).

✓ Returns entire array when k equals array length.

t2_04edge

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

Expected[1,2]

⏱ Performance - must finish in 2000ms

x smaller than all elements returns first k elements.

💡 Check if x is smaller than the first element.

💡 Return first k elements if x is less than or equal to arr[0].

💡 Avoid binary search in this case.

Why it failed: Fails to handle x smaller than all elements by searching unnecessarily. Fix by returning arr[:k] if x <= arr[0].

✓ Correctly returns first k elements when x is smaller than all elements.

t3_01corner

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

Expected[2,2,2]

⏱ Performance - must finish in 2000ms

Array with duplicates returns closest k elements including duplicates.

💡 Handle duplicates carefully when comparing distances.

💡 Tie-break by choosing smaller element when distances equal.

💡 Binary search should find leftmost window including duplicates.

Why it failed: Fails to handle duplicates properly, returning wrong elements or order. Fix by ensuring tie-break condition a < b is respected in comparisons.

✓ Correctly returns closest elements including duplicates with proper tie-break.

t3_02corner

Input{"arr":[1,3,5,7,9],"k":2,"x":8}

Expected[7,9]

⏱ Performance - must finish in 2000ms

Greedy approach picking closest element one by one fails; correct window must be found.

💡 Beware of greedy approach picking closest elements individually.

💡 Use binary search to find window of size k instead of picking elements one by one.

💡 Compare distances at window edges to decide left boundary.

Why it failed: Fails greedy trap by selecting elements individually, not as a contiguous window. Fix by using binary search on left boundary of window.

✓ Avoids greedy trap by correctly finding window of closest elements.

t3_03corner

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

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

⏱ Performance - must finish in 2000ms

Off-by-one errors in binary search cause wrong window selection.

💡 Check binary search boundaries carefully to avoid off-by-one errors.

💡 Ensure mid calculation and loop conditions correctly narrow search space.

💡 Return subarray starting at final left boundary index.

Why it failed: Off-by-one error in binary search causes incorrect window start index. Fix by adjusting mid calculation and loop conditions to correctly find left boundary.

✓ Correctly handles binary search boundaries to find exact window.

t4_01performance

Input{"arr":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"k":50,"x":50}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 and k=50 tests O(log(n-k)+k) binary search efficiency.

💡 Use binary search on left boundary to achieve O(log(n-k) + k) time.

💡 Avoid brute force or sliding window approaches that are O(n*k).

💡 Precompute or use efficient slicing to return result.

Why it failed: TLE due to brute force or sliding window approach with O(n*k) complexity on large input. Fix by implementing binary search on left boundary for O(log(n-k)+k) complexity.

✓ Efficient binary search approach confirmed by passing performance test.

Practice

1. You are given a sorted array and need to find how many times a specific target value appears. Which algorithmic approach guarantees the most efficient solution in terms of time complexity?

easy

A. Binary search to find the left and right boundaries of the target

B. Linear scan through the array counting occurrences

C. Dynamic programming to count occurrences using subproblems

D. Greedy approach selecting elements until target count is found

Solution

1. Step 1: Understand problem constraints

   The array is sorted, so binary search can be used to find boundaries efficiently.

2. Step 2: Identify optimal approach

   Binary search for left and right boundaries finds the first and last occurrence indices in O(log n) time, enabling count calculation by subtraction.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search halves search space each step [OK]

Hint: Sorted array -> binary search boundaries [OK]

Common Mistakes:

• Using linear scan despite sorted array
• Confusing DP with counting occurrences
• Applying greedy which doesn't guarantee correctness

2. Given the following code and input nums = [2, 4, 4, 6] and target = 4, what is the final returned value?

easy

A. [1, 2]

B. [2, 3]

C. [0, 1]

D. [-1, -1]

Solution

1. Step 1: Trace binary search to find any occurrence of 4

   Initial left=0, right=3, mid=1, nums[1]=4 matches target, found=1.

2. Step 2: Expand to find leftmost and rightmost indices

   Start=1, check left: nums[0]=2 !=4 stop; end=1, check right: nums[2]=4 matches, end=2; nums[3]=6 stop.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Positions of 4 are indices 1 and 2 [OK]

Hint: Break binary search on first found, then expand boundaries [OK]

Common Mistakes:

• Off-by-one errors expanding boundaries
• Returning found index only
• Confusing indices with values

3. Given the following code snippet, what is the final return value when calling minDays([1,10,3,10,2], 3, 1)?

easy

A. 2

B. 1

C. 3

D. -1

Solution

1. Step 1: Trace binary search boundaries

   min bloom day = 1, max bloom day = 10. Binary search mid values: 5, then 3, then 2.

2. Step 2: Check feasibility at mid=5 and mid=2

   At day=5, canMake returns true (flowers bloomed on days 1,3,2). Try lower days. At day=2, canMake returns true as well. At day=1, canMake returns false. So minimum day is 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Tracing confirms minimum feasible day is 2. [OK]

Hint: Check feasibility at midpoints to narrow minimum day [OK]

Common Mistakes:

• Off-by-one errors in binary search boundaries
• Miscounting bouquets in feasibility check

4. What is the time complexity of counting occurrences of a target in a sorted array using binary search to find left and right boundaries?

medium

A. O(n) because you must scan the array to count

B. O(log n) because binary search halves the search space each step

C. O(log n * log n) because two binary searches are performed

D. O(1) because built-in functions are optimized

Solution

1. Step 1: Analyze binary search calls

   Two binary searches are performed independently, each O(log n).

2. Step 2: Combine complexities

   Total time is O(log n) + O(log n) = O(log n), since constants are ignored.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two binary searches do not multiply complexities [OK]

Hint: Two O(log n) calls sum to O(log n) [OK]

Common Mistakes:

• Confusing two calls as O(log n * log n)
• Assuming linear scan is needed
• Believing built-in functions run in O(1)

5. Examine the following buggy code snippet for finding the smallest divisor. Which line contains the subtle bug that can cause incorrect results on some inputs?

medium

A. Line with total += num // divisor

B. Line with if total > threshold:

C. Line with mid = (low + high) // 2

D. Line with low, high = 1, max(nums)

Solution

1. Step 1: Identify the purpose of is_feasible

   It sums the ceiling division of each num by divisor to check if total ≤ threshold.

2. Step 2: Spot the bug in division

   Using integer division (//) underestimates the sum because it truncates instead of rounding up.

3. Step 3: Consequence of the bug

   Underestimating sum may cause the function to incorrectly return True, leading to wrong smallest divisor.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Ceiling division needed, integer division breaks correctness -> [OK]

Hint: Ceiling division needed, integer division underestimates sum [OK]

Common Mistakes:

• Using integer division instead of ceiling
• Incorrect binary search boundaries
• Not early exiting feasibility check