Completed all of the videos from this playlist in one go! And the best part is, almost all of them I was able to code on my own, by just focussing on the first few minutes of the video. Definitely, explained in the best way possible :)
Love it man, How you explain. I never thought i can understand such concepts so easy, because of you bro. Love to have more medium level question that is asked in interviews. Thank you so much
Java code: private static int connectRopes(int[] arr, int size) { PriorityQueue minHeap = new PriorityQueue(); int cost = 0; for (int i = 0; i < size; i++) { minHeap.add(arr[i]); } while (minHeap.size() >= 2) { int first = minHeap.poll(); int second = minHeap.poll(); cost += first + second; minHeap.add(first + second); } return cost; }
@Aditya Verma bohot hard smjaya hai bhai. Actually coding interviews ke liye revise kar rha hun, but practice chuti hui thi. Problem yeh nahi thi ki mujhe code karna nahi aata... CS kaa almost har baccha atleast implement toh kar hi skta hai.. but I guess GFG se padhna tiresome ho jaata hai.... I mean theory wise... But found your channel. Liked, shared and subscribed. Great content bhai... keep up the good stuff.
class Solution { public: //Function to return the minimum cost of connecting the ropes. long long minCost(long long arr[], long long n) { // Your code here long long ans=0; priority_queue pq; //Min Heap for(int i=0;i=2){ long long p=pq.top(); pq.pop(); long long q=pq.top(); pq.pop(); ans+=p+q; pq.push(p+q); } return ans; } };
Nice explanation bhaiya, here is how i did it in Java: import java.util.*; class connectRopes{ public static void main(String[] args) { int[] arr={1,2,3,4,5}; PriorityQueue min_heap= new PriorityQueue(); for (int val : arr) { min_heap.add(val); } System.out.println(min_heap); int cost=0; while(min_heap.size()>=2){ int f=min_heap.poll(); int s=min_heap.poll(); // System.out.println("//f+s "+(f+s)); cost+=(f+s); // System.out.println("//cost "+cost+" "); min_heap.add(f+s); } System.out.println(cost); } }
Simple Java Solution- private static int minCostToConnectRopes(int[] arr){ PriorityQueue pq = new PriorityQueue(); //min-heap int cost=0; for (int i : arr) { pq.add(i); } while (pq.size() > 1){ int first = pq.poll(); int second = pq.poll(); pq.add(first + second); cost += first + second; } return cost; }
min_heap will not work in case of merging exactly k consecutive ropes in array. try this with min heap: [3,5,1,2,6] k=3 expected answer = 25 but after applying min heap solution ans = 24 (incorrect)
You can't use sorting in this problem. At every step you have to choose 2 smallest ropes, join them and put the joined rope back. Sorting doesn't guarantee that you'll be choosing the 2 smallest ropes. e.g : 2 4 5 5 2 & 4 -> rem: 6 5 5, cost=6 5 & 5 -> rem: 6 10, cost=6+10 at last 6 & 10. cost = 6+10+16
public static void minCost(long arr[], int n) { PriorityQueue minHeap = new PriorityQueue(); for(long i : arr) { minHeap.add(i); } long cost =0; while(minHeap.size()>=2) { long first = minHeap.poll(); long second = minHeap.poll(); long temp =first + second; cost += temp; minHeap.add(temp); } System.out.println(cost); }
In this there is a error u shouls have added last remining elemnet in the heap while(----) {---- --} cost+=minheap.top(); return cost; //plz check it out! // as we r leaving last cost here it is 15
long long minCost(long long arr[], long long n) { // Your code here long long a,b; vector< long long> v(arr,arr+n); priority_queue< long long,vector< long long>,greater< long long>> pq; long long sum=0,cost=0; for( long long i=0;i1){ a=pq.top(); pq.pop(); b=pq.top(); pq.pop(); sum=a+b; cost+=sum; pq.push(sum); } return cost; } // Time Complexity O(nlogn) and Space Complexity O(n).
int minimumCost(int[] arr) { int cost = 0; PriorityQueue minHeap = new PriorityQueue(); for (int length : arr) { minHeap.add(length); } while(minHeap.size() > 1){ // Remove the two smallest lengths at any time int l1 = minHeap.remove(); int l2 = minHeap.remove(); // Add the length of new rope formed by combination of the above two lengths to the heap minHeap.add(l1 + l2); // Add the cost to the existing cost cost += l1 + l2; } return cost; }
class Solution { public int mergeStones(int[] stones, int k) { PriorityQueue minheap=new PriorityQueue(); int cost=0; int n=stones.length; for(int i=0;ik){ int first=minheap.peek(); minheap.poll(); int second=minheap.peek(); minheap.poll(); cost=cost+first+second; minheap.add(cost); } return cost;
Completed all of the videos from this playlist in one go! And the best part is, almost all of them I was able to code on my own, by just focussing on the first few minutes of the video. Definitely, explained in the best way possible :)
true brother i also
very true
bhai ab kaha per ho aap ?
this question && top k frequent elements was asked today in coding round of convegenius.Thanks bro for such awesome content.
Love it man, How you explain. I never thought i can understand such concepts so easy, because of you bro. Love to have more medium level question that is asked in interviews. Thank you so much
6:20 by this time I got the idea how to approach this problem. You are a genius teacher bhaiyaa.
Hi5
Still I will watch full video :D
This question was asked in my Goldman Sachs internship interview. Thanks bhaiya!
The Best playlist of HEAP :)
Its similar to "Optimal Merge Pattern Problem" and "Huffman Coding".
yes!
yes , like matching to MCM format
Yes
yeah
You are the best. I saw your 1st video and I was able to solve all the other problems just like that. You are 1000% best of best. !!!!!!
Just one question, by looking at the question looks like knapsack problem. Isn't it ?
Thank you aditya verma ...This series was a pure gold for me :)
thankyou so much. Please make some videos on graph and backtracking.
Java code:
private static int connectRopes(int[] arr, int size) {
PriorityQueue minHeap = new PriorityQueue();
int cost = 0;
for (int i = 0; i < size; i++) {
minHeap.add(arr[i]);
}
while (minHeap.size() >= 2) {
int first = minHeap.poll();
int second = minHeap.poll();
cost += first + second;
minHeap.add(first + second);
}
return cost;
}
Thanks dude for your tutorials. Very helpful
As for me, everything is simple and clear. Thank you very much
Tum shandaar ho bhai kya smjhate ho
Thanks brother !!
Do share the content where ever you feel right to help the channel grow !!
loved the intuition
Amazing explanation
Good Explaination.
how can one get the idea of approaching min sol, like adding 2 min ele every time?
Great question with amazing explanation
@Aditya Verma bohot hard smjaya hai bhai. Actually coding interviews ke liye revise kar rha hun, but practice chuti hui thi. Problem yeh nahi thi ki mujhe code karna nahi aata... CS kaa almost har baccha atleast implement toh kar hi skta hai.. but I guess GFG se padhna tiresome ho jaata hai.... I mean theory wise... But found your channel. Liked, shared and subscribed. Great content bhai... keep up the good stuff.
Are you doing any job now?
Guruji aapki kripa hai !
Seamless. Thanks a lot.
Great Explanation and very useful
JAVA CODE :
class Main{
public static void main(String[] args) {
int[] arr=new int[] {2,3,4,1,5};
PriorityQueue heap=new PriorityQueue();
int ans=0;
for(int x:arr){
heap.add(x);
}
while(heap.size()!=1){
int x1=heap.poll();
int x2=heap.poll();
int temp=x1+x2;
ans+=temp;
heap.add(temp);
}
System.out.println(ans);
}
}
class Solution
{
public:
//Function to return the minimum cost of connecting the ropes.
long long minCost(long long arr[], long long n) {
// Your code here
long long ans=0;
priority_queue pq; //Min Heap
for(int i=0;i=2){
long long p=pq.top();
pq.pop();
long long q=pq.top();
pq.pop();
ans+=p+q;
pq.push(p+q);
}
return ans;
}
};
good explaination
Nice explanation sir...
solved by just intution great bro❤❤
Nice explanation bhaiya, here is how i did it in Java:
import java.util.*;
class connectRopes{
public static void main(String[] args) {
int[] arr={1,2,3,4,5};
PriorityQueue min_heap= new PriorityQueue();
for (int val : arr) {
min_heap.add(val);
}
System.out.println(min_heap);
int cost=0;
while(min_heap.size()>=2){
int f=min_heap.poll();
int s=min_heap.poll();
// System.out.println("//f+s "+(f+s));
cost+=(f+s);
// System.out.println("//cost "+cost+"
");
min_heap.add(f+s);
}
System.out.println(cost);
}
}
Bahut badhiya bahut badhiya
Nicely explained!
what a heap series maannn
excellent explanation bhaiya👍
very good explanation
Nice question
Genius man
really interesting question
Simple Java Solution-
private static int minCostToConnectRopes(int[] arr){
PriorityQueue pq = new PriorityQueue(); //min-heap
int cost=0;
for (int i : arr) {
pq.add(i);
}
while (pq.size() > 1){
int first = pq.poll();
int second = pq.poll();
pq.add(first + second);
cost += first + second;
}
return cost;
}
AFAIU
does identification not match more of a knapsack ?
This can be solved through dynamic programming as well.
Using MCM to be precise
thanks!!
Gfg same question - Minimum cost of ropes
Amazing 🔥
this one is asked in amazon online assessment.
yeah
nice!!!!!
Thanks
how do i identify that this is a priority queue question like the k + smallest thing is not here only smallest factor is here
Awesome bro
can this question be solved using dp?
Yes..
Yes, MCM format to be precise in DP
Superb Sir
Sir k heap k ques h y kse pta lga h nd ...min heap p size 2 k equal kyu nhi kiya jssa aab tk krte aa rhe the??
min_heap will not work in case of merging exactly k consecutive ropes in array.
try this with min heap:
[3,5,1,2,6]
k=3
expected answer = 25
but after applying min heap solution ans = 24 (incorrect)
yeah, you're right
Right, then dp come into existence
How you get 25? Its not 37?
@@PRANAVMAPPOLI yes
@@PRANAVMAPPOLI Right bro
merci
this reminds me of huffman coding algorithm
Isn't this huffman coding problem and even the approach is exactly same.
bhaiya please graph pe series banado ap ke jab lecture dekhleta hu to thought process increase hojati he
seems like he stopped making videos now sadly.
Last Video was 7 months ago
Bhai please graph ke upar b videos bana do
While solving heap questions from leetcode there are actually four patterns in heap.. You have chosen 1/4 th pattern... Which is Top K elements.
Time complexity of this approach is n(logn) and by sorting also this would be same
You can't use sorting in this problem.
At every step you have to choose 2 smallest ropes, join them and put the joined rope back.
Sorting doesn't guarantee that you'll be choosing the 2 smallest ropes.
e.g : 2 4 5 5
2 & 4 -> rem: 6 5 5, cost=6
5 & 5 -> rem: 6 10, cost=6+10
at last 6 & 10. cost = 6+10+16
mauj krdi sir
u iz gem
hi again .......................
Sir humme cost push karni chaheye na ??
Nahi, jo 2 smallest lengths ko combine kr k length ayegi wo push krni hai.
Nahi, cost toh update hoti rahegi. jo 2 elements nikale hain, unka sum push karna hai
Isme pata ni thoda DP wali vibe ayi..
Kisi aur ko vi aya kya ?
Same. Matrix Chain Multiplication ke similar lag raha
Dp tmhe pura aa gya?
Haa
what is time complexity
Time Complexity O(nlogn) and Space Complexity O(n).
GOOD Q
priority queue
public static void minCost(long arr[], int n) {
PriorityQueue minHeap = new PriorityQueue();
for(long i : arr) {
minHeap.add(i);
}
long cost =0;
while(minHeap.size()>=2) {
long first = minHeap.poll();
long second = minHeap.poll();
long temp =first + second;
cost += temp;
minHeap.add(temp);
}
System.out.println(cost);
}
In this there is a error u shouls have added last remining elemnet in the heap
while(----)
{----
--}
cost+=minheap.top();
return cost;
//plz check it out!
// as we r leaving last cost here it is 15
hiiii
long long minCost(long long arr[], long long n) {
// Your code here
long long a,b;
vector< long long> v(arr,arr+n);
priority_queue< long long,vector< long long>,greater< long long>> pq;
long long sum=0,cost=0;
for( long long i=0;i1){
a=pq.top();
pq.pop();
b=pq.top();
pq.pop();
sum=a+b;
cost+=sum;
pq.push(sum);
}
return cost;
}
// Time Complexity O(nlogn) and Space Complexity O(n).
in gfg this is giving tle in java
No
laaajawaaab
For practice: practice.geeksforgeeks.org/problems/minimum-cost-of-ropes-1587115620/1
int minimumCost(int[] arr) {
int cost = 0;
PriorityQueue minHeap = new PriorityQueue();
for (int length : arr) {
minHeap.add(length);
}
while(minHeap.size() > 1){
// Remove the two smallest lengths at any time
int l1 = minHeap.remove();
int l2 = minHeap.remove();
// Add the length of new rope formed by combination of the above two lengths to the heap
minHeap.add(l1 + l2);
// Add the cost to the existing cost
cost += l1 + l2;
}
return cost;
}
class Solution {
public int mergeStones(int[] stones, int k) {
PriorityQueue minheap=new PriorityQueue();
int cost=0;
int n=stones.length;
for(int i=0;ik){
int first=minheap.peek();
minheap.poll();
int second=minheap.peek();
minheap.poll();
cost=cost+first+second;
minheap.add(cost);
}
return cost;
}
}