Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Why do we need binary search in 'K' Closest Numbers? Can't we just use the absol...

Lit Martian

Mar 13, 2022

Why do we need binary search in 'K' Closest Numbers? Can't we just use the absolute difference of each number with X to build the min heap and get the top K numbers from it?

0

0

Comments
Comments
R
Ray 4 years ago

@Lit Martian, binary search lets you find the closest (or exact) match of which you are searching for the next K-1 closest values. This is done in O(log N) time.

If you check the absolute difference of each number, that takes O(N) time, which is longer.

C
CaptainKidd 2 years ago

This question is kind of an odd duck because it throws in the binary search pattern along with the Top K elements pattern when those two combined haven't really come up before yet.

If you break it down and remember the original binary search pattern we're just using t...

J
Jayant Kumar2 years ago

I think this is a better solution. by sorting priorityQueue based on distance

  public static List<Integer> findClosestElements(int[] arr, int K, Integer X) {
    
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
      (a1,a2) -> Math.abs(X-a2)...

On this page