Scale Engineer

Find K Closest Elements

Med
#0612Time: O(N log N) - The dominant operation is sorting the entire array of N elements. Sorting the final k elements takes an additional O(k log k), but this is overshadowed by O(N log N).Space: O(N) - We need to create a list of Integer objects from the primitive `int` array, which requires space proportional to the number of elements N.5 companies
Patterns
Sliding WindowTwo Pointers
Algorithms
Binary SearchSorting
Data structures
ArrayHeap (Priority Queue)
Companies
AtlassianDoorDashLinkedInYandex

Prompt

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

  • |a - x| < |b - x|, or
  • |a - x| == |b - x| and a < b

 

Example 1:

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

Output: [1,2,3,4]

Example 2:

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

Output: [1,1,2,3]

 

Constraints:

  • 1 <= k <= arr.length
  • 1 <= arr.length <= 104
  • arr is sorted in ascending order.
  • -104 <= arr[i], x <= 104

Approaches

4 approaches with complexity analysis and trade-offs.

The most straightforward approach is to sort the entire array based on a custom rule. The rule is the distance of each element from x. If two elements have the same distance, the smaller element is considered closer. This method is easy to conceptualize but not the most performant.

Algorithm

    1. Convert the int[] arr to a List<Integer> to use Collections.sort.
    1. Sort the list using Collections.sort and a custom comparator.
    1. The comparator (a, b) first compares Math.abs(a - x) with Math.abs(b - x).
    1. If the absolute differences are equal, it compares a and b to handle the tie-breaker (a < b is closer).
    1. After sorting, the k closest elements are the first k elements in the list.
    1. Create a new list containing these first k elements.
    1. Sort this new list of k elements in ascending order, as the custom sort does not guarantee numerical order for elements with different distances.
    1. Return the final sorted list.

Walkthrough

This approach leverages Java's built-in sorting capabilities. We first convert the input array arr into a List<Integer> because the Collections.sort method works with lists and allows for custom comparators. The core of this method is the custom Comparator. It compares two numbers, a and b, based on their absolute difference from x. If |a - x| is not equal to |b - x|, the one with the smaller difference comes first. If the differences are equal, the problem states that the smaller number (a < b) should come first. After sorting the entire list with this logic, the k closest elements will be at the beginning of the list. We then take a sublist of the first k elements and sort it again in natural ascending order before returning it.

import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution {    public List<Integer> findClosestElements(int[] arr, int k, int x) {        List<Integer> list = new ArrayList<>();        for (int num : arr) {            list.add(num);        }         // Sort based on distance from x        Collections.sort(list, (a, b) -> {            int diffA = Math.abs(a - x);            int diffB = Math.abs(b - x);            if (diffA != diffB) {                return diffA - diffB;            } else {                return a - b;            }        });         // Take the first k elements        List<Integer> result = new ArrayList<>(list.subList(0, k));         // Sort the result in ascending order        Collections.sort(result);         return result;    }}

Complexity

Time

O(N log N) - The dominant operation is sorting the entire array of N elements. Sorting the final k elements takes an additional O(k log k), but this is overshadowed by O(N log N).

Space

O(N) - We need to create a list of Integer objects from the primitive `int` array, which requires space proportional to the number of elements N.

Trade-offs

Pros

  • Simple to understand and implement using standard library functions.

Cons

  • Highly inefficient for large arrays as it sorts the entire array, even though we only need k elements.

  • Requires extra space to convert the primitive array to a list of objects.

Solutions

class Solution { public List < Integer > findClosestElements ( int [] arr , int k , int x ) { int left = 0 ; int right = arr . length - k ; while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( x - arr [ mid ] <= arr [ mid + k ] - x ) { right = mid ; } else { left = mid + 1 ; } } List < Integer > ans = new ArrayList <>(); for ( int i = left ; i < left + k ; ++ i ) { ans . add ( arr [ i ]); } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem