Maximum Sum Combination | 25 September | POTD | GFG Problem of the Day | C++ | Java | Python.

[@bugsincode]

Like👍 | Share✌✌ | Subscribe▶ Solution Link: github.com/BugsInCodeYT/Problem-Of-The-Day-gfg/tree/main/Maximum%20Sum%20Combination%5B25-September-2023%5D EDIT: Space Complexity is O(n).

[@sardarsvlog9]

Very good explanation

[@debarpanjana399]

space complexity should be O(n) right?

[@bugsincode]

Yes, you're right buddy. The idea that I was using behind merge sort was [recursion depth(logn) and extra space(n)]. But practically it is O(n) because the code doesn't gets executed in parallel. So the correct space complexity will be: - O(n+n)=> O(n) which is due to merge sort/quick sort and priority queue. Thanks for the comment👍.

[@sandeepdhiman9887]

Not able to understand this line PriorityQueue pq = new PriorityQueue((a,b)->{ if(a[0]==b[0]) return b[1]-a[1]; return b[0]-a[0]; }); can you please explain?

[@bugsincode]

In this line, I'm declaring a priority with a custom comparator.I hope you know that comparator is used to define a custom sorting criteria. It will basically sort the elements in descending order on the basis of sum combinaton of elements and sum is represented by index 1. And if sum of two values is equal then is will first give priority to value having larger index.

[@parthshah6343]

@@bugsincode Simply single statement return b[0]-a[0]; will also work, instead of adding if condition.

[@SCSArumugaperumal]

Anna what if A=[1,2,3] and B=[1,1,100] and k = 2. How our solution works in these kinda situation. I'm beginner and I know I'm missing something so please do correct me

[@bugsincode]

Ok let me explain: We are using a priority queue which will give values with greater sum first. After running the first "for loop", the priority queue will look like: (101,2) , (102,2) , (103,2). Now we will come to "while loop": Popping first value will give sum = 103 which is the largest sum possible. Then do k--; We'll store in ans. After this it will also store a new pair(3,1) in the priority queue. PriorityQueue: (101,2) , (102,2) , (3,1) Now in the second iteration it will pop out 102. And now while loop will break. Beacuse k==0. Hence the output will be: 103, 102. Now I hope this is clear to you. Feel free to ask doubts.

[@SCSArumugaperumal]

@@bugsincode crystal clear. Thanks alot❣

[@ankitgupta2745]

In this code, i am not able to understand this line, if(ind-1 >= 0){ pq.push({sum - B[ind] + B[ind - 1], ind - 1}); } Please explain me

[@bugsincode]

See a sum combination is basically A[i] + B[j]. Right? i and j can be any index in array A and B. Inside the while loop we have sum = unknown(A[i]) + B[N-1]. This is very important to understand because we are initialising priority queue with every value in A + B[N-1]. So we can get value of A[i] by doing " sum-B[ind] ".Here ind is the index that I'm storing as a pair with sum. Now we just need to add the new value to A[i] so the new sum will be: A[i] + B[ind-1]. And this is nothing but sum-B[ind]+B[ind-1]. Now I hope it is clear to you. One more thing is: ind-1 can go out of bound for ind=0. That's why I'm checking the condition.