Comment hidden because of low score. Click to expand.
2
of 2 vote

1. Sort both arrays in descending order

``````/* Insert A + B into max heap */
max_heap.put(0, 0, A+B);
while (--k) {
p = max_heap.get();

if (p.a_index < p.b_index) {
sum = A[p.a_index] + B[p.b_index+1];
max_heap.put(make_pair(p.a_index, p.b_index+1, sum));
} else if (p.a_index > p.b_index) {
sum = A[p.a_index+1] + B[p.b_index];
max_heap.put(make_pair(p.a_index+1, p.b_index, sum));
sum = A[p.a_index] + B[p.b_index+1];
max_heap.put(make_pair(p.a_index, p.b_index+1, sum));
sum = A[p.a_index+1] + B[p.b_index];
max_heap.put(make_pair(p.a_index+1, p.b_index, sum));
}
}

p = max_hep.get();
sum = A[p.a_index] + B[p.b_index];
printf("kth max sum is formed by A[%d] + B[%d] = %d\n", p.a_index, p.b_index, sum);``````

Comment hidden because of low score. Click to expand.
0

you missed 1
else {
sum = A[p.a_index+1] + B[p.b_index+1];
max_heap.put(make_pair(p.a_index+1, p.b_index+1, sum));
}

Comment hidden because of low score. Click to expand.
0

@BIN: this case will be covered by existing conditions.

Comment hidden because of low score. Click to expand.
0

@mytestaccount2: BIN is right, did you actually try your code? (e.g. A = [ 9, 8, 1], B = [9, 3, 1]). You are always increasing the gap between the two indexes: a_index and b_index, so you will miss the A + B pair. Just look at the code: if a_index < b_index you increment again b_index, and when a_index > b_index you again increment a_index; so except for the initial case a_index = b_index = 0, they'll never be the same.

Comment hidden because of low score. Click to expand.
0
of 0 vote

can you please rephrase the question? It's not understandable.
thanks

Comment hidden because of low score. Click to expand.
0
of 0 vote

Is it Kth sum of 2 elements where each elements are picking from both arrays?

Comment hidden because of low score. Click to expand.
0
of 0 vote

If i got it correctly then there will be two arrays sorted/unsorted now we need to find out sum of elements which will be kth largest....
If this is right(if unsorted) u might want to sort it and start adding from the end...u know every (i)mod3 th largest sum as A[n]+B[n] is the largest then we've A[n]+B[n-1],A[n-1]+B[n] in between..next 4th biggie is A[n-1]+B[n-1]...go something this way...u already ....but this will not be the question I am sure this one's so darn easy....

Comment hidden because of low score. Click to expand.
0

what i mean by i mod 3 was for every i(mod3)==0 u've a known largest number...so we might use it :)

Comment hidden because of low score. Click to expand.
0

I think yoyr concept is not valid.
Check it for:
First Array :10 8 6 4 1
Second Array: 9 6 3 2 1

Comment hidden because of low score. Click to expand.
0

I am sorry , I am a bit slow here...Could you please explain if you discard your order of sorting(which we are doing ourself and assume ascending) then exactly how is that going to fail...

Comment hidden because of low score. Click to expand.
0

dude i never said that A[n]+B[n-1],A[n-1]+B[n] will be in any order..I left that to figure out once we know the index i such that k falls in between of out Arithmetic progression of known largest numbers as 1st,4th,7th,10th and so on where 1st largest belongs to A[n]+B[m] , 4th largest will be A[n-1]+B[m-1] , 7th largest will be A[n-2]+B[m-2] and so on...just figure out where K rests in AP..its simple math I guess....but for that we need to reach to the point right...ok...I'll be a bit more descriptive.....

Comment hidden because of low score. Click to expand.
0

I hope you got my point?

Comment hidden because of low score. Click to expand.
0

@abhi, what if A and B are as follows?
A: 51, 52, 53
B: 1, 2, 100
The third largest is (51 + 100), not (53 + 2)

Comment hidden because of low score. Click to expand.
0

