If you enjoyed this video, you might also enjoy our courses: ⚙ Learn dynamic programming: inscod.com/dp_course 💡 Learn to solve popular coding interview problems: inscod.com/50problems_course ⌛ Learn time and space complexity analysis: inscod.com/complexity_course 🔁 Learn recursion: inscod.com/recursion_course

This channel is gold. Found him thru a udemy course and he is by far one of the best. He covers major topics with a little twist. Good to watch to exercise your algorithm muscles. More people will benefit if the channel blows up and I don't know how most people didn't find him

@insidecode

Жыл бұрын

Thanks for your support!

how did i missed these channel so far. beautiful explanation

@insidecode

Жыл бұрын

Thanks!

thank you for the visuals!!...I've been struggling with this qs and now it's clear

Awesome explanation!!

Hi, thanks for a good visual explanation. I have tried the provided code with queue.Queue data structure and I got TLE on the 7/15 test. By changing it to collections.deque it passed. So defenitly I would recommend deque instead of Queue as it is more performant. from collections import deque class Solution: def minMutation(self, start: str, end: str, bank: List[str]) -> int: bank = set(bank) if end not in bank: return -1 queue = deque() queue.append((start, 0)) visited = {start} while queue: gene, level = queue.popleft() if gene == end: return level for i in range(8): # len of gene for letter in 'ACGT': new_gene = gene[:i] + letter + gene[i+1:] if new_gene in bank and new_gene not in visited: queue.append((new_gene, level+1)) visited.add(new_gene) return -1

beautiful explanation sir

Is this the most optimal solution available? It seems more like a brute force solution where you're trying out every combination.

Very Good!

Hey. Could you please explain how to calculate the time complexity?

The narration is on different level, make it so easy to understand with the visuals.

@insidecode

Жыл бұрын

Thank you! By the way, how did you find this video? Was it recommended by KZread or did you find it somewhere else?

@supriyodam2812

Жыл бұрын

@@insidecode It was reccomended by the KZread.

Putting the exact solution in Java, however I am using a different approach for checking if the 2 strings differ by only 1 character public int minMutation(String start, String end, String[] bank) { Map map = new HashMap(); for(String s:bank) map.put(s,true); if(map.get(end) == null) return -1; if(start.equals(end)) return 0; Queue que = new ArrayDeque(); que.add(new Pair(start,0)); boolean[] visited = new boolean[bank.length]; while (!que.isEmpty()){ Pair polled = que.poll(); if(polled.getKey().equals(end)) return polled.getValue(); for(int i=0;i if(!visited[i]){ int diff = diff(polled.getKey(), bank[i]); if (diff == 1) { que.add(new Pair(bank[i], polled.getValue()+1)); visited[i] = true; } } } } return -1; } private int diff(String start,String curr){ int counter = 0; for(int i=0;i

Impressive.

Nicely explained. But how did you come up with the intuition that this is a possible graph problem ?

@insidecode

Жыл бұрын

It's because we have a states and transition case, we have an initial state and a goal state, and we can move to other states by performing transitions. When we have this situation, we usually solve the problem as a graph problem and use dfs or bfs. Another interesting problem of the same kind is this one: leetcode.com/problems/open-the-lock/

@sushantkapoor9002

Жыл бұрын

@@insidecode Got it. Thanks for help. I understand it much better now : ). Cheers !

I don't understand how this iterative solution is failing for 4 of the test cases. Any ideas would be greatly appreciated. Side note, I am quite sure this test case is broken as there is no change to be made to the start gene that is in the bank that brings us closer to the end gene: start = "AACCGGTT" end = "AAACGGTA" bank = ["AACCGATT","AACCGATA","AAACGATA","AAACGGTA"] expected mutations: 4 Iterative solution: We loop through the start gene, if we find a differing letter from the end gene, change our start gene to this letter and check if this is in the bank. If it is, continue to the next letter and try the same. If the mutation isn't in the bank, revert the change and continue looping. Continue trying to change start letters to end letters until we find a mutation which is in the bank. Keep looping through the letters until no changes are made, in which case there is no valid change to be made to start gene. (i.e no changes that are in the bank). if end not in bank: return -1 start = list(start) end = list(end) count = 0 prevCount = 0 while True: prevCount = count for i,letter in enumerate(start): if letter != end[i]: start[i] = end[i] if ''.join(start) not in bank: start[i] = letter continue else: count += 1 if count == prevCount: break if count == 0: return -1 else: return count

@benjaminpittman2169

Жыл бұрын

Had same issue initially as I was using a list and append() and pop(). Use a deque() and popleft()

@oliverheber599

Жыл бұрын

@@benjaminpittman2169 Hey thanks for the reply. The issue was a misunderstanding of the problem domain on my part. Some mutations take us further away from the end gene but are valid in the bank, allowing us to make further mutations which do bring us closer to the end gene, and finally reverting the initial mutation. Hope that makes sense. Thanks.

you could become the largest channel on the topic if you made more of these.

@insidecode

Жыл бұрын

I hope

Wow man,your teaching👌

@insidecode

Жыл бұрын

Thank you! By the way, how did you find this video? Was it recommended by KZread or did you find it somewhere else?

That was really good👍

@insidecode

Жыл бұрын

Thanks!

that was a great explaination

@insidecode

Жыл бұрын

Thank you! By the way, how did you find this video? Was it recommended by KZread or did you find it somewhere else?

can someone tell why this is not working public int minMutation(String start, String end, String[] bank) { if(start == end || start.length() != end.length() ) return -1; int count = 0; boolean contains = false; StringBuilder s = new StringBuilder(start); for(int i = 0 ; i if(end.equals(bank[i])){ contains = true; } } for(int i = 0 ; i if(s.charAt(i) != end.charAt(i)){ s.setCharAt(i , end.charAt(i)); if(checkContains(s , bank)){ count++; }else{ return -1; } } } if(contains){ return count; } return -1; } boolean checkContains(StringBuilder s , String[] bank){ for(int i = 0 ; i if(bank[i].equals(s.toString())){ return true; } } return false; }

In video skipped a part about complexity. My thoughts: l - length of banks s - length of start string Time comp = O(l * s) Memory comp = O(l)

@insidecode

Жыл бұрын

Yes, but the length of start string is constant, (8, as mentioned in the problem description), so we get O(l)

@v8kali-linux246

Жыл бұрын

@@insidecode when graph theory course available i love your course @Udemy

@insidecode

Жыл бұрын

@@v8kali-linux246 I'm making it, I'll try to finish it by the end of the actual year

Why are you talking about 32 mutations? 8^4=4096

@insidecode

Жыл бұрын

I meant the number of mutations a mutation can go to by changing one of its characters