Skip to main content

Heaps

Find K Closest Elements Solution In C++/Python/Java/JS

Problem Description

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

|a - x| < |b - x|, or
|a - x| == |b - x| and a < b

Example

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]
Explanation: Given arr = [1, 2, 3, 4, 5], k = 4, and x = 3, we need to find the 4 closest elements to 3.
The absolute differences from 3 are: ∣1−3∣=2, ∣2−3∣=1, ∣3−3∣=0, ∣4−3∣=1, ∣5−3∣=2|1 - 3| = 2.
The 4 elements with the smallest differences are [1, 2, 3, 4].
Since they are already sorted in ascending order, the result is [1, 2, 3, 4].
Thus, the output is [1, 2, 3, 4].

Input: arr = [1,1,2,3,4,5], k = 4, x = -1
Output: [1,1,2,3]
Explanation:
The absolute differences from -1 are: ∣1−(−1)∣= 2 ,  ∣ 1− (−1 ) ∣ = 2, ∣ 2− ( −1 ) ∣= 3 , ∣3−(−1)∣= 4, ∣ 4− (−1 )∣= 5, ∣ 5− (− 1 )∣ = 6.The 4 elements with the smallest differences are [1, 1, 2, 3].
Since they are already sorted in ascending order, the result is [1, 1, 2, 3].
Thus, the output is [1, 1, 2, 3].

Constraints:

  • 1 <= k <= arr.length
  • 1 <= arr.length <= 10 ^4
  • arr is sorted in ascending order.
  • -10^4 <= arr[i], x <= 10^4
💡
Try it Yourself
The goal is to find the k elements closest to a given number x in a sorted array, where "closeness" is defined by the smallest absolute difference. Since the result must contain exactly k elements and be sorted in ascending order, the challenge is to efficiently identify and extract these elements.

Brute Force Approach

Intuition

Find K Closest Elements problem involves measure of "closeness" which is defined by the absolute difference between each element in the array and the given value x. This means that smaller differences indicate that an element is closer to x.

Given that the array is already sorted, the simplest approach to of finding K Closest Elements solution is to calculate the absolute difference for each element in the array relative to x. This provides a clear metric for how far each element is from x. With these differences calculated, the next step is to sort the array based on these differences in ascending order. This ensures that the elements closest to x appear at the beginning of the array.

Once the array is sorted by the absolute differences, the first k elements can be picked as the closest elements to x. These elements represent the solution to the problem because they have the smallest differences from x.

Finally, since the problem specifies that the result should be sorted in ascending order, we need to ensure that the selected elements are arranged in ascending order. If the array was sorted by differences but disrupted the natural order of elements, a final sorting step may be required. This guarantees that the result meets all the problem’s requirements.

If multiple elements have the same absolute difference from x, how do we choose which to include?

If the differences are the same, we can use the original order of the numbers as a tiebreaker since the array is already sorted. This works naturally because sorting keeps elements in their original order when values are equal (a property called stability).

Approach

Find K Closest Elements solution can be achieved using both min-heap and max-heap. The only difference would be that in min-heap our k elements would be first k elements while in max-heap our answer would be last k elements cause max-heap stores element according to max-distance from x.

Step 1: Create a Min-Heap

  • Initialize an empty min-heap (priority queue).
  • Each element in the heap will be a pair of the form (absolute difference, element itself)
  • abs(arr[i] - x) ensures sorting based on closeness to x.
  • arr[i] is stored to maintain the original value.

Step 2: Push Elements into the Min-Heap

  • Iterate through the array and insert each element as a pair into the min-heap.

Step 3: Extract the Top k Elements

  • Pop the top k elements from the min-heap. Since the heap is sorted by absolute difference, the first k elements will be the closest to x.

Step 4: Sort the Extracted Elements

  • The k extracted elements may not be in sorted order.
  • Sort them in ascending order before returning the result.

Dry Run

Find K Closest Elements example:

arr = [1, 2, 3, 4, 5], k = 4, x = 3

Step 1: Build the Min-Heap

