9 Connect Ropes to Minimise the Cost

แชร์
ฝัง
  • เผยแพร่เมื่อ 24 ธ.ค. 2024

ความคิดเห็น • 116

  • @explorewithSomya_9
    @explorewithSomya_9 4 ปีที่แล้ว +81

    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 :)

  • @saurabhgupta4082
    @saurabhgupta4082 4 ปีที่แล้ว +79

    this question && top k frequent elements was asked today in coding round of convegenius.Thanks bro for such awesome content.

  • @mukulbakshi28
    @mukulbakshi28 4 ปีที่แล้ว +23

    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

  • @cripz4203
    @cripz4203 4 ปีที่แล้ว +12

    6:20 by this time I got the idea how to approach this problem. You are a genius teacher bhaiyaa.

  • @shhhhhhhhhh2686
    @shhhhhhhhhh2686 5 หลายเดือนก่อน +1

    This question was asked in my Goldman Sachs internship interview. Thanks bhaiya!

  • @GouravArora-hx2sb
    @GouravArora-hx2sb 2 หลายเดือนก่อน

    The Best playlist of HEAP :)

  • @1998ksh
    @1998ksh 4 ปีที่แล้ว +84

    Its similar to "Optimal Merge Pattern Problem" and "Huffman Coding".

  • @madmaxfury9773
    @madmaxfury9773 ปีที่แล้ว

    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. !!!!!!

    • @madmaxfury9773
      @madmaxfury9773 ปีที่แล้ว

      Just one question, by looking at the question looks like knapsack problem. Isn't it ?

  • @ronitkumar19
    @ronitkumar19 ปีที่แล้ว +1

    Thank you aditya verma ...This series was a pure gold for me :)

  • @rupalitiwari5012
    @rupalitiwari5012 4 ปีที่แล้ว +8

    thankyou so much. Please make some videos on graph and backtracking.

  • @NotNotNithin
    @NotNotNithin 3 ปีที่แล้ว +4

    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;
    }

  • @mushahidgillani6915
    @mushahidgillani6915 4 หลายเดือนก่อน

    Thanks dude for your tutorials. Very helpful

  • @kunalkhandelwal5526
    @kunalkhandelwal5526 2 ปีที่แล้ว

    As for me, everything is simple and clear. Thank you very much

  • @cricketInsights614
    @cricketInsights614 4 ปีที่แล้ว +6

    Tum shandaar ho bhai kya smjhate ho

    • @TheAdityaVerma
      @TheAdityaVerma  4 ปีที่แล้ว +12

      Thanks brother !!
      Do share the content where ever you feel right to help the channel grow !!

  • @ishangujarathi10
    @ishangujarathi10 ปีที่แล้ว

    loved the intuition

  • @jatinkumar4410
    @jatinkumar4410 ปีที่แล้ว

    Amazing explanation

  • @akshaykeswani3601
    @akshaykeswani3601 ปีที่แล้ว

    Good Explaination.

  • @animeponder
    @animeponder ปีที่แล้ว +1

    how can one get the idea of approaching min sol, like adding 2 min ele every time?

  • @vrandakansal5940
    @vrandakansal5940 3 ปีที่แล้ว

    Great question with amazing explanation

  • @codingwithoutcoffee
    @codingwithoutcoffee 4 ปีที่แล้ว +11

    @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.

    • @moviesflix7082
      @moviesflix7082 8 หลายเดือนก่อน

      Are you doing any job now?

  • @cr7johnChan
    @cr7johnChan 2 ปีที่แล้ว

    Guruji aapki kripa hai !

  • @proghead00
    @proghead00 3 ปีที่แล้ว

    Seamless. Thanks a lot.

  • @prernagolani9014
    @prernagolani9014 4 ปีที่แล้ว

    Great Explanation and very useful

  • @rkalpeshk
    @rkalpeshk 4 ปีที่แล้ว +8

    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);
    }
    }

  • @raunakagarwal6077
    @raunakagarwal6077 2 ปีที่แล้ว +4

    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;
    }
    };

  • @vrajeshbadgujar
    @vrajeshbadgujar ปีที่แล้ว

    good explaination

  • @paragroy5359
    @paragroy5359 4 ปีที่แล้ว +1

    Nice explanation sir...

  • @kailashjangir1530
    @kailashjangir1530 3 ปีที่แล้ว

    solved by just intution great bro❤❤

  • @Yash-afk
    @Yash-afk 5 หลายเดือนก่อน

    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);
    }
    }

  • @engineer8340
    @engineer8340 2 ปีที่แล้ว

    Bahut badhiya bahut badhiya

  • @apoorvchaturvedi2493
    @apoorvchaturvedi2493 3 ปีที่แล้ว

    Nicely explained!

  • @avisoft-l2p
    @avisoft-l2p หลายเดือนก่อน

    what a heap series maannn

  • @ashfaqhussain761
    @ashfaqhussain761 2 ปีที่แล้ว

    excellent explanation bhaiya👍

  • @anuj3089
    @anuj3089 4 ปีที่แล้ว

    very good explanation

  • @ankit_s
    @ankit_s ปีที่แล้ว +1

    Nice question

  • @willturner3440
    @willturner3440 4 ปีที่แล้ว

    Genius man

  • @justsomeguywithoutamustach9978
    @justsomeguywithoutamustach9978 6 หลายเดือนก่อน

    really interesting question

  • @luvgupta8495
    @luvgupta8495 2 ปีที่แล้ว +1

    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;
    }

  • @shubhi2648
    @shubhi2648 4 ปีที่แล้ว +1

    AFAIU
    does identification not match more of a knapsack ?

  • @athiban94
    @athiban94 2 ปีที่แล้ว +3

    This can be solved through dynamic programming as well.

  • @amansinghal4663
    @amansinghal4663 ปีที่แล้ว +1

    Gfg same question - Minimum cost of ropes

  • @aniketmasram6500
    @aniketmasram6500 3 ปีที่แล้ว

    Amazing 🔥

  • @svworld01
    @svworld01 3 ปีที่แล้ว +4

    this one is asked in amazon online assessment.

  • @akhilhooda740
    @akhilhooda740 3 ปีที่แล้ว +1

    nice!!!!!

  • @AdarshPradyut
    @AdarshPradyut 3 ปีที่แล้ว

    Thanks

  • @peaches7627
    @peaches7627 6 หลายเดือนก่อน

    how do i identify that this is a priority queue question like the k + smallest thing is not here only smallest factor is here

  • @emonhasan-up6gm
    @emonhasan-up6gm 4 ปีที่แล้ว

    Awesome bro

  • @zoraiznaeem2579
    @zoraiznaeem2579 4 ปีที่แล้ว +3

    can this question be solved using dp?

    • @willturner3440
      @willturner3440 3 ปีที่แล้ว

      Yes..

    • @imPriyansh77
      @imPriyansh77 9 หลายเดือนก่อน

      Yes, MCM format to be precise in DP

  • @ananysharma9290
    @ananysharma9290 3 ปีที่แล้ว

    Superb Sir

  • @ishigupta2649
    @ishigupta2649 4 ปีที่แล้ว

    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??

  • @karanpathak528
    @karanpathak528 3 ปีที่แล้ว +4

    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)

  • @louerleseigneur4532
    @louerleseigneur4532 4 ปีที่แล้ว

    merci

  • @joshithmurthy6209
    @joshithmurthy6209 2 ปีที่แล้ว

    this reminds me of huffman coding algorithm

  • @swasthiknayak5653
    @swasthiknayak5653 4 ปีที่แล้ว +3

    Isn't this huffman coding problem and even the approach is exactly same.

  • @mohitkumarbansal3486
    @mohitkumarbansal3486 3 ปีที่แล้ว

    bhaiya please graph pe series banado ap ke jab lecture dekhleta hu to thought process increase hojati he

    • @sleepypanda7172
      @sleepypanda7172 3 ปีที่แล้ว +1

      seems like he stopped making videos now sadly.
      Last Video was 7 months ago

  • @rahulbodyal2706
    @rahulbodyal2706 3 ปีที่แล้ว

    Bhai please graph ke upar b videos bana do

  • @rahulgunkar6308
    @rahulgunkar6308 2 ปีที่แล้ว +1

    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.

  • @pranshumehta3228
    @pranshumehta3228 2 ปีที่แล้ว

    Time complexity of this approach is n(logn) and by sorting also this would be same

    • @pranayavnish8028
      @pranayavnish8028 ปีที่แล้ว +1

      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

  • @onehp9759
    @onehp9759 3 ปีที่แล้ว +1

    mauj krdi sir

  • @runtime379
    @runtime379 3 ปีที่แล้ว +1

    u iz gem

  • @MOHITRANA-to7rf
    @MOHITRANA-to7rf 3 ปีที่แล้ว

    hi again .......................

  • @yashgupta-rs9ro
    @yashgupta-rs9ro 4 ปีที่แล้ว

    Sir humme cost push karni chaheye na ??

    • @jagrit07
      @jagrit07 4 ปีที่แล้ว +2

      Nahi, jo 2 smallest lengths ko combine kr k length ayegi wo push krni hai.

    • @imPriyansh77
      @imPriyansh77 9 หลายเดือนก่อน

      Nahi, cost toh update hoti rahegi. jo 2 elements nikale hain, unka sum push karna hai

  • @sayantaniguha8519
    @sayantaniguha8519 3 ปีที่แล้ว +3

    Isme pata ni thoda DP wali vibe ayi..
    Kisi aur ko vi aya kya ?

    • @sanjayvasnani988
      @sanjayvasnani988 3 ปีที่แล้ว +1

      Same. Matrix Chain Multiplication ke similar lag raha

    • @amanbhadani8840
      @amanbhadani8840 3 ปีที่แล้ว

      Dp tmhe pura aa gya?

    • @imPriyansh77
      @imPriyansh77 9 หลายเดือนก่อน

      Haa

  • @aanchalsharma5264
    @aanchalsharma5264 4 ปีที่แล้ว

    what is time complexity

    • @edutriangle4300
      @edutriangle4300 3 ปีที่แล้ว

      Time Complexity O(nlogn) and Space Complexity O(n).

  • @atulwadhwa192
    @atulwadhwa192 2 หลายเดือนก่อน

    GOOD Q

  • @HARSHAGRAWALBCE-nb3gb
    @HARSHAGRAWALBCE-nb3gb 3 ปีที่แล้ว +1

    priority queue

  • @vipulgupta3915
    @vipulgupta3915 3 ปีที่แล้ว +1

    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);
    }

  • @heavydriver183
    @heavydriver183 4 ปีที่แล้ว

    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

  • @MOHITRANA-to7rf
    @MOHITRANA-to7rf 3 ปีที่แล้ว

    hiiii

  • @yativishnoi5110
    @yativishnoi5110 2 ปีที่แล้ว +1

    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).

  • @ankurgupta4696
    @ankurgupta4696 4 ปีที่แล้ว

    in gfg this is giving tle in java

  • @kuldeepnarayanminj
    @kuldeepnarayanminj 4 ปีที่แล้ว +1

    laaajawaaab

  • @abbas.muzammil23
    @abbas.muzammil23 2 ปีที่แล้ว +7

    For practice: practice.geeksforgeeks.org/problems/minimum-cost-of-ropes-1587115620/1

  • @DroidHolicOfficial
    @DroidHolicOfficial 2 ปีที่แล้ว

    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;
    }

  • @harshita6683
    @harshita6683 ปีที่แล้ว

    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;

    }
    }