Bus Routes | Dry Run | Intuition | UBER | Leetcode-815

Поділитися
Вставка
  • Опубліковано 22 гру 2024

КОМЕНТАРІ • 75

  • @codestorywithMIK
    @codestorywithMIK  Рік тому +45

    Happy Diwali to everyone of you.
    My love and blessings to everyone ❤❤❤❤🪔🪔🪔

  • @prudhvirajmacherla9854
    @prudhvirajmacherla9854 Рік тому +18

    I started seeing this channel when it was having 100 subscribers now it's nearly above 10k all bcoz of clearly explaining the concept with same belief I expect you to start contest solutions

  • @wearevacationuncoverers
    @wearevacationuncoverers Рік тому +2

    No channel can beat your way of explanation. It's different and unique.

  • @dreamiitians4909
    @dreamiitians4909 Рік тому +3

    I see many solution but your solution is very very nice thanks a lot !!
    (This question asked in Phonepe Interview 2023-sept.)

    • @codestorywithMIK
      @codestorywithMIK  Рік тому

      You are most welcome
      Thank you so much for sharing company tag ❤️🙏

  • @kunal4710
    @kunal4710 Рік тому +2

    INTUITION -
    As in the question least number was given src,target was given hence thought of bfs
    /*
    Think of question as a Metro use case , here you have to start your journey from your nearest metro station that is in this case is the source Once you have seated in the metro , you can go to n metro station and if in this n station one is your destination(target) station then well and good you reached your target, but if target is not on this route then you have to switch metro , so from a particular station check which metro is available and sit on that metro which you have not taken before and repeat the same process
    */
    int numBusesToDestination(vector& routes, int source, int target) {

    //No need to take metro
    if(source==target){
    return 0;
    }
    int n=routes.size();
    //to store from each metro station which metro trains are available
    unordered_map adj;
    for(int metro=0;metro

  • @muditkhanna8164
    @muditkhanna8164 Рік тому +4

    i assumed the bus routes as metro lines and the question got way easier, all they are asking the minimum metro lines to switch to reach the destination, the intuition also works with the examples you can relate to. i was confused thinking its asking the shortest path.

  • @md.tamaltahasinkhan6448
    @md.tamaltahasinkhan6448 Рік тому +4

    Firtst tried to BFS through the adjacent bus stops but got MLE in case 43. Then tried BFS for bus routes keeping track of the bus stops in the bus routes using map and vector. It got accepted.
    Now watching your video for most optimal solution. ❤

    • @codestorywithMIK
      @codestorywithMIK  Рік тому +2

      I am glad you tried BFS through adjacent bus as well. Although it gives MLE but it teaches us many things. Different approaches often teach us a lot.

    • @darkstudio3170
      @darkstudio3170 Рік тому

      When you are doing BFS through adjacent bus , how did you maintain the number of bus counts, did you tried each path and calculate min bus count ?

    • @md.tamaltahasinkhan6448
      @md.tamaltahasinkhan6448 Рік тому

      @@darkstudio3170 actually I kept the bus count in a map for each of the bus stations.
      Take an example like below
      routes = [[1,2,7],[3,6,7]], source = 1, target = 6
      1 has two adjacents 2 & 7
      2 has two adjacents 1 & 7
      3 has two adjacents 6 & 7
      6 has two adjacents 3 & 7
      7 has four adjacents 1, 2, 3 & 6 (cause you can visit all these nodes from 7 directly)
      when I visit '1' (source) for the first time, I set all its adjacent bus route count value to '1' in the map.
      that means
      map[1] = 0;
      map[2] = 1;
      map[7] = 1;
      then for '2': all its adjacent are already visited.
      for '7': 1 & 2 are already visited, but 3 and 6 was not visited before.
      therefore,
      map[3] = map[7] + 1 = 1 + 1 = 2;
      map[6] = map[7] + 1 = 1 + 1 = 2;
      when I found the target then returned the value stored in the map. like
      return map[6];
      if(map.find(6) == map.end()) return -1;
      let me know if its still not clear.

  • @iamnoob7593
    @iamnoob7593 2 місяці тому +1

    Wow this was a tough BFS question. Thanks again for brilliant explanation.

  • @souravjoshi2293
    @souravjoshi2293 Рік тому +1

    super duper clean. I almost solved it on my own, just got MLE . Using index in map was really smart.

  • @VishalYadav-gk1kg
    @VishalYadav-gk1kg 5 місяців тому +1

    Very nice explanation sir, Thank you!

  • @HealthyOm
    @HealthyOm Рік тому +1

    happy diwali bhaiaya .... aaj aapki story sunke problem sol karneka try kiya aur ho gaya hehehehheehhe :) :) :) :) ....... love u bhaiaya 😘😘😘😘😘

  • @newglobal7271
    @newglobal7271 Рік тому +1

    Happy Diwali Bhaiya .. Day 49 completed .. Thank You 🙏🙏🙏🙏..

  • @prudhvirajmacherla9854
    @prudhvirajmacherla9854 Рік тому

    Will be waiting eagerly and I will make sure I will remember you for every contest and I hope u start it as soon

  • @souravdubey4578
    @souravdubey4578 Рік тому +1

    bhahiya leetcode k contests k bhi solutions post kiya kro please and please post 1 video of begginer dp playlist daily

  • @anshukmishra4520
    @anshukmishra4520 Рік тому

    Happy Diwali Bhaiya 🎆🎆🎆🎆.

  • @AmarjeetKumar-to9ub
    @AmarjeetKumar-to9ub Рік тому +2

    Happy Diwali Sir :)

  • @sauravchandra10
    @sauravchandra10 Рік тому +1

    Happy diwali bhaiya!

  • @mohithadiyal6083
    @mohithadiyal6083 Рік тому

    The best explanation 😊 ,also Happy Diwali 🪔

  • @FanIQQuiz
    @FanIQQuiz Рік тому

    Awesome explanation bro.

  • @vineetkumar2899
    @vineetkumar2899 Рік тому

    Best ❤

  • @umeshbisht1054
    @umeshbisht1054 Рік тому

    Thanku bhaiya ❤

  • @iWontFakeIt
    @iWontFakeIt Рік тому

    beautiful! ❤
    happy diwali 🪔

  • @DeepakSingh-fd2ix
    @DeepakSingh-fd2ix Рік тому

    sir please contest ke solutions bhi upload kiya karo

  • @DevOpskagyaan
    @DevOpskagyaan Рік тому

    Too good

  • @taarakmehtakaoolthachasmat4649

    Happy diwali sir

  • @weirdo12121
    @weirdo12121 Рік тому

    sir I think the Time complexity will (m*k*m) instead of (m*k^2) as in the worst case in the queue we would be visiting each bus and for each bus we would be exploring the stop the bus will be visiting and for that stop we will be exploring the buses which will that visit that stop.
    Please correct me sir if I am wrong .

  • @tusharnanda3885
    @tusharnanda3885 Рік тому

    A humble request , if you could post leetcode contest 3rd and 4th question.

  • @tutuimam3381
    @tutuimam3381 Рік тому +1

    ❤❤❤❤❤❤❤

  • @kamranwarsi12b22
    @kamranwarsi12b22 Рік тому +1

    since we want to store the source int the queue , why we are not directly doing this q.push(source) as the source is already given ??

    • @codestorywithMIK
      @codestorywithMIK  Рік тому +2

      That source can be present in multiple routes (indices). We must be able to know from which possible routes(bus) we can start. Hence we must store the indices in which source is present

    • @kamranwarsi12b22
      @kamranwarsi12b22 Рік тому

      @@codestorywithMIK thnx , understood

  • @ashwint959
    @ashwint959 3 місяці тому

    You missed the edge case where source is not present in any of the routes I guess..

  • @prudhvirajmacherla9854
    @prudhvirajmacherla9854 Рік тому +1

    This diwali I expect @codestorywithmik to start discussing leetcode contest qns for better improvement of student coding knowledge

    • @codestorywithMIK
      @codestorywithMIK  Рік тому +2

      Will definitely start this on a regular basis. 🙏🙏😇😇❤️❤️
      And wish you a very happy and prosperous diwali ❤️❤️

  • @ManishGupta-lz8ho
    @ManishGupta-lz8ho Рік тому +1

    happy Diwali bhaiya, idk plz aap time nikal kr contest ka solution video bnao na plzzzz 😢

    • @xiaoshen194
      @xiaoshen194 Рік тому +1

      Coding Mohan ko follow Kiya kro. Uska seg tree playlist acha h.

  • @sanjaykatta6499
    @sanjaykatta6499 Рік тому

    For this approach, I was getting TLE. 43/49 were passing.
    public int numBusesToDestinationv1(int[][] routes, int source, int target) {
    Map adj = new HashMap();
    for (int[] route : routes) {
    for (int i = 0; i < route.length; i++) {
    for (int j = i + 1; j < route.length; j++) {
    adj.computeIfAbsent(route[i], k -> new ArrayList()).add(route[j]);
    adj.computeIfAbsent(route[j], k -> new ArrayList()).add(route[i]);
    }
    }
    }
    for (Map.Entry entry : adj.entrySet()) {
    System.out.println(entry.getKey() + " : " + entry.getValue());
    }
    Queue queue = new ArrayDeque();
    queue.add(new Pair(source, 0));
    Set visited = new HashSet();
    visited.add(source);
    while (!queue.isEmpty()) {
    Pair node = queue.poll();
    int u = node.getKey();
    int bus = node.getValue();
    if (u == target) return bus;
    if (adj.containsKey(u)) {
    for (int v : adj.get(u)) {
    if (!visited.contains(v)) {
    visited.add(v);
    queue.add(new Pair(v, bus + 1));
    }
    }
    }
    }
    return -1;
    }

  • @knoxmacroboy7272
    @knoxmacroboy7272 Рік тому +1

    since source and target is given cant we do it using dijkstra or any of the algorithms

    • @xiaoshen194
      @xiaoshen194 Рік тому +1

      Abe minimum cost nhi minimum buses btani h 😂. Mtlb minimum nodes traversed.

  • @rahulraj_iitgn
    @rahulraj_iitgn Рік тому +1

    why you included while(sz--){...code...} inside while(!que.empty()){...code...}?

    • @codestorywithMIK
      @codestorywithMIK  Рік тому +1

      Because we want to traverse level by level in BFS.
      Always remember that when we want to find a target in shortest distance, always prefer writing this way of doing BFS. It traverses level by level.
      sz = number of nodes in current level

    • @rahulraj_iitgn
      @rahulraj_iitgn Рік тому

      @@codestorywithMIK Ok will do this way. But just I am curious why in any article/video i referred so far, i haven't found this way, is it like they preassume that there is only one source they are starting with? Thanks

    • @lofireverbz-wy7go
      @lofireverbz-wy7go Рік тому

      we also use dp sometimes than how to identify whether we have to use dp or graph? any trick mik bhaiya?@@codestorywithMIK

  • @shivaggarwal4073
    @shivaggarwal4073 Рік тому +1

    I tried to apply dijkstra but it failed

    • @xiaoshen194
      @xiaoshen194 Рік тому +1

      Fail hi hoga cuz tujhe minimum buses btani h, cost nhi. Moreover source node multiple routes mein available h.

  • @codeandtalk6
    @codeandtalk6 Рік тому

    ❤❤❤

  • @deepanshupant453
    @deepanshupant453 Рік тому

    Sir your content is amazing but the presentation of thumbnails are not upto the mark which restricts the viewership... If you want to improve let's connect...as a thumbnail designer may be i can help you with that

    • @codestorywithMIK
      @codestorywithMIK  Рік тому +2

      Hi there,
      Thank you so much for this feedback ❤️
      Actually i have received this couple of times. I am curious now and want to know what are the things missing in the thumbnail. Can you please jot down some points ?
      Let me then think through it.

    • @deepanshupant453
      @deepanshupant453 Рік тому

      ​@@codestorywithMIKsure sir
      Look due to the high supply of videos on UA-cam there are lot of options for viewers and your teaching method is super easy but thumbnails make it seems difficult at the first place... Second visually appealing thumbnails boost the ctr for the channel and eventually UA-cam promote it as more viewer's show interest in the video but in your case they are not appealing so viewers who know you watch your videos coz they are aware of your content but for new viewers you need to make them click or create curiosity there are more technicals things on which you can work and genuinely if you see UA-cam as a serious game i would love to have a meeting with you and we can discuss further.

  • @aryansrivastava6692
    @aryansrivastava6692 3 місяці тому

    Man this sucks, couldn't solve this easy problem 😢😢😢😢

  • @DeepakSingh-fd2ix
    @DeepakSingh-fd2ix Рік тому

    please sir

  • @utkarshsingh2747
    @utkarshsingh2747 Рік тому +1

    Happy diwali Bro! Making life easy for eveyone!🪔🪔❤

  • @DeepakSingh-fd2ix
    @DeepakSingh-fd2ix Рік тому

    please sir

  • @DeepakSingh-fd2ix
    @DeepakSingh-fd2ix Рік тому

    please sir