← Back to Index

📚 Find K Closest Elements – Java Cheat Sheet

📌 What Is It?

The Find K Closest Elements problem involves finding the K closest elements to a given target in a sorted array. The result should also be sorted in ascending order.

🧱 Pattern Template

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; // Narrow down to the right half
            } else {
                right = mid; // Narrow down to the left half
            }
        }

        List<Integer> result = new ArrayList<>();
        for (int i = left; i < left + k; i++) {
            result.add(arr[i]);
        }

        return result;
    }
}

📊 Time Complexity

• Binary Search: O(log(N - K)) – Halving the search space for the starting index.
• Result Construction: O(K) – Adding K elements to the result list.
• Overall Complexity: O(log(N - K) + K).

✅ Use Cases

• Finding the closest elements to a target in a sorted array
• Applications in recommendation systems and search engines

📘 Common LeetCode Problems

• 658. Find K Closest Elements [Medium] Binary Search

🧪 Example: Find K Closest Elements

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

Explanation:
- The 4 closest elements to 3 are [1, 2, 3, 4].

▶️ View Animation

💡 Pro Tips

• Use binary search to efficiently find the starting index of the closest elements.
• Edge cases: target outside the array bounds, duplicates in the array.
• Ensure the result is sorted in ascending order.