The O(n) Club: Find K Closest Elements and Avoid Interviewer Ambushes

The O(n) Club: Find K Closest Elements and Avoid Interviewer Ambushes

⚡ TL;DR

If you’re asked for k elements closest to x in a sorted array, don’t reach for coffee. Slide a window with binary search, don’t touch the heap, and keep the order. Here’s how Java does it without breaking a sweat:

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

🧠 How Devs Usually Mess This Up

Most folks freak out and sort the array all over again, judging each value’s distance from x with Math.abs(arr[i] - x) and then call it a day. Classic. Except that totally ignores the sorted input (which is basically the interviewer’s only hint) and spits back a scrambled mess. Worse, some devs smell a heap problem and start pushing everything onto one—congrats, you just built an O(n log k) monster. Also, many ignore the fine print: output has to match the *original order*. And ties? Pick the smaller number—no, really, that’s what the angry platform says every time.

🔍 What’s Actually Going On

Surprise! Because the array is sorted, the answer always lives in one neat, unbroken stretch. This is a window, not a puzzle. Imagine k adjacent theater seats, and your target x is a celebrity walking the aisle: park those seats so the group is huddled closest together to them. No need to leap across rows or rearrange the audience. Binary search lets you skip the awkward small talk with every possible window and find the best spot in O(log(n – k)) time.

🛠️ PseudoCode

• Set up window bounds:
  left = 0; right = arr.length - k
• Binary search for best window:
  • While left < right:
  • Find mid = (left + right) / 2
  • If x - arr[mid] > arr[mid + k] - x, slide right: left = mid + 1
  • Else, slide left: right = mid
• Return your window: Every element from arr[left] to arr[left + k - 1] (inclusive). Preserve original order—always.

💻 The Code

import java.util.*;
 public class ClosestElementsFinder {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0, right = arr.length - k;
        while (left < right) {
            int mid = (left + right) / 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;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Ties: If two numbers are the same distance from x, always pick the smaller one. Not the prettier, not the one with a LinkedIn connection—the smaller.
• Keep it in order: Output better match the input’s order or the test case bot will come knocking.
• Unsorted array?: Don’t bother with this trick. Go build a heap and lament performance elsewhere.
• Time & space: O(log(n – k)) to find where to park, plus O(k) to copy the answer. If you brute-force, pack a lunch.

🧠 Interviewer Brain-Tattoo

Sorted array? Slide a window. If your instinct is to sort again, get more sleep. Binary search: because sliding is faster than juggling.