Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: 'K' Closest Numbers

Problem Statement

Given a sorted number array and two integers ‘K’ and ‘X’, find ‘K’ closest numbers to ‘X’ in the array. Return the numbers in the sorted order. ‘X’ is not necessarily present in the array.

Example 1:

Input: [5, 6, 7, 8, 9], K = 3, X = 7
Output: [6, 7, 8]

Example 2:

Input: [2, 4, 5, 6, 9], K = 3, X = 6
Output: [4, 5, 6]

Example 3:

Input: [2, 4, 5, 6, 9], K = 3, X = 10
Output: [5, 6, 9]

Constraints:

  • 1 <= k <= arr.length
  • 1 <= arr.length <= 10<sup>4</sup>
  • arr is sorted in ascending order.

.....

.....

.....

Like the course? Get enrolled and start learning!
J

Jayant Kumar

· 3 years ago

  public static List<Integer> findClosestElements(int[] arr, int K, Integer X) {
    
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
      (a1,a2) -> Math.abs(X-a2) - Math.abs(X-a1)
    );
    for(int n:arr){
      maxHeap.add(n);
      if(maxHeap.size()>K){
        maxHeap.poll();
      }
    }
    List<Integer> result = new ArrayList<>(maxHeap);
    Collections.sort(result);
    return result;
  }
Show 3 replies
A

Alberto Young

· 4 years ago

Why do we need:

if (low > 0) { return low - 1; }

in our binary search?

Show 7 replies
Durga Pramodh Kumar Jajala

Durga Pramodh Kumar Jajala

· 2 years ago

The question never states if the array is sorted in increasing or decreasing order. But then one of the test cases has an array in decreasing order. This breaks the logic of finding the closest value through binary search since the solution they provided, binary search algo assumes the array is increasing order.

Custom Testcase :

[12,10, 9,7,6,3,2,1] X= 4 ,K = 2

Expected Result:

[2,3] or [3,6]

Actual Result:

[9,10]

Show 1 reply
Miguel

Miguel

· 2 years ago

I would like to see more careful wording on the explanation behind using binary search.

# Binary search method to find the index of the closest element to the target

Note that this method returns either mid or low-1, meaning it returns the index of the closest element that is less than or equal to the target, not necessarily the closest (given len(arr) > 1 and there are both smaller and larger numbers in the list).

ex: binary_search([0, 1, 100, 1000, 10000], 99) => returns index 1 (despite the fact that 100 is closer)

P

Perry Robinson

· 4 years ago

Why are we making an Entry class here? I have been going through this course and looking to create a "template" for each pattern, but the addition of the Entry class or using Map.Entry for some of these patterns solutions throws me off and confuses me.

L

Lit Martian

· 4 years ago

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?

Show 3 replies
C

calvio

· 3 years ago

discuss here, thanks

S

SK

· 3 years ago

Your Input


[5,4,3,2,1]

3

3

Output

[3,2,1]

Expected

[4,2,3]

This seems incorrect.

Show 1 reply
Alex B

Alex B

· 2 years ago

Within one of the tests on Submit, we have the following:

Your Input 
[5,4,3,2,1]
3
3

Output
...

Expected
[2,3,4]

My implementation returned [4,3,2] due to an assumption from the constraints that: "arr is sorted in ascending order".

Show 1 reply
Eric Imho Jang

Eric Imho Jang

· 2 years ago

follows the same previous pattern. except that this covers an edge case as described below.

from heapq import *

class Solution:
  def findClosestElements(self, arr, K, X):
    maxHeap = []

    for i in range(len(arr)):
      difference = -abs(arr[i] - X)
      tuple = (difference, arr[i])

      # for edge cases where maxHeap is full already has K elements and there
      # already exists an element with same difference and is smaller number
      prevMaxDiff = maxHeap[0][0] if len(maxHeap) > 0 else None 
      if len(maxHeap) == K and difference == prevMaxDiff:
        continue

      heappush(maxHeap, tuple)

      if i >= K:
          heappop(maxHeap)
          
    result = []
    for i in range(len(maxHeap)):
      result.append(maxHeap[i][1])
    
    result.sort()