We push all elements into the min-heap. Each element is pushed as a pair (abs(arr[i] - x), arr[i]):

  • For arr[0] = 1:Pair = (abs(1 - 3), 1) = (2, 1)Heap = [(2, 1)]
  • For arr[1] = 2:Pair = (abs(2 - 3), 2) = (1, 2)Heap = [(1, 2), (2, 1)]
  • For arr[2] = 3:Pair = (abs(3 - 3), 3) = (0, 3)Heap = [(0, 3), (2, 1), (1, 2)]
  • For arr[3] = 4:Pair = (abs(4 - 3), 4) = (1, 4)Heap = [(0, 3), (1, 4), (1, 2), (2, 1)]
  • For arr[4] = 5:Pair = (abs(5 - 3), 5) = (2, 5)Heap = [(0, 3), (1, 4), (1, 2), (2, 1), (2, 5)]

Step 2: Extract the Top k Elements

We extract the top k = 4 elements from the min-heap:

  1. Extract the top element (0, 3):Result = [3]Heap = [(1, 2), (1, 4), (2, 5), (2, 1)]
  2. Extract the top element (1, 2):Result = [3, 2]Heap = [(1, 4), (2, 1), (2, 5)]
  3. Extract the top element (1, 4):Result = [3, 2, 4]Heap = [(2, 1), (2, 5)]
  4. Extract the top element (2, 1):Result = [3, 2, 4, 1]Heap = [(2, 5)]

Step 3: Sort the Result

The extracted elements are [3, 2, 4, 1]. After sorting in ascending order, we get:

Result = [1, 2, 3, 4]

Final Output:

[1, 2, 3, 4]

Code for All Languages
C++ 
class Solution {
public:
    // Function to find k closest elements to x
    vector<int> FindClosestElements(vector<int>& arr, int k, int x) {
        // Min-heap to store pairs of (absolute difference, element)
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> min_heap;

        // Push all elements into the min-heap with their absolute differences
        for (int i = 0; i < arr.size(); i++) {
            // Calculate absolute difference from x
            int diff = abs(arr[i] - x);

            // Push pair (difference, element) into the heap
            min_heap.push({diff, arr[i]});
        }

        // Initialize vector to store the result
        vector<int> result;

        // Extract the top k closest elements from the heap
        for (int i = 0; i < k; i++) {
            // Get the element with the smallest difference
            result.push_back(min_heap.top().second);

            // Remove the top element from the heap
            min_heap.pop();
        }

        // Sort the result in ascending order
        sort(result.begin(), result.end());

        // Return the final sorted result
        return result;
    }
};

Java 
public class Solution {

    // Method to find k closest elements to x in a sorted array
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        // Min-heap to store pairs of (absolute difference, element)
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            (a, b) -> {
                // Compare the absolute differences first, then the elements if differences are equal
                if (a[0] == b[0]) {
                    return Integer.compare(a[1], b[1]); // Sort by value if differences are the same
                }
                return Integer.compare(a[0], b[0]); // Sort by absolute difference
            }
        );

        // Step 1: Push all elements into the min-heap with their absolute differences
        for (int num : arr) {
            int diff = Math.abs(num - x); // Calculate absolute difference from x
            minHeap.offer(new int[] { diff, num }); // Push pair (difference, element)
        }

        // Step 2: Extract k closest elements from the heap
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            result.add(minHeap.poll()[1]); // Get the element with the smallest difference
        }

        // Step 3: Sort the result in ascending order
        Collections.sort(result);

        // Return the final sorted result
        return result;
    }
};

Python 
class Solution:
    def findClosestElements(self, arr, k, x):
        """
        Find k closest elements to x in a sorted array.
        
        Parameters:
        arr (List[int]): The input sorted array
        k (int): The number of closest elements to find
        x (int): The target number
        
        Returns:
        List[int]: A list of k closest elements sorted in ascending order
        """
        # Min-heap to store pairs of (absolute difference, element)
        min_heap = []
        
        # Step 1: Push all elements into the min-heap with their absolute differences
        for num in arr:
            # Calculate absolute difference from x
            diff = abs(num - x)
            # Push pair (difference, element) into the heap
            heapq.heappush(min_heap, (diff, num))
        
        # Step 2: Extract k closest elements from the heap
        result = []
        for _ in range(k):
            # Get the element with the smallest difference
            result.append(heapq.heappop(min_heap)[1])
        
        # Step 3: Sort the result in ascending order
        result.sort()
        
        # Return the final sorted result
        return result

