LeetCode 658: Find K Closest Elements Solution

Master LeetCode problem 658 (Find K Closest Elements), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

658. Find K Closest Elements

Medium

Array Two Pointers Binary Search Sliding Window Sorting Heap (Priority Queue)

Problem Explanation

Explanation

To find the k closest elements to x in a sorted array, we can use a binary search approach. We can find the index of the element closest to x using binary search, then expand around that index to find the k closest elements. We can use a two-pointer approach to maintain a window of size k around the closest element.

Perform a binary search to find the index of the element closest to x.
Use two pointers to expand around this index and select the k closest elements.
Keep track of the window using the two pointers and return the elements within this window.

Time Complexity: O(log(n) + k) where n is the length of the array arr. Space Complexity: O(1)

Solution Code

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0, right = arr.length - k;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        List<Integer> result = new ArrayList<>();
        for (int i = left; i < left + k; i++) {
            result.add(arr[i]);
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 658 (Find K Closest Elements)?

This page provides optimized solutions for LeetCode problem 658 (Find K Closest Elements) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 658 (Find K Closest Elements)?

The time complexity for LeetCode 658 (Find K Closest Elements) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 658 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 658 in Java, C++, or Python.

Back to LeetCode Solutions