Find K Closest Elements Leetcode Problem 658 [Python Solution]

If you’ve ever encountered a problem on LeetCode that requires finding the k closest elements to a target value in a sorted array, you’ll know it can be a bit tricky.

In this blog guide, we’ll break down the Find K Closest Elements problem, explore different approaches, and provide a Python solution.

We’ll also discuss the time and space complexity of the solution to help you understand its efficiency.

Problem Overview

The problem statement can be summarized as follows:

Problem Statement:

Given a sorted integer array arr, two integers k and x, your task is to 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:

1. |a - x| < |b - x|, or
2. |a - x| == |b - x|, and a < b.

Here’s an example to illustrate the problem:

Example:

Input:

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

Output:

• [1,2,3,4]

In this example, k is 4, and x is 3. The solution includes the values [1,2,3,4], which are the closest to x.

Constraints:

• 1 <= k <= arr.length
• 1 <= arr.length <= 10^4
• arr is sorted in ascending order.
• -10^4 <= arr[i], x <= 10^4

Now that we have a clear understanding of the problem, let’s explore different approaches to solving it.

Understanding the Constraints

Before diving into the solutions, it’s essential to understand the constraints mentioned in the problem.

These constraints help us determine the best approach to solving the problem efficiently.

1. 1 <= k <= arr.length: This constraint specifies that k can be any value between 1 and the length of the input array arr.

We need to consider scenarios where k is at its minimum and maximum values.

2. 1 <= arr.length <= 10^4: The length of the input array can range from 1 to 10,000 elements.

We must ensure our solution is efficient even for larger arrays.

3. arr is sorted in ascending order: The array arr is guaranteed to be sorted in ascending order.

This property will be crucial in our solution.

4. -10^4 <= arr[i], x <= 10^4: The values in the array and the target value x can range from -10,000 to 10,000. We need to handle both positive and negative values.

Now, let’s explore two different approaches to solving this problem: the brute-force approach and an efficient approach.

Brute-Force Approach

The brute-force approach involves scanning through the array, finding the index of the target value or the closest value to the target, and then expanding a window to capture the k closest elements.

Here’s a step-by-step breakdown of this approach:

1. Find the index of x or the closest value to x in the array.

This can be done using a linear search.

2. Initialize two pointers, left and right, to this index.

These pointers will be used to expand the window.

3. Start expanding the window by moving the left and right pointers towards the beginning and end of the array, respectively, to include the k closest elements.

To decide which direction to move, compare the absolute differences between the current elements at the left and right positions and the target value x.

4. Repeat the expansion process until you have k elements in the window.
5. Return the elements within the window as the result.

Here’s the Python code for the brute-force approach:

def findClosestElements(arr, k, x):
    # Step 1: Find the index of x or the closest value to x
    val, idx = arr[0], 0
    for i in range(len(arr)):
        curDiff, resDiff = abs(arr[i] - x), abs(val - x)
        if curDiff < resDiff or (curDiff == resDiff and arr[i] < val):
            val, idx = arr[i], i

    # Step 2: Initialize left and right pointers
    left, right = idx, idx

    # Step 3: Expand the window to include k closest elements
    for i in range(k - 1):
        if left == 0:
            right += 1
        elif right == len(arr) - 1 or x - arr[left - 1] <= arr[right + 1] - x:
            left -= 1
        else:
            right += 1

    # Step 4: Return the elements in the window
    return arr[left:right + 1]

The brute-force approach is relatively straightforward to understand, but it has a time complexity of O(n) due to the linear search for the target value.

In the worst case, it may need to scan the entire array.

Efficient Approach

The efficient approach leverages the sorted property of the array to perform a binary search to find the best window of k elements.

This approach is more efficient and provides a better time complexity.

Here’s how it works:

1. Initialize left and right pointers, representing the search range in the array.

The left pointer starts at 0, and the right pointer starts at len(arr) - k.

2. Perform a binary search within this range, trying to find the optimal window that contains the k closest elements to x.
3. In each iteration of the binary search, calculate the middle index mid between the left and right pointers.
4. Determine the difference between the values at mid and mid + k and the target value x.

This step helps us decide whether to move the window to the left or right.

5. Based on the difference calculations, update the left or right pointer accordingly.

If the values to the right of mid are closer, move the left pointer to mid + 1.

If the values to the left of mid are closer, move the right pointer to mid.

6. Repeat the binary search until the pointers meet.
7. Return the k elements in the identified window as the result.

The following Python code implements the efficient approach:

   def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        left, right = 0, len(arr) - k

        while left < right:
            mid = (left + right) // 2
            if x - arr[mid] > arr[mid + k] - x:
                left = mid + 1
            else:
                right = mid

        return arr[left:left + k]

The efficient approach, while slightly more complex to grasp, has a time complexity of O(log(n)) in the worst case

, which is significantly faster than the brute-force approach, especially for large arrays.

Comparing the Approaches

Now that we have two approaches to solve the problem, let’s compare their time complexity:

• Brute-Force Approach: O(n)
• Efficient Approach: O(log(n))

As you can see, the efficient approach is more scalable and performs significantly better on large datasets due to its logarithmic time complexity.

Related Interview Questions By Company:

• Single Threaded Cpu LeetCode
• Rotate List LeetCode
• Kth Smallest Element In A BST LeetCode

Related Interview Questions By Difficulty:

• Find K Closest Elements LeetCode
• Longest Repeating Character Replacement LeetCode
• Contains Duplicate II LeetCode

Related Interview Questions By Category:

• Copy List With Random Pointer LeetCode
• Find The Duplicate Number LeetCode
• Remove All Adjacent Duplicates In String II LeetCode

Conclusion

The Find K Closest Elements problem on LeetCode can be solved using both a brute-force approach and a more efficient approach that leverages binary search.

While the brute-force approach is relatively straightforward to implement, the efficient approach offers better scalability and performance, making it the preferred choice, especially for larger arrays.

I hope this explanation and Python solutions help you better understand how to tackle this problem.

Happy coding!