Javascript 
class Solution {
    findClosestElements(arr, k, x) {
        const minHeap = [];
        
        // Step 1: Push all elements into the min-heap with their absolute differences
        for (const num of arr) {
            const diff = Math.abs(num - x);
            minHeap.push([diff, num]);
        }
        
        // Step 2: Sort the heap based on absolute difference and element value
        minHeap.sort((a, b) => {
            if (a[0] === b[0]) {
                return a[1] - b[1]; // Sort by element if differences are the same
            }
            return a[0] - b[0]; // Sort by absolute difference
        });
        
        // Step 3: Extract k closest elements
        const result = [];
        for (let i = 0; i < k; i++) {
            result.push(minHeap[i][1]);
        }
        
        // Step 4: Sort the result in ascending order
        result.sort((a, b) => a - b);
        
        return result;
    }
}

// Create an instance of the class.
const solution = new Solution();

// Define a global function that wraps the class method.
function findClosestElements(arr, k, x) {
    return solution.findClosestElements(arr, k, x);
}

Time Complexity Analysis of the problem : O(n log n).

  1. Building the Heap:
    We are pushing all elements from the array into the Min-Heap. Each insertion into a heap takes O(log n) time, and since there are n elements, the total time complexity for building the heap is O(n log n).
  2. Extracting k Elements from the Heap:
    Extracting an element from the heap takes O(log n) time, and we are performing this extraction k times. Therefore, the time complexity for this step is O(k log n).
  3. Sorting the Result:
    After extracting k elements, we sort the result. Sorting the k elements will take O(k log k) time.

In the worst case, when k is approximately equal to n, the complexity simplifies to:

O(3n log n) = O(n log n)

Space Complexity Analysis of the problem: O(n)

Auxiliary Space:
The primary additional space used is for the Min-Heap. The heap stores all n elements initially, so it requires O(n) space.
The operations on the heap (insertion and extraction) are done in place, and no extra space is needed for them.
Therefore, the auxiliary space complexity is O(n).

Total Space Complexity:
The total space used by the algorithm includes:
Input space: The input array (which is not counted in space complexity).
Min-Heap: The heap stores all n elements, contributing O(n) space.
Result storage: The result storage for the k closest elements, requiring O(k) space.

Since O(k) space for the result is negligible compared to O(n), the total space complexity is the sum of the heap storage and the result storage:Total space complexity = O(n) + O(k) = O(n)

How to do it using max-heap

In the context of finding the k closest elements to a target value x in a sorted array, both min-heaps and max-heaps can be utilized, each with distinct operational differences.

When employing a min-heap, the algorithm computes the absolute differences between each element and x, then inserts these differences along with their corresponding elements into the heap. The heap is structured to prioritize smaller differences, ensuring that the top of the heap always contains the element closest to x. After processing all elements, the algorithm extracts the top k elements from the heap, which are then sorted to produce the final result. This approach effectively identifies the k closest elements by leveraging the heap's property of maintaining the smallest differences at the top.

Conversely, using a max-heap involves a similar initial step of calculating absolute differences and inserting them into the heap. However, in this case, the heap is organized to prioritize larger differences, placing the element with the largest difference at the top. As the algorithm iterates through the array, it maintains a heap of size k, ensuring that only the k elements with the smallest differences remain in the heap. When a new element with a smaller difference is encountered, it replaces the element with the largest difference in the heap. After processing all elements, the heap contains the k closest elements, which are then sorted to produce the final result. This method effectively identifies the k closest elements by retaining the smallest differences and discarding larger ones.

The Min-Heap approach effectively solves the problem by maintaining a heap of k closest elements, but it involves extra space usage due to heap storage. To improve this, we can leverage the Two-Pointer approach, which directly narrows down the search space without the need for extra data structures.

Better Approach

Intuition

We know that the array is already sorted, and we are tasked with finding the k closest elements to a given value x. The key insight in this approach is that we don't need to compare every single element in the array. Instead, by using two pointers (L and R), we can focus our search on the region of the array where the closest elements are located.

