2 sorted integer arrays,Find the Kth smallest distinct sum.[1,2,4,6] and [2,3,5,8,10] with K == 3, the answer is 5


  • 3
    I

    public int FindKthSmallestSum(int[] m, int[] n, int k)
    {

            if (m.Length == 0 || n.Length == 0 || k <=0 ) 
            {
                throw new ArgumentException("Invalid Argument");
            }
    
            var sum = m[0] + n[0];
            var rank = 1;
            var i =0;
            var j =0;
    
            while (i < m.Length && j < n.Length) 
            {
                if (m[i] + n[j] > sum)
                {
                    sum = m[i] + n[j];
                    rank++;
                }
    
                if (rank == k)
                {
                    break;
                }
    
                if (i == m.Length - 1) 
                {
                    j++;
                }
                else if (j == n.Length - 1) 
                {
                    i++;
                }
                else if(m[i +1] + n[j] > m[i] + n[j+1] )
                {
                    j++;
    
                    var tmp =  m[i] + n[j] ;
                    while (i != 0 && m[i - 1] + n[j] < tmp && m[i - 1] + n[j]  > sum) 
                    {
                        i--;
                    }
                }
                else 
                {
                    i++;
    
                    var tmp = m[i] + n[j];
                    while (j != 0 && m[i] + n[j - 1] < tmp && m[i] + n[j - 1] > sum)
                    {
                        j--;
                    }
                }
            }
    
            if (rank < k) 
            {
                throw new ArgumentException(string.Format("There is no {0}th smallest sum",k));
            }
    
            return sum;
        }

  • 0

    Do you mean the kth smallest of the union of two sorted arrays? Also, does the k starts from 0? So k == 3 actually means the 4th distinct element in ascending order, right?


  • 0
    I

    Sorry, it only allow me to input no more than 150 characters.in fact , I could describe more detail.

    Consider 2 sorted arrays of integers A[M] & B[N], where array A is of length M and array B is of length N. Assume that the lengths M and N are both extremely large.

    Write a function in Java, C, C++, or C# that can find the Kth smallest distinct sum between a number from array A and a number from array B.

    Here is a simplified example: given the arrays [1, 2, 4, 6] and [2, 3, 5, 8, 10] and the value K == 3, the answer would be 5.


  • 1
    I

    1 No. union of the distinct sum.

    e.g. A [1,2,4,6] and B [2,3,5,8,10]

    the sum array should like this [3(1+2), 4(2+2), 5(2+3), 6(1+6) .....] , the 3 rd , it's 5

    2 I thought K should start with 1


  • 0
    J

    Your logic seems has some problem on the below code from the current i and j to find the next i and j. think about the array, A = 2,3,7, 10, 20 and B 0, 3,6,8,10, when i = 1, j = 1.
    the sum is 6. from you code ,you only find the A array to get the i, which you get the next sum is 8, actually ,the next sum should be 7, so your code should be find all the next sum

    from A[0...i+1] and B[0...j+1].

    else if(m[i +1] + n[j] > m[i] + n[j+1] )
    {
    j++;

                var tmp =  m[i] + n[j] ;
                while (i != 0 && m[i - 1] + n[j] < tmp && m[i - 1] + n[j]  > sum) 
                {
                    i--;
                }
            }
            else 
            {
                i++;
    
                var tmp = m[i] + n[j];
                while (j != 0 && m[i] + n[j - 1] < tmp && m[i] + n[j - 1] > sum)
                {
                    j--;
                }
            }
        }
    

  • 0
    V

    void FindKthSmallestSum(int *arr, int *arr1, int m, int n, int &sum) {

    int k1 = 0;
    
    while (i < n && j < m && k1 != k) {
    
    	if (arr[i] >= arr1[j]) {
    		sum += arr1[j++];
    		++k1;
    	}
    
    	if (k1 == k) break;
    
    	if (arr[i] < arr1[j]) {
    		sum += arr[i++];
    		++k1;
    	}			
    }
    

    }


  • 0
    I

    Hi Buddy,

    e.g. [1, 2, 4, 6] & [2, 3, 5, 8, 10]

    When k == 1

    Your code return 1. It's incorrect


  • 0
    I

    Yes, you are right.

    Actually,I missed this case in my interview.

    Don’t know whether there is concise way to figure it out ?


  • 0
    J

    Your solution use brute force, we can use the heap O(kLogK)to fix this case, you can find information by google


  • 0
    I

    Oh I see,

    Thank you very much !


  • 1

    We can use Best First Search algorithm to solve this problem, the key idea is how to manage the states and how to generate new states. Let's say we have the following input (sorted) arrays:

    x[] = {1, 2, 4, 6}

    y[] = {2, 3, 5, 8, 10}

    The initial state contains x[0] and y[0], the sum is 3 which is the minimum sum (of course), as we know, in order to quickly know which state has the minimum sum, we can use a min heap to manage the states, so let's add the initial state to the min heap, now we complete the first step in Best First Search.

    How to generate new states? It's simple, each state knows the current index of x[] (i) and y[] (j), we just need to put (x[i], y[j+1]) and (x[i+1], y[j]) to the min heap and let it figure out what will be the next state.

    Best First Search algorithm is pretty useful in solving problems like finding k-th element from bunch of sorted input data. Below is the Java solution for this problem, we assume that k is 1-based and within a valid range.

    Time complexity is O(klog(k)).

    public class Solution {
      
      class State {
        int i;   // index of x[]
        int j;   // index of y[]
        int sum; // x[i] + y[j]
        
        public State(int i, int j, int sum) {
          this.i = i;
          this.j = j;
          this.sum = sum;
        }
      }
      
      public int findKthDistinctSum(int[] x, int[] y, int k) {
        if (x.length == 0 || y.length == 0) {
          throw new IllegalArgumentException("Can't handle zero-length arrays.");
        }
        
        // use a min heap to poll the next state that has minimum sum
        PriorityQueue<State> heap = new PriorityQueue<>(new Comparator<State>() {
          public int compare(State a, State b) {
            return a.sum - b.sum;
          }
        });
        
        // use a hash set to avoid duplicate sum
        Set<Integer> set = new HashSet<>();
        
        // step 1. create initial state
        int sum = x[0] + y[0];
        heap.offer(new State(0, 0, sum));
        set.add(sum);
        
        // step 2. generate new states based on current state
        // until we get the kth smallest sum
        while (k-- > 1) {
          State s = heap.poll();
          
          // new state 1: x[i], y[j + 1]
          if (s.j < y.length - 1) {
            sum = x[s.i] + y[s.j + 1];
            
            if (!set.contains(sum)) {
              heap.offer(new State(s.i, s.j + 1, sum));
              set.add(sum);
            }
          }
          
          // new state 2: x[i + 1], y[j]
          if (s.i < x.length - 1) {
            sum = x[s.i + 1] + y[s.j];
            
            if (!set.contains(sum)) {
              heap.offer(new State(s.i + 1, s.j, sum));
              set.add(sum);
            }
          }
        }
        
        return heap.poll().sum;
      }
      
    }
    

  • 0
    I

    Nice solution ! Thank you very much for your very clear explanation.

    I learn much from it.


  • 0

    No worries mate.


  • 0
    E

    this solution get different answers for this:
    int A[] = {1, 2, 4, 6};
    int B[] = {2, 3, 6};
    int k = 4;
    Output:
    7
    6
    Correct answer: 6
    http://ideone.com/krYZ15


  • 0
    U

    @jeantimex prove that you can produce all the unions?


Log in to reply
 

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