Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
The time complexity lower bound of this problem is O(klgk) rather than O(n).
With a min-heap, we can solve it with O(klgk) time complexity and O(k) space complexity.
I'll show you the code later.
I think I have same idea, though not in O(k) space complexity. Problem is that k is in range of 1 to n^2, so the time complexity goes to O(n^2 lgn^2).....
@Alexy.
1. when k is up to n^2, actually you need to sort all these n^2 numbers. Since no appropriate linear sorting algorithm can be applied here, the lower bound of a comparison sorting algorithm' time complexity is O(n^2lgn^2)=O(n^2lgn). Theorectically, you can't do it better.
2. Although k is a variable no greater than n^2, O(n^2lgn) is only the upper bound for O(klgk). So O(klgk) is more accurate than O(n^2lgn).
B.T.W. I just want to clarify the question: do we need k minimum numbers or just the kth number? If only need the kth, we can achieve O(n^2) time complexity by taking "median of medians" algorithm. If we need k mininum numbers, the lower bound of time complexity is O(klgk).
Here's the code. Most of the code is a min_heap implementation.
#include <iostream>
using namespace std;
typedef struct {
int i;
int j;
int sum;
} HeapElem;
void Swap(HeapElem* a, HeapElem* b) {
HeapElem t = *a;
*a = *b;
*b = t;
}
class MinHeap {
public:
MinHeap(int capacity): capacity__(capacity), heap_size__(0) {
heap_array__ = new HeapElem[capacity];
};
~MinHeap() {
delete[] heap_array__;
};
bool Insert(HeapElem e);
bool ExtractMin(HeapElem* e);
void PrintHeap();
private:
int LeftChild(int id) { return 2*id + 1; }
int RightChild(int id) { return 2*id + 2; }
int Parent(int id) {
if ( id == 0 ) return -1;
else return (id-1) / 2;
}
HeapElem* heap_array__;
int capacity__;
int heap_size__;
};
void MinHeap::PrintHeap() {
cout << "==============================" << endl;
cout << "heap_size:" << heap_size__ << endl;
for (int m = 0; m < heap_size__; ++m) {
cout << "elem[" << m <<"]={" << heap_array__[m].i << "," << heap_array__[m].j << "," << heap_array__[m].sum << "}" << endl;
}
cout << "==============================" << endl;
}
bool MinHeap::Insert(HeapElem e) {
if (heap_size__ == capacity__)
return false;
// cout << "Insert elem:{" << e.i << "," << e.j << "," << e.sum << "}" << endl;
heap_array__[heap_size__++] = e;
int p = heap_size__-1;
while (p != 0 && heap_array__[Parent(p)].sum > heap_array__[p].sum) {
int q = Parent(p);
Swap(&(heap_array__[p]), &(heap_array__[q]));
p = q;
}
// PrintHeap();
return true;
}
bool MinHeap::ExtractMin(HeapElem* e){
if (heap_size__ <= 0)
return false;
*e = heap_array__[0];
// cout << "Exact MinElem={" << e->i << "," << e->j <<"," << e->sum << "}" << endl;
heap_array__[0] = heap_array__[--heap_size__];
int p = 0;
while(p < heap_size__) {
int left = LeftChild(p);
if (left >= heap_size__)
break;
int min = left;
int right = RightChild(p);
if (right < heap_size__ && heap_array__[right].sum < heap_array__[left].sum)
min = right;
if (heap_array__[min].sum < heap_array__[p].sum) {
Swap(&(heap_array__[min]), &(heap_array__[p]));
p = min;
} else {
break;
}
}
// PrintHeap();
return true;
}
bool FindKthMin(int* a, int* b, int n, int k, int* v) {
if (k <= 0 || k > n*n) {
cerr << "k is invalid" << endl;
return false;
}
MinHeap heap(k);
HeapElem e = {0, 0, a[0]+b[0]};
heap.Insert(e);
HeapElem t1;
for(int m = 0; m < k; ++m) {
heap.ExtractMin(&t1);
cout << "a[" << t1.i << "]+b[" << t1.j << "]=" << a[t1.i] << "+"<< b[t1.j] << "=" << t1.sum << endl;
if (t1.j+1 < n) {
HeapElem t2 = {t1.i, t1.j+1, a[t1.i]+b[t1.j+1]};
heap.Insert(t2);
}
if (t1.j == 0 && t1.i+1 < n) {
HeapElem t3 = {t1.i+1, t1.j, a[t1.i+1]+b[t1.j]};
heap.Insert(t3);
}
}
*v = t1.sum;
cout << k << "th min value is " << *v <<endl;
return true;
}
int main () {
int v;
int a[] = {1,2,3};
int b[] = {1,4,7};
cout << "Test 0" << endl;
FindKthMin(a, b, 3, 9, &v);
int a1[] = { 1, 50, 100, 1000, 6000, 6002, 6004, 6006, 6008, 6010 };
int b1[] = {100, 200, 300, 2000, 3000, 4000, 5000, 6000, 7000, 8000 };
cout << "Test 1" << endl;
FindKthMin(a1, b1, 10, 100, &v);
int a2[] = { 1, 6, 7, 9, 10, 14 };
int b2[] = { 2, 3, 5, 8, 11, 16 };
cout << "Test 2" << endl;
FindKthMin(a2, b2, 6, 36, &v);
int a3[] = { 1, 30, 35 };
int b3[] = { 5, 6, 50 };
cout << "Test 3" << endl;
FindKthMin(a3, b3, 3, 9, &v);
int a4[] = { 1, 2, 3, 4, 5, 7, 8, 9, 10, 11};
int b4[] = { 1, 20, 30, 40, 50, 60, 70, 80, 90,100};
cout << "Test 4" << endl;
FindKthMin(a4, b4, 10, 100, &v);
int a5[] = {3,4,5,6,13,19};
int b5[] = {1,2,5,9,10,11};
cout << "Test 5" << endl;
FindKthMin(a5, b5, 6, 36, &v);
int a6[] = {0, 1, 3, 5};
int b6[] = {1, 2, 4, 7};
cout << "Test 6" << endl;
FindKthMin(a6, b6, 4, 16, &v);
return 0;
}
package careercup;
public class KthMinSum {
public static Integer[] find(int k, int[] a, int[] b) {
final Integer[] _result = new Integer[k];
int q = (int) Math.sqrt(k);
for (int i = 0; i < q; i++) {
for (int j = 0; j < q; j++) {
_result[i * q + j] = a[i] + b[j];
}
}
int left = 0;
int right = 0;
for (int i = q * q; i < k; i++) {
_result[i] = (a[q] + b[left]) < (b[q] + a[right]) ? (a[q] + b[left++]) : (b[q] + a[right++]);
}
return _result;
}
}
The way I implemented this takes O(K log(K)) time if I use a heap, or O(K^2) if I use a naive sorted array.
Here is the key idea: Obviously, the first pair is A[0] and B[0]. Furthermore, the first pair where we take index "i" from array "A" is indeed (A[i], B[0]). So we can initialize a list of "K" pairs of (A[i], B[0]) for "i = 0, 1, ..., K- 1".
Assume this list is sorted (or Heap with Extract Min). Take first Pair out say, (A[0], B[0]). NOTE: If the next pair leading to K-minimum sum includes (A[0]) it must be (A[0], B[1]). So we simply put the pair (A[0], B[1]) inside. In general, when you extract the pair (A[i], B[j]), you must Insert (A[i], B[j + 1]) back in.
Insertion and Extraction takes O(K) time if you use a simple sorted array, and O(log(K)) if you use a Heap. Overall, it takes, O(K Log(K)) = O(K^2).
Here is what I used for class Pair:
class Pair {
ind ind_A, ind_B;
public Pair(int a, b) {
ind_A = a; ind_B = b
}
public boolean IsLessThan(Pair other) {
return (A[ind_A] + B[ind_B]) < (A[other.ind_A] + B[other.ind_B]);
}
Here is the code for the main for-loop
public void Solve(int K) {
pairs = new Heap(A.length);
for (int i = 0; i < A.length; i++)
pairs.Insert(new Pair(i, 0));
// Now begin
for (int k = 0; k < K; k++) {
Pair p = pairs.ExtractMin();
System.out.println(p);
p.ind_B++;
pairs.Insert(p);
}
}
Here is a sample test:
public static void main(String[] args) {
// TODO code application logic here
int[] a = {1, 5, 6, 7, 8, 20, 21, 22};
int[] b = {1, 4, 5, 10, 15, 16, 17, 18};
MinSumArray ms = new MinSumArray(a, b);
ms.Solve(6);
}
Output:
A[0] + B[0] = 1 + 1 = 2
A[0] + B[1] = 1 + 4 = 5
A[1] + B[0] = 5 + 1 = 6
A[0] + B[2] = 1 + 5 = 6
A[2] + B[0] = 6 + 1 = 7
A[3] + B[0] = 7 + 1 = 8
My answer is almost the same with yours, but with slight difference.
That is, you initialize a list of "K" pairs of (A[i], B[0]) for "i = 0, 1, ..., K- 1", thus form a min heap naturally.
But I insert (A[i], B[0]) to the heap only when (A[i-1], B[0]) is extracted from the heap.See my code.
def find_kth(a, b, k):
a_count, b_count = 0, 0
is_last_b = False
while a_count * b_count < k:
if a[a_count] < b[b_count]:
a_count += 1
is_last_b = False
else:
b_count += 1
is_last_b = True
if is_last_b:
return a[a_count - (a_count * b_count - k) - 1], b[b_count - 1]
else:
return a[a_count - 1], b[b_count - (a_count * b_count - k) - 1]
Interesting problem that kept me busy some time but the trick is that arrays are sorted so, given a[0]+b[0] is for sure the first number that is to be produced, what are the next possible sums, well:
- S1 = a[a_i+1] + b[b_i];
- S2 = a[a_i+1] + b[0];
- S3 = a[a_i] + b[b_i+1];
- S4 = a[0] + b[b_i+1];
as you want to iterate over each arrays always checking the sum result of the other first array element when you increment either A index or B index. The smallest sum of the above for is the next one given that you:
- discard any sum smaller than the previous generated sum
- does not go beyond array boundaries
resulting code passing all the test series in this page is:
#include <stdio.h>
void print_Kth_min(int a[], int b[], int K, int N)
{
int a_i = 0, b_i = 0;
int count = 0;
int sum = 0;
sum = a[a_i] + b[b_i];
printf("[%d]+[%d] %d\n", a_i, b_i, sum);
while (count < K) {
/* Create the 4 possible next sum */
int S1 = a[a_i+1] + b[b_i];
int S2 = a[a_i+1] + b[0];
int S3 = a[a_i] + b[b_i+1];
int S4 = a[0] + b[b_i+1];
/*
Select the smallest one ensuring that:
- it needs to be bigger than latest generated sum (otherwise it has been made up already)
- does not goes beyond the array boundaries
*/
if ((S1 >= sum) && (a_i+1 < N) &&
((S2 < sum ? 1 : S1 <= S2)) &&
((S3 < sum ? 1 : S1 <= S3)) &&
((S4 < sum ? 1 : S1 <= S4))) {
a_i++;
} else if ((S2 >= sum) && (a_i+1 < N) &&
((S1 < sum ? 1 : S2 <= S1)) &&
((S3 < sum ? 1 : S2 <= S3)) &&
((S4 < sum ? 1 : S2 <= S4))) {
a_i++; b_i = 0;
} else if ((S3 >= sum) && (b_i+1 < N) &&
((S1 < sum ? 1 : S3 <= S1)) &&
((S2 < sum ? 1 : S3 <= S2)) &&
((S4 < sum ? 1 : S3 <= S4))) {
b_i++;
} else if ((S4 >= sum) && (b_i+1 < N) &&
((S1 < sum ? 1 : S4 <= S1)) &&
((S2 < sum ? 1 : S4 <= S2)) &&
((S3 < sum ? 1 : S4 <= S3))) {
b_i++; a_i = 0;
} else {
/* We've reached array's limits and need to finish iterating the one not reached yet */
if (a_i+1 == N) {
if (b_i+1 == N) {
/* K is greater than values we can make up */
return;
} else {
b_i++;
}
} else {
a_i++;
}
}
sum = a[a_i] + b[b_i];
printf("[%d]+[%d] %d\n", a_i, b_i, sum);
count ++;
}
}
int main(int argc, char *argv[])
{
int a1[] = { 1, 50, 100, 1000, 6000, 6002, 6004, 6006, 6008, 6010 };
int b1[] = {100, 200, 300, 2000, 3000, 4000, 5000, 6000, 7000, 8000 };
printf("Test 1\n");
print_Kth_min(a1, b1, 50, 10);
int a2[] = { 1, 6, 7, 9, 10, 14 };
int b2[] = { 2, 3, 5, 8, 11, 16 };
printf("Test 2\n");
print_Kth_min(a2, b2, 30, 6);
int a3[] = { 1, 30, 35 };
int b3[] = { 5, 6, 50 };
printf("Test 3\n");
print_Kth_min(a3, b3, 10, 3);
int a4[] = { 1, 2, 3, 4, 5, 7, 8, 9, 10, 11};
int b4[] = { 1, 20, 30, 40, 50, 60, 70, 80, 90,100};
printf("Test 4\n");
print_Kth_min(a4, b4, 100, 10);
return 0;
}
Consider the following input:
a = [ 1, 3, 4, 10 ]
b = [ 2, 3, 8, 9]
First pair is {1,2} .
Iteration 1 selects S3 {1,3} // b_i++
Iteration 2 selects S2 {2,3} // a_i++, b_i=0
Iteration 3 selects S1 {4,2} // a_i++
Iteration 4 selects S3 {4,3} // a_i++
Note that {3,3} is missed and can't be found later since sum has now grown to 7. The {3,3} pair had to be selected at iteration 3 as S3, but there was no criterion to prefer it over S1 as they both yield the same sum. More logic of this type can be added, but the basic truth is there are more than 4 different options at every step. There are actually N options (worst case) as demonstrated by the min-heap based solutions. The pairs sit in a matrix, each row has a cursor running from min to max (two cursors a,b are not enough) and in each step one "row" is selected as having the minimal value. If you don't use a min-heap and just go thru the cursors top-to-bottom, then you can have the following optimization: all the cursors we have not checked yet AND point to columns bigger-equal than ours must have higher-equal values, so can be skipped. Anyway, using min-heap is simpler and faster.
How about the following solution, it will run as long as we don't request K to be more then the number of all the possible combinations
public static ArrayList<Integer> firstKMin(int[] A, int[] B, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
int firstA=0;
int nextA=1;
int firstB=0;
int nextB=1;
list.add(A[firstA]+B[firstB]);
int count=1;
while(count<k) {
if(A[firstA]+B[nextB] < B[firstB]+A[nextA]) {
list.add(A[firstA]+B[nextB]);
nextB++;
if(nextB >= B.length) {
firstA++;
nextB=0;
}
} else {
list.add(B[firstB]+A[nextA]);
nextA++;
if(nextA >= A.length) {
firstB++;
nextA=0;
}
}
count++;
}
return list;
}
Finally I worked out it! It can pass all the test cases before! Here is the code:
static void nextIdx(const std::vector<int> & r1,
const std::vector<int> & r2,
const std::vector<int> & idx1,
const std::vector<int> & idx2,
int & i,
int & j,
int min_i,
int min_j)
{
if(j > 0){
int rr = r1[i] + r2[j];
for(int ii = min_i;ii < int(r1.size());++ii){
int jj = idx1[ii] + 1;
if(jj < j && rr > r1[ii] + r2[jj]){
i = ii;
j = jj;
rr = r1[i] + r2[j];
}
if(!jj)
break;
}
}
if(i > 0){
int rr = r1[i] + r2[j];
for(int jj = min_j;jj < int(r2.size());++jj){
int ii = idx2[jj] + 1;
if(ii < i && rr > r1[ii] + r2[jj]){
i = ii;
j = jj;
rr = r1[i] + r2[j];
}
if(!ii)
break;
}
}
}
//find k-th min in O(N)
int kthMin(const std::vector<int> & r1, const std::vector<int> & r2, int k)
{
assert(1 <= k && k <= int(r1.size() * r2.size()));
assert(!r1.empty() && !r2.empty());
std::vector<int> idx1(r1.size(), -1);
std::vector<int> idx2(r2.size(), -1);
int ret;
for(int i = 0, j = 0, n = 1;i < int(r1.size()) && j < int(r2.size());++n){
ret = r1[i] + r2[j];
if(n == k)
break;
idx1[i] = j;
idx2[j] = i;
if(i == r1.size() - 1){
assert(j < int(r2.size()) - 1);
i = idx2[++j] + 1;
if(i > 0)
nextIdx(r1, r2, idx1, idx2, i, j, r1.size(), j + 1);
}else if(j == r2.size() - 1){
assert(i < int(r1.size()) - 1);
j = idx1[++i] + 1;
if(j > 0)
nextIdx(r1, r2, idx1, idx2, i, j, i + 1, r2.size());
}else if(r1[i + 1] < r2[j + 1]){
int jj = j;
j = idx1[++i] + 1;
nextIdx(r1, r2, idx1, idx2, i, j, i + 1, jj + 1);
}else{
int ii = i;
i = idx2[++j] + 1;
nextIdx(r1, r2, idx1, idx2, i, j, ii + 1, j + 1);
}
}
return ret;
}
And with the all test cases:
//O(N * N)
int kthMinSlow(const std::vector<int> & r1, const std::vector<int> & r2, int k)
{
assert(1 <= k && k <= int(r1.size() * r2.size()));
std::vector<int> v;
for(int i = 0;i < k && i < int(r1.size());++i)
for(int j = 0;j < k && j < int(r2.size());++j)
v.push_back(r1[i] + r2[j]);
std::sort(v.begin(), v.end());
assert(int(v.size()) >= k);
return v[k - 1];
}
void test(const int v1[], const int v2[], int N)
{
assert(N > 0);
std::vector<int> r1(v1, v1 + N);
std::vector<int> r2(v2, v2 + N);
//test
std::vector<int> t1;
for(int k = 1;k <= int(r1.size() * r2.size());++k){
t1.push_back(kthMinSlow(r1, r2, k));
//std::cout<<t1.back()<<", ";
}
//std::cout<<"\n";
std::vector<int> t2;
for(int k = 1;k <= int(r1.size() * r2.size());++k){
t2.push_back(kthMin(r1, r2, k));
//std::cout<<t2.back()<<", ";
}
//std::cout<<"\n";
if(t1 != t2)
std::cerr<<"test FAILED\n";
}
int main()
{
{
const int v1[] = {0, 1, 3, 5};
const int v2[] = {1, 2, 4, 7};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 2, 3,4,5,7,8,9,10,11};
const int v2[] = {1,20,30,40,50,60,70,80,90,100};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 30, 35};
const int v2[] = {5,6,50};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 6, 7, 9, 10, 14};
const int v2[] = {2, 3, 5, 8, 11, 16};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 2, 2, 2};
const int v2[] = {1, 2, 3, 4};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 3, 4, 10};
const int v2[] = {2, 3, 8, 9};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 50, 100, 1000, 6000, 6002, 6004, 6006, 6008, 6010};
const int v2[] = {100, 200, 300, 2000, 3000, 4000, 5000, 6000, 7000, 8000};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 5, 6, 7, 8, 20, 21, 22};
const int v2[] = {1, 4, 5, 10, 15, 16, 17, 18};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {100,200,300,400};
const int v2[] = {1,2,3,4};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 2, 3};
const int v2[] = {1, 4, 7};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {1, 50, 100, 1000, 6000, 6002, 6004, 6006, 6008, 6010};
const int v2[] = {100, 200, 300, 2000, 3000, 4000, 5000, 6000, 7000, 8000};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}{
const int v1[] = {3,4,5,6,13,19};
const int v2[] = {1,2,5,9,10,11};
test(v1, v2, sizeof v1 / sizeof v1[0]);
}
}
I have to admit that the algorithm is not straightly O(N). But I think there might be a way to prove that, in the worst case, nextIdx() could be in a limited complexity. Maybe I will think about it later.
This complexity is O(K^2 log(K)). You are not using some of the information about A and B. We know that A and B are sorted, which implies that you only need the first "K" elements. But that is not all that is implied.
If the first "K" elements of A and B are not sorted, then the list of numbers A[i] + B[j] could form (K^2)! different types of orderings. Then, your algorithm might have been optimal since the complexity is that of sorting.
For this problem we know that A and B are sorted. An O(K log(K)) algorithm actually exists). I guess even an O(K) algorithm might exist but as Anonymous said, if it does, it looks very hard to be found.
** Nevermind, I only saw the second algorithm which you already mentioned is O(N*N)
Also for the first algorithm, in the main loop you are increasing either "i" or "j" by 1 in each iteration. Then each time you also call "nextIdx" which has a for loop running for (N - i) or (N - j) iterations. So the complexity seems to be O(K N).
public class MaxSumsOf2SortedArrays {
public MaxSumsOf2SortedArrays() {
a = new int[]{0, 1, 3, 5};
b = new int[]{1, 2, 4, 7};
}
int[] a;int[] b;
void findMax(int K){
int a1=0;int a2=1;
int b1=0;int b2=1;
int count = 0;
System.out.println(a[0]+b[0]);
while(count<K && count<=a.length*b.length){
count++;
int aSum = a[a1]+b[a2];
int bSum = b[b1]+a[b2];
if(aSum<=bSum){
System.out.println(aSum + "--"+a[a1]+"+"+b[a2]);
a2++;
if(a2==b.length){
a1++;
a2=a1;
}
}
else{
System.out.println(bSum+ "--"+b[b1]+"+"+a[b2]);
b2++;
if(b2==a.length){
b1++;
b2=b1;
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
MaxSumsOf2SortedArrays m = new MaxSumsOf2SortedArrays();
m.findMax(100);
}
}
public class MaxSumsOf2SortedArrays {
public MaxSumsOf2SortedArrays() {
a = new int[]{0, 1, 3, 5};
b = new int[]{1, 2, 4, 7};
}
int[] a;int[] b;
void findMax(int K){
int a1=0;int a2=1;
int b1=0;int b2=1;
int count = 0;
System.out.println(a[0]+b[0]);
while(count<K && count<=a.length*b.length){
count++;
int aSum = a[a1]+b[a2];
int bSum = b[b1]+a[b2];
if(aSum<=bSum){
System.out.println(aSum + "--"+a[a1]+"+"+b[a2]);
a2++;
if(a2==b.length){
a1++;
a2=a1;
}
}
else{
System.out.println(bSum+ "--"+b[b1]+"+"+a[b2]);
b2++;
if(b2==a.length){
b1++;
b2=b1;
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
MaxSumsOf2SortedArrays m = new MaxSumsOf2SortedArrays();
m.findMax(100);
}
}
public class KthMinSumFromTwoArrays {
public static void main(String[] args){
int[] a = new int[]{1,5,9,15,20};
int[] b = new int[]{3,4,7,10,12};
KthMinSumFromTwoArrays obj = new KthMinSumFromTwoArrays();
for(int i = 1; i<=9; i++){
System.out.println(obj.findNthMinSum(a, b, i));
}
}
private int whichIsMin(int first, int second, int third){
int min = Math.min(first, second);
if(min == first){
min = Math.min(first, third);
if(min == first){
return 1;
} else {
return 3;
}
} else {
min = Math.min(second, third);
if(min == second){
return 2;
} else {
return 3;
}
}
}
private int findNthMinSum(int[] a, int[] b, int n){
if(n == 1){
return a[0]+b[0];
}
int aLimit = a.length;
int bLimit = b.length;
int firstA = 0;
int firstB = 0;
int secondA = 1;
int secondB = 0;
int thirdA = 2;
int thirdB = 0;
int nThMin = 0;
while(n > 0){
int firstSum = Integer.MAX_VALUE;
int secondSum = Integer.MAX_VALUE;
int thirdSum = Integer.MAX_VALUE;
if(firstA < aLimit && firstB < bLimit){
firstSum = a[firstA]+b[firstB];
}
if(secondA < aLimit && secondB < bLimit){
secondSum = a[secondA]+b[secondB];
}
if(thirdA < aLimit && thirdA < bLimit){
thirdSum = a[thirdA]+b[thirdB];
}
int whichIsMin = whichIsMin(firstSum, secondSum, thirdSum);
switch(whichIsMin){
case 1:
nThMin = a[firstA]+b[firstB];
firstB++;
if(firstB == bLimit){
firstA = secondA;
secondA = thirdA;
thirdA++;
firstB = secondB;
secondB = thirdB;
thirdB = 0;
}
break;
case 2:
nThMin = a[secondA]+b[secondB];
secondB++;
break;
case 3:
nThMin = a[thirdA]+b[thirdB];
thirdB++;
break;
}
n--;
}
return nThMin;
}
}
Minimum value will be a[0] + b[j] or a[i] + b[0]
so the answer is
int[] firstKMin(int k, int[] a, int b []){
int i = 1;
int j = 1;
int index = 1;
int[] answer = new int[k];
// This is special case
answer[0] = a[0] + b[0];
while(i < N && j < N){
x = a[i] + b[0];
y = a[0] + b[j];
if(x < y){
answer[index] = x;
i++;
}else{
answer[index] = y;
j++;
}
c++;
}
if(index < k){
if(i == N){
for(int l = j; l < N; l++){
answer[index] = a[0] + b[l];
index++;
}
}
if(j == N){
for(int l = i; l < N; l++){
answer[index] = a[i] + b[0];
index++;
}
}
}
return answer;
}
Minimum value will be a[0] + b[j] or a[i] + b[0]
Note#
a[0] + b[0] is the special case, we need to be careful for
this case.
k > N case is also special case.
so the answer is
int[] firstKMin(int k, int[] a, int b []){
int i = 1;
int j = 1;
int index = 1;
if( K >= 2N){
// invalid input
retrun null;
}
int[] answer = new int[k];
// This is special case
answer[0] = a[0] + b[0];
while(i < N && j < N){
x = a[i] + b[0];
y = a[0] + b[j];
if(x < y){
answer[index] = x;
i++;
}else{
answer[index] = y;
j++;
}
c++;
}
if(index < k){
if(i == N){
for(int l = j; l < N; l++){
answer[index] = a[0] + b[l];
index++;
}
}
if(j == N){
for(int l = i; l < N; l++){
answer[index] = a[i] + b[0];
index++;
}
}
}
return answer;
}
A (klog k) Soluton
import java.util.*;
class node{
int aX;
int bX;
node(int aX, int bX)
{
this.aX=aX;
this.bX=bX;
}
}
public class kthMin {
static node kthMin(int[] arrA, int[] arrB,int k)
{
//Declaration/Intialization section
Queue<node> maxHeap=new PriorityQueue<node>(1,new Comparator<node>(){
public int compare(node A, node B)
{
return (B.aX+B.bX)-(A.aX+A.bX);
}
});
//Logic section
for(int i=0;i < k && i < arrA.length;i++)
for(int j=0; j < k && j < arrB.length;j++)
if(maxHeap.size() < k)
maxHeap.add(new node(arrA[i],arrB[j]));
else{
if(maxHeap.peek().aX+maxHeap.peek().bX > arrA[i]+arrB[j])
{
maxHeap.poll();
maxHeap.add(new node(arrA[i],arrB[j]));
}
}
return maxHeap.peek();
}
public static void main(String[] args) {
int[] arrA={ 1, 2, 3, 4, 5, 7, 8, 9, 10, 11};
int[] arrB={ 1, 2, 30, 40, 50, 60, 70, 80, 90,100};
node n=kthMin(arrA,arrB,6);
System.out.print(n.aX+" "+ n.bX);
}
}
Why not simply add the two arrays together (O(n)) and then run quickselect (O(n)) on the resulting array? If we're just selecting the Kth min then thats fine, we'd get the element we need, if we're providing the list of mins up to K then, anything to the left of the returned element from quick select will be the min. If we need to know the elements of each array that composed these then perhaps we could sort an array of a datatype which contains the requisite information.
k = 1: a[0] + b[0]
k = 2: min(a[0] + b[1], a[1] + b[0])
k = 3: max(a[0] + b[1], a[1] + b[0])
k = 4: a[1] + b[1]
...
k = 3n-1: min(a[n-1] + b[n], a[n-1] + b[n])
k = 3n: max(a[n-1] + b[n], a[n-1] + b[n])
k = 3n + 1: a[n] + b[n]
k = 3
Here is the code that was implemented based on the above generalization.
public class KthMinimum {
public static int findKthMin(int[] A, int[] B, int K) {
// Get square root of previous and next perfect squares of K
// Example: If K=8 then low = 2 (sqrt of 4) and high =3 (sqrt of 9)
int low = (int) Math.floor(Math.sqrt(K));
int high = (int) Math.ceil(Math.sqrt(K));
// If K is a perfect square (like 1, 4, 9)
if (low == high) {
low--;
return A[low] + B[low];
}
int max = (int) Math.pow(high, 2);
int offset = (int) Math.ceil((Math.pow(high, 2) - K) / 2);
high--;
low = high - offset;
if ((max % 2 == 0 && K % 2 == 0) || (max % 2 != 0 && K % 2 != 0)) {
return Math.min(A[high] + B[low], A[low] + B[high]);
} else {
return Math.max(A[high] + B[low], A[low] + B[high]);
}
}
public static void main(String[] args) {
int a[] = { 1, 6, 7, 9, 10, 14 };
int b[] = { 2, 3, 5, 8, 11, 16 };
System.out.println(findKthMin(a, b, 32));
}
}
Please tell me how wrong I am:
public ArrayList<Integer> getKthMin(int k, int[] a, int[] b){
ArrayList<Integer> answer = new ArrayList<>();
int i = 0;
int j = 0;
while((i + j) < k)
{
answer.add(a[i] + b[j])
if(a[i] <= b[j])
i++;
else if(a[i] > b[j])
j++;
}
return answer;
}
public int findKthMin(int[] A, int[] B, int K)
{
int indexA = 0;
int indexB = 0;
int count = 1;
while (count < K)
{
int sum1 = A[indexA + 1] + B[indexB];
int sum2 = A[indexA] + B[indexB + 1];
if (sum1 > sum2)
{
indexA++;
}
else
{
indexB++;
}
}
return A[indexA] + B[indexB];
}
Consider the example:
a: 1, 30, 35
b: 5,6,50
k = 1 : 1 + 5
k = 2 : 1 + 6
k = 3 : correct ans: (30 + 5) your algo: (30 + 6)
you do not need to calculate sums inside the loop. Just keep track of the indexes.
public int findKthMin(int[] A, int[] B, int K)
{
int indexA = 0;
int indexB = 0;
char min;
int count = 0;
int *pMin = null;
int *pMinLast = null;
while (count < k)
{
pMinLast = pMin;
if (A[indexA] < B[indexB])
{
pMin = &A[IndexA];
indexA++;
}
else
{
pMin = &B[IndexB];
indexB++;
}
}
return *pMin + *pMinLast;
}
This doesn't work, it skips some numbers.
For example, if the sequence of mins goes like that:
a[0] + b[1]
a[1] + b[1]
a[0] + b[2]
We need to go backwards sometimes.
If consider a matrix where each cell contains summation of array elements, then next min is a cell adjacent to ANY explored cell not only current cell... hopefully that make sense
Got it finally:
(1)do merge process, record each item is from a[] or b[].
(2)find the Kth smallest pair(remember a pair must be one from a[], the other from b[]).
time complexity: O(N)
space complexity: O(N)
As I'm more familiar with C++, following is my C++ code with annotation:
#include <cstdlib>
#include <utility>
#include <algorithm>
using namespace std;
pair<int,int> getKthSmallestPair(const int a[], const int b[], int N, int K)
{
//only exist N*N pairs of a[i]+b[j]
if(K <= 0 || K > N*N) return make_pair(-1, -1);
//alloc memory for the merged array flags
int total = N << 1;
bool* isFromA = new bool[total];
//do merge process, record whether the item is from a[] or not
int i = 0, j = 0, k = 0;
for(; i < N && j < N; ++k){
if(a[i] > b[j]){
isFromA[k] = false;
++j;
}
else{
isFromA[k] = true;
++i;
}
}
for(; i < N; ++i, ++k){
isFromA[k] = true;
}
for(; j < N; ++j, ++k){
isFromA[k] = false;
}
//find the Kth smallest pair of a[i] + b[j]
i = j = -1;
//step 1: find the certain i or j of the Kth pair
int itemsOfA = 0, itemsOfB = 0;
for(k = 0; k < total; ++k){
if(isFromA[k]){
++itemsOfA;
if(itemsOfA * itemsOfB >= K){
i = itemsOfA - 1;
break;
}
}
else{
++itemsOfB;
if(itemsOfA * itemsOfB >= K){
j = itemsOfB - 1;
break;
}
}
}
//step 2: find the matched j or i in the Kth pair
int dis = itemsOfA * itemsOfB - K + 1;
if(i == -1){//b[j] has been found in step 1, whose index is k in the merged array
for(--k; k >= 0; --k){
if(isFromA[k]){
--itemsOfA;
if(--dis == 0){
i = itemsOfA;
break;
}
}
}
}
else{//a[i] has been found in step 1, whose index is k in the merged array
for(--k; k >= 0; --k){
if(!isFromA[k]){
--itemsOfB;
if(--dis == 0){
j = itemsOfB;
break;
}
}
}
}
//free memory and return indexes
delete[] isFromA;
return make_pair(i, j);
}
int main()
{
int a[] = {1, 2, 3};
int b[] = {1, 4, 7};
pair<int,int> res;
for(int i = 1; i <= 9; ++i){
res = getKthSmallestPair(a, b, 3, i);
printf("%dth smallest pair is a[%d] + b[%d]\n", i, res.first, res.second);
}
puts("\nafter switch a[] and b[]:\n");
for(int i = 1; i <= 9; ++i){
res = getKthSmallestPair(b, a, 3, i);
printf("%dth smallest pair is a[%d] + b[%d]\n", i, res.first, res.second);
}
return 0;
}
I think your answer is wrong. Your program can not pass the following test data.
int a[] = {0, 1, 3, 5};
int b[] = {1, 2, 4, 7};
k=0;j=0;i=0;
while(k<K)//K is the K mentioned in the question
{
sum= a[i]+b[j]; //calculate sum with current i and j, it will be the next smallest
k++;
//now we need to know whether to increment i or j
//This will depend on (a[i]+b[j+1]) and (a[i+1]+b[j])
if ( a[i]+b[j+1] < a[i+1]+b[j] ) //incrementing index of b takes us to the next smallest sum
j++;
else
i++
}
return sum;
dont keep computing sums inside the loop. Just need to keep track of which is the kth min and (k+1)th min number in combined array.
public int findKthMin(int[] A, int[] B, int K)
{
int indexA = 0;
int indexB = 0;
int *pMin = null;
int *pMinLast = null;
while ((indexA+indexB) <= k + 1)
{
pMinLast = pMin;
if (A[indexA] < B[indexB])
{
pMin = &A[IndexA];
indexA++;
}
else
{
pMin = &B[IndexB];
indexB++;
}
}
return *pMin + *pMinLast;
}
public class KthMinSum {
public static Integer[] find(int k, int[] a, int[] b) {
final Integer[] _result = new Integer[k];
int q = (int) Math.sqrt(k);
for (int i = 0; i < q; i++) {
for (int j = 0; j < q; j++) {
_result[i * q + j] = a[i] + b[j];
}
}
int left = 0;
int right = 0;
for (int i = q * q; i < k; i++) {
_result[i] = (a[q] + b[left]) < (b[q] + a[right]) ? (a[q] + b[left++]) : (b[q] + a[right++]);
}
return _result;
}
}
Like Alexey mentioned below, this doesn't work. Downvoting so it doesnt show up as top voted result (which it currently does)
"a = new int[] { 1, 2, 3,4,5,7,8,9,10 };
b = new int[]{1,20,30,40,50,60,70,80,90,100};
doesnt work
Also, k can be up to n^2, so the first double loop can take n^2
- Alexey on December 18, 2013 | Flag"
package careercup;
public class KthMinSum {
public static Integer[] find(int k, int[] a, int[] b) {
final Integer[] _result = new Integer[k];
int q = (int) Math.sqrt(k);
for (int i = 0; i < q; i++) {
for (int j = 0; j < q; j++) {
_result[i * q + j] = a[i] + b[j];
}
}
int left = 0;
int right = 0;
for (int i = q * q; i < k; i++) {
_result[i] = (a[q] + b[left]) < (b[q] + a[right]) ? (a[q] + b[left++]) : (b[q] + a[right++]);
}
return _result;
}
}
a = new int[] { 1, 2, 3,4,5,7,8,9,10 };
b = new int[]{1,20,30,40,50,60,70,80,90,100};
doesnt work
Also, k can be up to n^2, so the first double loop can take n^2
thanks for review. That was big fail ;)
> Also, k can be up to n^2, so the first double loop can take n^2
in original problem need to return first K elements, not just Kth element which was described as PS, that's why at least need to fill K elements. So algorithm's expected complexity is O(K). If K is equal to max value n^2, do you know any algorithm which fill n^2 elements in O(N)?
static int kthMinimum(int index1, int index2, int curr, int k)
{
if(curr == k)
{
return array1[index1] + array2[index2];
}
int n1 = array1[index1 + 1] + array2[index2];
int n2 = array1[index1] + array2[index2 + 1];
if(n1<n2)
{
curr++;
if(curr == k)
return n1;
curr ++;
if(curr == k)
return n2;
}
else
{
curr++;
if(curr == k)
return n2;
curr ++;
if(curr == k)
return n1;
}
return kthMinimum(index1 + 1, index2 + 1, curr+1,k);
}
int findKthSum(int A[], int B[], int N, int K)
{
ASSERT(N*N > K); // we must have K pairs
// lets say A[a] and B[b] is Kth lowest sum
// we must have ((a-1) * b < K) and (a * (b-1) < K)
// merge sort
int a = 1; // this is elements used from A.
int b = 1; // this is elements used from B.
bool lastFromA = false;
while (a * b < K)
{
if (A[a-1] < A[b-1])
{
a++;
lastFromA = true;
}
else
{
b++;
lastFromA = false;
}
}
if (a*b == K) return A[a-1]+B[b-1];
// so far we have used up a-1 elements from A, and b-1 elements from B. and have found (a-1)*(b-1)th lowest.
// we also have one of the correct index (nextFromA). just find the other one.
if (lastFromA)
{
b = K - (a-1)*b;
}
else
{
a = K - (b-1)*a;
}
// our answer is A[a] + B[b]
return A[a] + B[b];
}
like merge sort, increase pointers from a and b. You do not need to calculate the min values, you just count the min values while increasing the pointers. And when you exceed the desired k, you can calculate a[i] + b[j] for the kth min.
private static int kthMin(int[] a, int[] b, int k){
int i = 0 ;
int j = 0 ;
int numOfMin = 1;
while(i < a.length -1 && j < b.length - 1) {
if(a[i+1] <= b[j+1]) {
i++;
numOfMin += (j+1);
if(numOfMin >= k) return a[i] + b[j- numOfMin + k];
}
else {
j++;
numOfMin += (i+1);
if(numOfMin >= k) return a[i- numOfMin + k] + b[j];
}
}
return 0;
}
O(n) algorithm:
suppose you have initial minimum:
a[i]+b[j]
To find next minimum you need to test the following 4-6 pairs and find the pair
with minimum sum that is greater than the current one. Rinse-repeat K times.
Code:
public static int getMin(int[]a, int[]b, int k){
if(a.length!=b.length || a.length*a.length < k){
return Integer.MIN_VALUE;
} else {
int newmin=a[0]+b[0]; // this is the result holder, initialized to satisfy Java
for(int cura=0, curb=0, i=0; i<k; i++ ){
int curmin = a[cura] + b[curb]; // current minimum
newmin = curmin;
int newa =cura, newb=curb;
int testa, testb, testsum;
boolean gotcandidate = false;
// Test a[cura-1]+b[curb+1] pair
if(curb<b.length-1 && cura>0){
testa=cura-1;
testb=curb+1;
testsum=a[testa] + b[testb];
// if this pair's value is greater than current minimum we got candidate
if(testsum>curmin){
newmin=testsum;
newa=testa;
newb=testb;
gotcandidate=true;
}
}
// Test a[cura+1]+b[curb-1] pair
if(cura<a.length-1 && curb>0){
testa=cura+1;
testb=curb-1;
testsum=a[testa] + b[testb];
// we got new candidate if
// this sum is greater than current minimum
// AND
// we haven't got candidate yet OR this sum is less than the current candidate
// i.e. current minimum > this test > current candidate
if(testsum>curmin && (!gotcandidate || testsum<newmin)){
newmin=testsum;
newa=testa;
newb=testb;
gotcandidate=true;
}
}
// Test a[cura]+b[curb+1]
// if curb+1 is out of bound then test
// a[cura+1]+b[0] instead
if(curb<b.length-1){
testa=cura;
testb=curb+1;
} else {
testb=0;
testa=cura+1;
}
testsum=a[testa] + b[testb];
// we got new candidate if
// this sum is greater than current minimum
// AND
// we haven't got candidate yet OR this sum is less than the current candidate
// i.e. current minimum > this test > current candidate
if(testsum>curmin && (!gotcandidate || testsum<newmin)){
newmin=testsum;
newa=testa;
newb=testb;
gotcandidate=true;
}
// Test a[cura+1]+b[curb]
// if cura+1 is out of bound then test
// a[0]+b[curb+1] instead
if(cura<a.length-1){
testa=cura+1;
testb=curb;
} else {
testa=0;
testb=curb+1;
}
testsum=a[testa] + b[testb];
// we got new candidate if
// this sum is greater than current minimum
// AND
// we haven't got candidate yet OR this sum is less than the current candidate
// i.e. current minimum > this test > current candidate
if(testsum>curmin && (!gotcandidate || testsum<newmin)){
newmin=testsum;
newa=testa;
newb=testb;
gotcandidate=true;
}
if(!gotcandidate){
System.out.println("Couldn't figure out next step for " + cura + ":" + curb);
return -1;
} else {
// advance a and b indexes
// to the newly found minimum
cura=newa;
curb=newb;
}
}
return newmin;
}
}
Oops, forgot to write up pairs in explanations
Here goes:
current min is a[i]+b[j];
next min will be amongs
a[i-1]+b[j+1] // test only if i>0
a[i+1]+b[j-1] // test only if j>0
a[i]+b[j+1] // if j+1 is out of bound test a[i+1]+b[0] instead
a[i+1]+b[j] // if i+1 is out of bound test a[0]+b[j+1] instead
amongst these candidates your next minimum is the smallest one which is
greater than the current minimum.
a: i-1 i i+1
b: j-1 j j+1
Minimum value will be a[0] + b[j] or a[i] + b[0]
so the answer is
int[] firstKMin(int k, int[] a, int b []){
int i = 1;
int j = 1;
int index = 1;
int[] answer = new int[k];
// This is special case
answer[0] = a[0] + b[0];
while(i < N && j < N){
x = a[i] + b[0];
y = a[0] + b[j];
if(x < y){
answer[index] = x;
i++;
}else{
answer[index] = y;
j++;
}
c++;
}
if(index < k){
if(i == N){
for(int l = j; l < N; l++){
answer[index] = a[0] + b[l];
index++;
}
}
if(j == N){
for(int l = i; l < N; l++){
answer[index] = a[i] + b[0];
index++;
}
}
}
return answer;
}
Since both are sorted array,The first element of both the array will be minimum. So the sum a[0]+b[0] will be less than any of other a[i]+b[j]
so the answer is straight
A[0] + B[0]
It's doable in O(N) but not easy. Look up the paper "Selection in X + Y and matrices with sorted rows and columns* ".
- lasthope December 23, 2013