The idea of Find K Closest Elements solution is to maintain a sliding window of size n (where n is the length of the array) and progressively shrink this window until it contains exactly k elements. By doing so, we can efficiently locate the k closest elements to x. The challenge here lies in determining which element to remove (either from the left or right side) at each step to reduce the window size.

How do we determine which side of the window to shrink?

If the difference between x and arr[L] (left element) is smaller than the difference between x and arr[R] (right element), it indicates that arr[L] is closer to x than arr[R]. Thus, we eliminate arr[R] from the window.

Conversely, if arr[R] is closer to x than arr[L], we eliminate arr[L].

Approach

Step 1: Initialize Pointers
Set L = 0 (left pointer).
Set R = n - 1 (right pointer), where n is the size of the array.

Step 2: Define Window
The initial window size is the full array (n elements).

Step 3: Shrink the Window Until Size Becomes k
Check if (R - L + 1) > k.
If true, compare x - arr[L] with arr[R] - x.
If x - arr[L] ≤ arr[R] - x decrement R(eliminate arr[R]).
Otherwise, increment L (eliminate arr[L]).
Repeat this process until the window size becomes exactly k.

Step 4: Extract k Closest Elements
The remaining window [L:R+1](elements in range L to (R+1) ) now contains the k closest elements to x.

Step 5: Return the Result
Return arr[L:R+1] (elements in range L to (R+1) )as the final answer.

Dry Run

Find K Closest Elements example:

Input:
arr = [1, 2, 3, 4, 5]
k = 4
x = 3

Initial State:
L = 0, R = 4 (array size = 5)
Window size = n = 5

  • Step 1:
    Check x - arr[L] = 3 - 1 = 2 vs arr[R] - x = 5 - 3 = 2
    Since both are equal, eliminate arr[R] (move R left): R = 3.
  • Step 2:
    Check x - arr[L] = 3 - 1 = 2 vs arr[R] - x = 4 - 3 = 1
    Since arr[R] is closer, eliminate arr[L] (move L right): L = 1.
  • Step 3:
    Now, L = 1 and R = 3, and the window size is k = 4.

The subarray [2, 3, 4, 5] is the result.

Code for All Languages
C++ 
class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int L = 0, R = size(arr) - 1;
        
        // Shrink the window until it contains exactly k elements
        while (R - L >= k) {
            if (x - arr[L] <= arr[R] - x) {
                R--; // Eliminate arr[R] if arr[L] is closer
            } else {
                L++; // Eliminate arr[L] if arr[R] is closer
            }
        }
        
        // Return the subarray with k closest elements
        return vector<int>(begin(arr) + L, begin(arr) + R + 1);
    }
};

Java 
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int L = 0, R = arr.length - 1;

        // Shrink the window until it contains exactly k elements
        while (R - L >= k) {
            if (Math.abs(x - arr[L]) <= Math.abs(arr[R] - x)) {
                R--; // Eliminate arr[R] if arr[L] is closer
            } else {
                L++; // Eliminate arr[L] if arr[R] is closer
            }
        }

        // Create the result list with the k closest elements
        List<Integer> result = new ArrayList<>();
        for (int i = L; i < L + k; i++) {
            result.add(arr[i]);
        }
        return result;
    }
};

Python 
class Solution:
    def findClosestElements(self, arr, k, x):
        # Initialize two pointers for the window
        L, R = 0, len(arr) - 1
        
        # Shrink the window until it contains exactly k elements
        while R - L >= k:
            if abs(x - arr[L]) <= abs(arr[R] - x):
                R -= 1  # Eliminate arr[R] if arr[L] is closer
            else:
                L += 1  # Eliminate arr[L] if arr[R] is closer
        
        # Return the subarray with k closest elements
        return arr[L:L + k]

Javascript 
class Solution {
    /**
     * Find k closest elements to x in a sorted array.
     * 
     * @param {number[]} arr - The input sorted array
     * @param {number} k - The number of closest elements to find
     * @param {number} x - The target number
     * @return {number[]} - A list of k closest elements
     */
    findClosestElements(arr, k, x) {
        // Initialize two pointers for the window
        let L = 0, R = arr.length - 1;
        
        // Shrink the window until it contains exactly k elements
        while (R - L >= k) {
            if (Math.abs(x - arr[L]) <= Math.abs(arr[R] - x)) {
                R--; // Eliminate arr[R] if arr[L] is closer
            } else {
                L++; // Eliminate arr[L] if arr[R] is closer
            }
        }
        
        // Return the subarray with k closest elements
        return arr.slice(L, L + k);
    }
};

Time Complexity Analysis of the problem :O(n - k)

We start with a window of size n and reduce it to size k. In each iteration, we make a comparison and either increment L or decrement R. This process continues until the window is reduced to exactly k elements, requiring n - k comparisons in the worst case.

Therefore, the overall time complexity is O(n - k), which can be simplified to O(n) in the worst case.

Space Complexity Analysis of the problem : O(k)

  1. Auxiliary Space Complexity: O(1):

The algorithm only uses a few integer variables (L, R) and no additional data structures, so the auxiliary space is constant.

  1. Total Space Complexity: O(k):

The total space includes the space for the input array arr (which is not counted in the space complexity) and the space for the output (the result array containing the k closest elements). The result array requires O(k) space to store the k closest elements.

Therefore, the total space complexity is O(k).

Although the 2-Pointer approach is efficient in terms of space (O(1)) and provides an intuitive way to reduce the window size until the exact k closest elements are identified, it still requires a linear pass through the array.

Optimal Approach

Intuition

Now, let’s translate Find K Closest Elements problem solution into a real-world analogy.We are looking at a row of items, each with a price. Our goal is to pick the k items that are closest to our target price, and the items are already sorted in increasing price.

 How do we choose the best starting point to pick the k closest items?

If we started picking items from anywhere in the row, we could end up picking items that are far from our target price. So, the first thing to ask is:"Can we make this selection more efficient?"

Binary Search Comes In

Since the items are sorted by price, we don’t have to check every possible combination of items. Instead, we can zoom in on the area of the row where the items are closest to our target price.

Approach

Step 1: Initial Setup
Set l = 0 (left boundary).
Set r = arr.size() - k (right boundary, ensuring a window of size k fits within the array).

Step 2: Perform Binary Search
Check if l < r.
Compute the midpoint m = l + (r - l) / 2.
Compare the distances between x and the elements at m (left boundary of the window) and m + k (right boundary of the window).
If x - arr[m] <= arr[m + k] - x, set r = m (narrow search to the left side).
Otherwise, set l = m + 1 (narrow search to the right side).
Repeat the process until l == r.

Step 3: Extract the Result
l now points to the start of the optimal subarray.
Return the subarray from l to l + k.

Why are we setting right boundary as total_size - k?

  • r = arr.size() - k ensures that when we pick the starting index l of the window of k elements, the subarray of size k starting at l doesn't exceed the bounds of the array.

If r were set to arr.size(), it would allow us to pick starting indices that could lead to subarrays of size less than k (which isn’t valid).

For example, if arr.size() is 5 and k is 4, the valid starting indices for a subarray of size 4 are 0 and 1. If r were set to arr.size() (5), we could choose index 4 as the starting point, but this would give a subarray of size 1, which is incorrect.

Thus, r = arr.size() - k ensures that, at most, the subarray starting at r will have exactly k elements, and it helps in constraining the binary search to only valid subarray positions.

Why the given conditions for trimming lower and upper limit?

if (x - arr[m] <= arr[m + k] - x) {

r = m; // Narrow down the search space to the left half

} else { l = m + 1; // Narrow down the search space to the right half

}

  • The key goal is to find the starting index of the subarray that contains the k closest elements to x.
  • We want to determine whether the window of k elements starting from m is closer to x than the window starting from m+1.

The Condition:

  • x - arr[m]: This is the distance between x and the element at index m (the left boundary of the current window).
  • arr[m + k] - x: This is the distance between x and the element at index m + k (the right boundary of the window that would start at index m and contain k elements).

Why this works:

  1. If x - arr[m] <= arr[m + k] - x:

The subarray starting at index m (i.e., from arr[m] to arr[m+k-1]) is closer to x than the subarray starting at index m+1.

This happens because the left boundary arr[m] is closer to x than the right boundary arr[m+k], so it's more beneficial to pick the subarray starting from m.

