719. Find K-th Smallest Pair Distance

leetcode hard

#array#csharp#hard#leetcode#search#sort#two-pointers

Task

Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.

Пример:

Input: nums = [1,3,1], k = 1

Output: 0

C# solution

matched/original

public class Solution {
    public int SmallestDistancePair(int[] nums, int k) {
        Array.Sort(nums);
        int left = 0, right = nums[nums.Length - 1] - nums[0];
        while (left < right) {
            int mid = (left + right) / 2;
            if (CountPairs(nums, mid) < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    private int CountPairs(int[] nums, int mid) {
        int count = 0, j = 0;
        for (int i = 0; i < nums.Length; i++) {
            while (j < nums.Length && nums[j] - nums[i] <= mid) {
                j++;
            }
            count += j - i - 1;
        }
        return count;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int SmallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int left = 0, right = nums[nums.size() - 1] - nums[0];
        while (left < right) {
            int mid = (left + right) / 2;
            if (CountPairs(nums, mid) < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    private int CountPairs(vector<int>& nums, int mid) {
        int count = 0, j = 0;
        for (int i = 0; i < nums.size(); i++) {
            while (j < nums.size() && nums[j] - nums[i] <= mid) {
                j++;
            }
            count += j - i - 1;
        }
        return count;
    }
}

Java solution

matched/original

import java.util.Arrays;

public class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        
        int left = 0, right = nums[nums.length - 1] - nums[0];
        while (left < right) {
            int mid = (left + right) / 2;
            if (countPairs(nums, mid) < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    private int countPairs(int[] nums, int mid) {
        int count = 0, j = 0;
        for (int i = 0; i < nums.length; i++) {
            while (j < nums.length && nums[j] - nums[i] <= mid) {
                j++;
            }
            count += j - i - 1;
        }
        return count;
    }
}

JavaScript solution

matched/original

var smallestDistancePair = function(nums, k) {
    nums.sort((a, b) => a - b);
    
    const countPairs = (mid) => {
        let count = 0, j = 0;
        for (let i = 0; i < nums.length; i++) {
            while (j < nums.length && nums[j] - nums[i] <= mid) {
                j++;
            }
            count += j - i - 1;
        }
        return count;
    };
    
    let left = 0, right = nums[nums.length - 1] - nums[0];
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (countPairs(mid) < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
};

Python solution

matched/original

def smallestDistancePair(nums, k):
    nums.sort()
    
    def countPairs(mid):
        count, j = 0, 0
        for i in range(len(nums)):
            while j < len(nums) and nums[j] - nums[i] <= mid:
                j += 1
            count += j - i - 1
        return count
    
    left, right = 0, nums[-1] - nums[0]
    while left < right:
        mid = (left + right) // 2
        if countPairs(mid) < k:
            left = mid + 1
        else:
            right = mid
    return left

Go solution

matched/original

package main

import (
    "sort"
)

func countPairs(nums []int, mid int) int {
    count := 0
    j := 0
    for i := 0; i < len(nums); i++ {
        for j < len(nums) && nums[j] - nums[i] <= mid {
            j++
        }
        count += j - i - 1
    }
    return count
}

func smallestDistancePair(nums []int, k int) int {
    sort.Ints(nums)
    left, right := 0, nums[len(nums) - 1] - nums[0]
    for left < right {
        mid := (left + right) / 2
        if countPairs(nums, mid) < k {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

Explanation

Algorithm

Отсортируйте массив nums.

Определите минимальное и максимальное возможные расстояния.

Используйте бинарный поиск, чтобы найти k-е наименьшее расстояние, проверяя количество пар с расстоянием меньше или равно текущему среднему значению.

😎