Published 2024-08-14

0719. Find K-th Smallest Pair Distance

leetcode

Problem

Given an integer array nums and an integer k, return the k-th smallest distance among all the pairs in the array. The distance between a pair (i, j) is defined as |nums[i] - nums[j]|. The problem in simpler terms is to find the k-th smallest absolute difference in any two elements in the array nums.

Solution Description

To solve this problem efficiently, we need to use a combination of sorting and binary search on the possible distance values:

  1. Sort the Array:
    • Sorting the array allows us to efficiently calculate the distance between any two elements since the elements will be in ascending order. This simplifies the comparison of distances.
  2. Binary Search on the Distance:
    • The smallest possible distance (lower bound) is `0`, which occurs when there are duplicate elements in the array.
    • The largest possible distance (upper bound) is `nums[nums.length - 1] - nums[0]`, which is the difference between the largest and smallest elements in the sorted array.
    • The goal is to find the smallest distance d such that there are at least `k` pairs whose distance is ≤ d. This can be done efficiently using binary search over the range of possible distances.
  3. Count Pairs with Distance <= Mid:
    • For a given midpoint mid in the binary search, count how many pairs have a distance less than or equal to mid. This counting step is crucial as it determines the direction in which we adjust our binary search range.
    • The counting can be done in O(n) time using two pointers, which iteratively check pairs in the sorted array.

Why This Works:

  • The binary search ensures that we efficiently narrow down the possible distance values to the k-th smallest. By leveraging the sorted order of the array, we can quickly count valid pairs for each midpoint in the search, thus reducing the overall complexity of the problem.

Time Complexity:

  • Sorting the array takes O(n log n).
  • The binary search over possible distances requires O(log(max-min)), where max and min are the maximum and minimum distances respectively.
  • Counting pairs for each midpoint takes O(n) time.

Thus, the overall time complexity is O(n log n + n log(max-min)).

Example

Consider an array [1, 3, 1] and k = 1. The sorted array is [1, 1, 3]. The possible pairs and their distances are:

  • (1, 1) -> distance = 0
  • (1, 3) -> distance = 2
  • (1, 3) -> distance = 2

Since we are looking for the 1st smallest distance, the answer is 0.

Detailed Steps:

  1. Sort the array: [1, 1, 3].
  2. Use binary search to find the k-th smallest distance.
    • Start with a range of distances: low = 0, high = 2 (3 - 1).
    • Calculate the midpoint = 1.
    • Count how many pairs have a distance ≤ 1.
    • Adjust the search range based on the count and continue until the k-th smallest distance is found.

References

Solution

// Helper functions to add logs and tables
const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
const table = typeof NestedInteger!== 'undefined' ? () => {} : console.table;

/**
 * Main function to find the k-th smallest pair distance
 * @param {number[]} nums - Array of integers
 * @param {number} k - The k-th position
 * @returns {number} The k-th smallest pair distance
 */
function findKthSmallestPairDistance(nums, k) {
    // return dummy result for now

    return -1;
}

/**
 * Test cases to validate the solution
 */
const testCases = [
    { nums: [1, 3, 1], k: 1, expected: 0 },
    { nums: [1, 1, 1], k: 2, expected: 0 },
    { nums: [1, 6, 1], k: 3, expected: 5 },
    { nums: [1, 6, 1, 2], k: 4, expected: 5 },
    { nums: [1, 3, 5], k: 3, expected: 4 },
];

testCases.forEach((test, index) => {
    const result = findKthSmallestPairDistance(test.nums, test.k);
    log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});
© d)zharii. sitemap