Therefore, we narrow the search space to the left half by updating r = m.

  1. If x - arr[m] > arr[m + k] - x:

The subarray starting at index m+1 (i.e., from arr[m+1] to arr[m+k]) is closer to x than the subarray starting at index m.

This happens because the right boundary arr[m + k] is closer to x than arr[m], so it’s better to move to the right half to search for the optimal starting index.

Therefore, we narrow the search space to the right half by updating l = m + 1.

Dry Run

Find K Closest Elements example:

  • Input: arr = [1, 2, 3, 4, 5]
  • k = 4
  • x = 3

Initial Setup:

  • We have the sorted array: arr = [1, 2, 3, 4, 5]
  • The left boundary (l) is set to 0, and the right boundary (r) is set to arr.size() - k = 5 - 4 = 1.

We aim to find the starting index of the k closest elements to x = 3.

Step-by-Step Dry Run:

Iteration 1:

  • l = 0, r = 1
  • Compute the midpoint:m = l + (r - l) / 2 = 0 + (1 - 0) / 2 = 0
  • Compare distances:

Left boundary distance: x - arr[m] = 3 - arr[0] = 3 - 1 = 2

Right boundary distance: arr[m + k] - x = arr[0 + 4] - 3 = arr[4] - 3 = 5 - 3 = 2

Condition check:

x - arr[m] (2) <= arr[m + k] - x (2), so the condition is true.

This means the subarray starting at m = 0 is closer to x or equally close as the subarray starting at m + 1.

Hence, we update r = m, so now r = 0.

Iteration 2:

  • l = 0, r = 0
  • The condition l < r is no longer satisfied, so the binary search loop terminates.

Final Step:

  • The binary search loop has ended, and l = 0.
  • The starting index of the k closest elements is l = 0.
  • We return the subarray starting from arr[l] with k elements:return vector<int>(arr.begin() + l, arr.begin() + l + k);
  • This results in the subarray: [1, 2, 3, 4]

Result:

  • The output is [1, 2, 3, 4].

Conclusion:

  • The binary search approach efficiently narrows down the starting index for the subarray of size k that contains the k closest elements to x in arr.
  • In this case, the subarray starting from index 0 provides the closest 4 elements to x = 3.
Code for All Languages
C++ 
class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        // Initialize the left and right pointers for binary search
        int l = 0;  // Left boundary of the search space
        int r = arr.size() - k;  // Right boundary to ensure we can pick exactly k elements
        
        // Perform binary search to find the optimal starting index of the k closest elements
        while (l < r) {
            // Calculate the mid-point of the current search space
            int m = l + (r - l) / 2;
            
            // Compare the distances from x to the elements at m and m + k
            if (x - arr[m] <= arr[m + k] - x) {
                // If the left boundary is closer or equally close to x, move the right pointer to m
                r = m;  // Narrow down the search space to the left half
            } else {
                // Otherwise, move the left pointer to m + 1
                l = m + 1;  // Narrow down the search space to the right half
            }
        }
        
        // After the binary search loop, 'l' will point to the start of the k closest elements
        // Return the subarray starting from index 'l' with exactly 'k' elements
        return vector<int>(arr.begin() + l, arr.begin() + l + k);
    }
};

Java 
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        // Initialize the left and right pointers for binary search
        int l = 0;  // Left boundary of the search space
        int r = arr.length - k;  // Right boundary to ensure we can pick exactly k elements
        
        // Perform binary search to find the optimal starting index of the k closest elements
        while (l < r) {
            // Calculate the mid-point of the current search space
            int m = l + (r - l) / 2;
            
            // Compare the distances from x to the elements at m and m + k
            if (x - arr[m] <= arr[m + k] - x) {
                // If the left boundary is closer or equally close to x, move the right pointer to m
                r = m;  // Narrow down the search space to the left half
            } else {
                // Otherwise, move the left pointer to m + 1
                l = m + 1;  // Narrow down the search space to the right half
            }
        }
        
        // After the binary search loop, 'l' will point to the start of the k closest elements
        // Return the subarray starting from index 'l' with exactly 'k' elements
        List<Integer> result = new ArrayList<>();
        for (int i = l; i < l + k; i++) {
            result.add(arr[i]);
        }
        return result;
    }
};