truly said agreed...darn it....:(...will think of smthn lse

Comment hidden because of low score. Click to expand.
0
of 0 vote

I am hoping this will be more like subset sum up to kth largest in two unsorted arrays :D ....

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort both the arrays in descending order O(nlogn) and then the following code snippet

int Kthlargepair(int[] a, int[] b)
{
int aIndex = 0;
int bIndex = 0;
for(int i = 1; i < k; ++i)
{
if(a[aIndex] > b[bIndex])
++aIndex;
else
++bIndex;
}
return a[aIndex] + b[bIndex];
}

The above code is of complexity O(n)

Total complexity: O(nlogn)+O(n) = O(nlogn)

Comment hidden because of low score. Click to expand.
0

Check for:
First Array :10 8 6 4 1
Second Array: 9 6 3 2 1

Comment hidden because of low score. Click to expand.
0

Good counter example. Never thought of this..

Comment hidden because of low score. Click to expand.
0

SOlution wont work for:
a => 100,70,40
b => 80, 49, 10

3rd highest will be:
100+80, 70+80, 100+49

bt by the logic it comes out to be: 70+49

Comment hidden because of low score. Click to expand.
0
of 0 vote

What I can think is of O(n^2)

Maintain a mean heap of size k.For each sum(one element from first array and another from second array),if sum<top_of_the_heap the no need to insert it
else
Remove the top.Insert the sum at the top.Call Min heapify.
At last the top element is the kth largest.

Comment hidden because of low score. Click to expand.
0

Seems like a young tableau problem, if we decide to sum up all elements in both sorted array.
sort: nlogn
sum: mn
young tableau extraction: klogn

total: mn

this can be reduced if we can come up with some scheme that identifies only those elements which needs to be added (reduced sum complexity to less than "mn")

Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem can solved in O(n * log(max_Value(a) + max_Value(b) )) + O(nlogn) using binary search. First sort both the arrays. Now consider the following query .
How many pairs of numbers are there which have sum >= to the given value. This query can be solved in many ways . There are two algorithms to solve this query . The first one in the best case takes O(logn) and worst case O(nlogn).Another algorithm takes always O(n) time. Once you can answer this query we can use binary search to solve the given problem.

int search(int start, int end,const int &K) {
if(start>end)
return -INF;
int mid = (start+end)>>1;
//func(arg) returns how many pairs are there which have sum >=arg
int no_pairs = func(mid);
if( no_pairs < K ) {
return search(start,mid-1,K);
}
else if( no_pairs > K ) {
return search(mid+1,end,K);
}
else{
return max(mid, search(mid+1,end,K) ) ;
}
}

Working of the above algorithm:
First of all we note that kth maximum is a number b/w min_value(a)+min_value(b) and max_value(a)+max_value(b) . So we do a search in this interval for that kth maximum. By definition kth maximum sum means a value in the sum array and number of elements in that sum array greater than this value is k-1.
Algorithm working: If the number of pairs which have sum>=mid is say Count. if Count
> K then we search in [mid+1,end] . If Count < K then we search in [start,mid-1] . Now if Count ==K then we note that the value mid can be our answer or there can be another integer larger than this and for which Count==K . Suppose your sum array is 1 2 10 15. and K is 2 . Then 3,4,5,...10 values satisfy the condition that number of pairs greater than that value is 2. Now convince yourselves that the answer is maximum among all the values.

It is good exercise to think how we can write the function by name func used in this binary search :)

Comment hidden because of low score. Click to expand.
0

could you please explain how do you keep track of sum? are you calculating sum based upon partition? Please excuse me but I am finding it hard to understand

Comment hidden because of low score. Click to expand.
0

You need not calculate the sum array actually. All you need to find how many elements in the sum array will be >= the given value. Can you tell me which part of the solution you did not understand

Comment hidden because of low score. Click to expand.
0

The part where you try to get a pair of number where you compare it against *some* sum. If you could explain with example, I will get more clear idea.

Comment hidden because of low score. Click to expand.
0

What I dont understand is *All you need to find how many elements in the sum array will be >= the given value* Here what is the given value? Our range is fixed min_value(a)+min_value(b) and max_value(a)+max_value(b)
but when we calculate interim sum, how do we validate its position relative to the kth sum
e.g max-min range is 80-11 and my interim sum is 45 and I am looking for 6th largest sum, how would I know that 45 is larger or smaller than 6th largest sum?

Comment hidden because of low score. Click to expand.
0

U need to find the number of pairs which have sum >=45. If that answer is 6 then ur almost done. Otherwise u need to search in [start,44] or [46,end] depending upon the number of pairs u get.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort Both Arrays complexity O(nlogn)
e.g.
a1[] = {10 9 6 4 2}
a2[] = {11 9 7 1}

Create another result array r[] sorted using insertion sort & count number of elements in result array

1st Pass:
take 1st element of a1 & a2 sum = 21 insert r (count = 1)

check if k <= count (every time when pass over)
a1+a2 = 21
take a1+a2 = 19 compare a2+a1=20 (inset 20) r2 =  count 2
check if k <= count (every time when pass over)

a2+a1 = 18 < 19
insert 19 r3 = 19
check if k <= count (every time when pass over)

compare element is 18 now
now traverse on a1 with each a2 element upto index 1 in above line
a1+a2 there
a1+a2 =18 checking element
a1+a2 = 17 < 18

inser 18 count 4 r4[] =18
check if k <= count (every time when pass over)

so on........

r[] = {21, 20 , 19, 18, 17...}
sorted
kth element is there

Comment hidden because of low score. Click to expand.
0

OMG

Comment hidden because of low score. Click to expand.
0

Doesn't work with

a1[] = {10,9,8,4,2}
a2[] = {12,9,7,1}

At 3rd pass, r3 should equals to a2+a1, not a1+a2.
The algorithm does not checks this case.

Comment hidden because of low score. Click to expand.
0
of 0 vote

kth largest sum from two arrays. sum of how many elements? two? if so, are they one from each array? or the could be from array?
"Question Unclear"

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

1)Sort both array (nlogn)
2)now we have A[n] and B[m] two sorted array.
take iA and iB two index variable
lets create a minimum heap minHeap(max size=k);
n+

for each iA+iB=0 Add A[iA]+A[iB](only one elem in heap till now)
.....
do the same thing till you are able to add elemment in k space heap
suppose
for each iA+iB=x Add A[iA]+A[iB](no element found space in k spaced heap)

after this point every element formed will be lesser than found in last iteration

here minimum value of heap will be the kth element.

ps: the idea is to create virtual young's table and iterate thru each diagonal,till one diagonal miss entry in minheap

Complexity of step 2 will be about K(logK).

Total complexity = nlogn +nlogn + klogk =O(nlogn)

Comment hidden because of low score. Click to expand.
0
of 0 vote

The easies solution i hope...
1) Sort both arrays A[] and B[]
2) result = 0;
for each b in B {
result += countElementsThatAreLessThan(k - b);
}

Where countElementsThatAreLessThan is simple binary search function that finds index of last element in A that is less than given value;

O(nlogn)

Comment hidden because of low score. Click to expand.
0

sorry, i thought that you should count how many pairs there are <k. For largest sum function should return sum itself and you should store max return value it will be result.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I have an idea:
1. sort both A[] and B[];
2. do something like merging them:
a)find p that A->A[p-1]>B and A[p] < B;
now we have the biggest (p) elements in both A and B (they are from A);
b)find q that B->B[q-1]>A[p] and B[q] < A[p];
now we have the second biggest (q) elements in both A and B (they are from B);
so these two sets of elements will make the (p*q) biggest SUMs.
3.if(k > p*q),we will do the same to find (k-q*q)th max sum in A[p..n] and B[0..n]
4.if(k < p*q),we could find it in A[0..p-1] and B[0..q-1].They are both sorted and A[p-1] > B.In this case, A and B will be make the biggest sum, and A[0..1] and B[0..1] will make the biggest 2*2 sums, and A[0..2] and B[0..2] will make the biggest 3*3...so we can get the position X that X >=sqrt(k) and X <= sqrt(k)+1. (A[X] and B[0..X]) and (B[X] and A[0..X]) will make the (X-1)^2+1 to X^ biggest sums,we can really sort them now

Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Sort both arrays in descending order. O(nlogn)
2) Merger them in descending order O(n)
3) Find biggest n such n*(n-1)/2 is < k. O(?) probably sqrt of 2k+1.
4) add n+1 the element to mergedArray(k- nC2) O(constat)

