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!
L

lejafilip

· 2 years ago

This is next problem where Heap isn't the most optimal solution so we shouldn't be forced to use it. When you are looking for solution you are looking for something with heap, because it is in heap chapter but this isn't enough. I commit my heaps solution in LC and got "memory limit exceeded". Propably it won't be accepted at interview.

Guys you should fix that because this course isn't worthy at all.

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()
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
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)

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
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
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
C

calvio

· 3 years ago

discuss here, thanks

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.

A

Alberto Young

· 4 years ago

Why do we need:

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

in our binary search?

Show 7 replies

Reading Progress

0%