We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find K Closest Elements

Difficulty: Medium

Problem Description

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

Key Insights

  • The array is sorted, allowing for efficient searching techniques.
  • The problem can be approached using binary search to find the closest element.
  • Once the closest element is found, a two-pointer technique can be used to gather the k closest elements.
  • The returned elements must be sorted, which is guaranteed by the nature of the input array.

Space and Time Complexity

Time Complexity: O(log(N) + k)
Space Complexity: O(1) (if we return the results in a new array, space used is O(k))

Solution

The solution involves using binary search to find the position of the closest number to x in the sorted array. From that position, we can then utilize a two-pointer technique to find and collect k closest elements. The pointers will move inward from the closest position, allowing us to compare and select the closest elements efficiently.

Code Solutions

def findClosestElements(arr, k, x):
    # Binary search to find the closest element to x
    left, right = 0, len(arr) - 1
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < x:
            left = mid + 1
        else:
            right = mid
    # left is now the insert position for x
    left = left - 1
    right = left + 1
    
    # Collect k closest elements
    result = []
    for _ in range(k):
        if left < 0:  # If left pointer is out of bounds
            result.append(arr[right])
            right += 1
        elif right >= len(arr):  # If right pointer is out of bounds
            result.append(arr[left])
            left -= 1
        else:  # Both pointers are within bounds
            if abs(arr[left] - x) <= abs(arr[right] - x):
                result.append(arr[left])
                left -= 1
            else:
                result.append(arr[right])
                right += 1
    
    return sorted(result)  # Return the result sorted
← Back to All Questions