final order O(n).

Any gotcha in logic?

Comment hidden because of low score. Click to expand.
0

In my opinion after you merged two arrays you cannot choose pairs.

Comment hidden because of low score. Click to expand.
0

In my opinion after you merged two arrays you cannot choose pairs.

Comment hidden because of low score. Click to expand.
0

is there a restriction that each element has to be from a different array?

Comment hidden because of low score. Click to expand.
0

Of course!

Comment hidden because of low score. Click to expand.
0

Thx for clearing that. Well, we can use similar technique even in this case.
1) let the size of a be n, b be m.
total of m*n pairs.
2) find x elements from A, and y elements from B such that these x+y elements are the top most elements in both arrays. ( can be foun O(x+y) inline).. such x*y <= k.
3) there can be atmost x*y combinations with these sets which are bound to be the top most sums.
4) from then on, take x+1th and y+1 element and do (k-xy) additions to figure out kth higest sum. (this step is tricky but can be done in O(k-xy) which is def.ly less >= O(max of x or y).
5) Effective algorithm can be solved in O(nlogn) which is required for sorting.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry, final order in above methos id O(nlogn).
Basically 2 elements can be picked from n numbers in nC2 ways.
if we find max n such nC2 is less than K, any combinational sum of those n numbers is bigger than kth sum. then we pick n+1 elemtn and keep adding from highest number to get nC2+1th number etc.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't think there is a sure way to avoid the case that Rahul's algorithm missed. How about the following:
1) Order the two arrays a and b in descending order
2) Starting with a[i] where i=0, add it to b[j] where j = 0 ... n and b[j] > a[i+1] and store the values to a result array, using insertion sort
3) Increment i and repeat (the last element of a will obviously be a special case since there is no i+1)
4) This way, at each "round", the largest number in that round is strictly smaller than the largest number in the previous round so to find kth largest sum, we only need to compute while i < k.

I might be missing something though. Any thoughts?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the array first then do the following

``````int KthlargestSum(int[] a, int[] b)
{
int aIndex = 0;
int bIndex = 0;
Sum = 0;
for(int i = 1; i < k; ++i)
{
if(a[aIndex] > b[bIndex])
{
sum + = a[aIndex]
++aIndex;
}
else
{
sum + = a[bIndex]
++bIndex;
}
}
return sum;
}``````

Time O(nlogn) + O(k) = O(nlogn)
Space O(1)

Comment hidden because of low score. Click to expand.
0

Sorry Star i from 0.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't know why so many people wasting their time on this bullshit question.

If you are posting a question, please explain it well.

What an unclear and idiot question is this?

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is an instance of a top-k problem. Take a look at TA, NRA algorithm. With the objective function here is x+y where x, y are two attributes of a database.

Comment hidden because of low score. Click to expand.
0
of 0 vote

here's my solution in (nlgn+k) time.

Sort the both arrays.
Start from the end.
Let the arrays be A and B.
at each step maintain two pointer to last element of arrays.

At each point, compare A[last1]+ A[last1-1] , B[last2]+ B[last2-1] and A[last1] +B[last2]
According to largest of them decrease last1 and last2.
this way you'll get Kth largest sum in k steps.

Comment if I am mistaken somewhere.

Comment hidden because of low score. Click to expand.
0
of 0 vote

assuming arrays are sorted ascending order, will this work? ur comments are really appreciated. thx

``````public static int kthLargestSum(int [] a1, int [] a2, int k) {
int maxSum = 0;
int a =  a1.length-1;
int b = a2.length -1;
for(int i = 0; i < k; i++) {
maxSum  = 0;
if(a1[a] < a2[b]) {
maxSum+=a2[b];
maxSum+=a1[a];
a--;
} else if(a1[a] > a2[b]) {
maxSum+=a1[a];
maxSum+=a2[b];
b--;
} else {
maxSum+=a1[a];
maxSum+=a2[b];
b--;
}
}
return maxSum;
}``````

Comment hidden because of low score. Click to expand.
0

Please Ignore it, it wont work

Comment hidden because of low score. Click to expand.
0

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.