Python 
class Solution:
    def findClosestElements(self, arr, k, x):
        # Initialize the left and right pointers for binary search
        l, r = 0, len(arr) - k  # 'r' is set to len(arr) - k to ensure we can pick exactly k elements
        
        # Perform binary search to find the optimal starting index of the k closest elements
        while l < r:
            # Calculate the mid-point of the current search space
            m = l + (r - l) // 2
            
            # Compare the distances from x to the elements at m and m + k
            if x - arr[m] <= arr[m + k] - x:
                # If the left boundary is closer or equally close to x, move the right pointer to m
                r = m  # Narrow down the search space to the left half
            else:
                # Otherwise, move the left pointer to m + 1
                l = m + 1  # Narrow down the search space to the right half
        
        # After the binary search loop, 'l' will point to the start of the k closest elements
        # Return the subarray starting from index 'l' with exactly 'k' elements
        return arr[l:l + k]

Javascript 
class Solution {
    /**
     * Find k closest elements to x in a sorted array using binary search.
     * 
     * @param {number[]} arr - The input sorted array
     * @param {number} k - The number of closest elements to find
     * @param {number} x - The target number
     * @return {number[]} - A list of k closest elements
     */
    findClosestElements(arr, k, x) {
        // Initialize the left and right pointers for binary search
        let l = 0, r = arr.length - k; // 'r' is set to arr.length - k
        
        // Perform binary search to find the optimal starting index of the k closest elements
        while (l < r) {
            // Calculate the mid-point of the current search space
            const m = Math.floor(l + (r - l) / 2);
            
            // Compare the distances from x to the elements at m and m + k
            if (x - arr[m] <= arr[m + k] - x) {
                // If the left boundary is closer or equally close to x, move the right pointer to m
                r = m; // Narrow down the search space to the left half
            } else {
                // Otherwise, move the left pointer to m + 1
                l = m + 1; // Narrow down the search space to the right half
            }
        }
        
        // After the binary search loop, 'l' will point to the start of the k closest elements
        // Return the subarray starting from index 'l' with exactly 'k' elements
        return arr.slice(l, l + k);
    }
}

// Create an instance of the class
const solution = new Solution();

// Define the global function
function findClosestElements(arr, k, x) {
    return solution.findClosestElements(arr, k, x);
}

Time Complexity Analysis of the problem : O(log(n - k) ) + O(k)

  1. Binary Search (O(log(n - k))):
    We perform a binary search to find the optimal starting index for the k closest elements. Since we are searching within a reduced range from 0 to len(arr) - k, the search space is effectively reduced to n - k.
    Binary search reduces the search space by half in each iteration, resulting in a time complexity of O(log(n - k)).
  2. Extracting k Elements (O(k)):
    After completing the binary search, we extract the k closest elements starting from index l. Extracting a subarray of size k takes O(k) time.
  3. Total Time Complexity:
    O(log(n - k)) for the binary search step.
    O(k) for creating the subarray.

Therefore, the overall time complexity is: O(log(n - k) + k)

Space Complexity Analysis of the problem :  O(k)

  1. Auxiliary Space Complexity (O(1)):
    The algorithm uses only a constant amount of extra space for the integer variables l, r, and m. These do not depend on the size of the input array, so the auxiliary space complexity is O(1).
  2. Total Space Complexity (O(k)):
    The total space complexity includes:
    The input array, which is not counted in space complexity.
    The output list, which stores the k closest elements and requires O(k) space.

Thus, the total space complexity is primarily determined by the space needed to store the result. Total space complexity = O(k)

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

Similar Problems

Guess Number Higher or Lower

The problem is a number guessing game where you need to determine the number that I have picked, which lies between 1 and n. You make guesses using a pre-defined API guess(num), which returns whether your guess is higher, lower, or equal to the number I picked. The goal is to find the number I picked using this feedback.

Find K-th Smallest Pair Distance

The problem asks to find the kth smallest distance between any pair of integers in a given array nums. The distance between two numbers a and b is defined as the absolute difference |a - b|. The task is to return the kth smallest distance among all the unique pairs in the array where the indices i and j satisfy 0 <= i < j < nums.length.