Binary Search solution O(logN n logn)


  • 0
    I

    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


Log in to reply
 

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