algoadvance

Leetcode 658. Find K Closest Elements

Problem Statement

Given a sorted integer array arr, two integers k and x, find the k closest integers to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Clarifying Questions

  1. Can x be outside the range of elements in arr?
    • Yes, x can be any integer, not necessarily within the range of elements in arr.
  2. What should we return if there are fewer than k elements in arr?
    • It’s given that k will always be valid, i.e., 1 <= k <= arr.length.
  3. Can there be duplicate elements in arr?
    • Yes, the array may contain duplicate elements.

Strategy

  1. Binary Search for Closest Element: Use binary search to locate the position in the array where x would fit if inserted. This helps in finding the potential starting point for the closest elements.

  2. Two pointers to find closest elements: After finding the position, use two pointers to find the k closest elements:
    • Initialize two pointers left and right at this position.
    • Expand the window to the left and right to include the k closest elements based on the absolute difference from x.
  3. Sort the Result: Since we need to return the elements in ascending order, simply sorting the resultant array of k elements might be necessary, but since the array is already sorted, the selected window will also be sorted correctly.

Code

#include <vector>
#include <algorithm>
#include <cstdlib>

class Solution {
public:
    std::vector<int> findClosestElements(std::vector<int>& arr, int k, int x) {
        int left = 0;
        int right = arr.size() - 1;
        while (right - left >= k) {
            if (abs(arr[left] - x) > abs(arr[right] - x)) {
                left++;
            } else {
                right--;
            }
        }
        return std::vector<int>(arr.begin() + left, arr.begin() + right + 1);
    }
};

Explanation

  1. Binary Search for Closest Element: Here the binary search is implicitly used to balance the left and right borders by checking the difference |arr[left] - x| and |arr[right] - x|.
  2. Window Adjustment: The while loop keeps shrinking the search window until its size is exactly k. If the element at left is less close to x than the element at right, increment left; otherwise, decrement right.
  3. Extract the Result: Finally, a subarray from arr[left] to arr[right] inclusive is returned as the result.

Time Complexity

  1. Binary Search: Although this is not explicitly a binary search over positions, the while loop mimics a binary search mechanism over window size reductions.
    • The while loop runs in O(n - k) operations, where n is the size of the array.
  2. Extraction of Subarray: Copying the result array takes O(k).

So, the overall time complexity is O(n - k + k) = O(n), but since we are performing the bulk of operations within the while loop it’s more meaningful to consider the complexity as O(n - k).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI