# Binary Search solution O(logN n logn)

• Time complexity is `O(logN n logn)`, where `N` is the largest possible numbers and `n` is the smaller length of `nums1` and `nums2`.

I met 378. Kth Smallest Element in a Sorted Matrix first, which is almost the same as this problem. I learnt a Binary Search method and put it into practice here.

``````require 'minitest/autorun'

class FooTest < Minitest::Test
def k_smallest_pairs(nums1, nums2, k)
return [] if [ nums1, nums2 ].any?(&:empty?)

lo = [nums1,nums2].map(&:first).reduce(:+)
hi = [nums1,nums2].map(&:last ).reduce(:+)

n1, n2 = nums1.count, nums2.count
return get_pairs_le(hi, nums1, nums2) if n1*n2 <= k

while lo < hi
mid = lo + (hi-lo)/2

# how many pairs' sums are <= mid
count = 0
nums1.each do |num|
# count += nums2.bsearch_index{|x| num + x > mid} || nums2.count
count += (0..n2-1).bsearch{|i| num + nums2[i] > mid} || nums2.count
end

# predict is count >= k

if count >= k
hi = mid
else
lo = mid + 1
end
end

par = lo

get_pairs_le(par, nums1, nums2).first(k)
end

def get_pairs_le(par, nums1, nums2)
pairs = []

nums1.each do |a|
nums2.each do |b|
pairs << [a,b] if a+b <= par
end
end

pairs.sort_by{|ar| ar.reduce(:+)}
end

def test_run
assert_equal [],                  k_smallest_pairs( [],       [2,4,6], 3 )
assert_equal [[1,2],[1,4],[1,6]], k_smallest_pairs( [1,7,11], [2,4,6], 3 )
assert_equal [[1,1],[1,1]],       k_smallest_pairs( [1,1,2],  [1,2,3], 2 )
assert_equal [[1,3],[2,3]],       k_smallest_pairs( [1,2],    [3],     3 )
end
end

``````

TODO

Understand StefanPochmann's awesome O(k) solution

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.