By doing the one-liner you end up guaranteed going over every element in the array. By checking the hashset on each element you will most likely get better performance, except in a degenerate case.
I hope this explanation helps someone who found this problem tricky - If two strings are of same length, how can be determine if one is a permutation of the other? One way is to check the frequencies of all the chars in s1 and s2. If they are exactly the same, that means they are permutations of each other. How many matches are needed? That will be equal to the number of characters allowed. In this case, the problem mentions that all are lowercase, so we need 26 matches. We start by initializing the freq of first n characters of s1. We do this for s2 as well (for its n characters only). If the freq of all 26 chars match at this point, we can simply return true. Otherwise, we will use sliding window to look for other substrings. We shift the window by 1 step. The freq of new char on right will increase. The freq of left most char in the previous window will decrease. Then, we can again check if the freq of all the 26 chars is exactly the same. If yes, they must be permutations of each other. So, return true. ```java class Solution { public boolean checkInclusion(String s1, String s2) { int n = s1.length(); int m = s2.length(); if(n > m) return false; int[] f1 = new int[26]; int[] f2 = new int[26]; for(int i=0; i<n; i++) f1[s1.charAt(i)-'a']++; for(int i=0; i<n; i++) // we will iterate only till n chars since those will form the initial permutation f2[s2.charAt(i)-'a']++; if (Arrays.equals(f1, f2)) return true; int idx = n; // start of next window while(idx < m){ // we have moved the window one step towards right // so freq of char at idx should increase // and freq of left most char in prev window should decrease char newChar = s2.charAt(idx); char prevChar = s2.charAt(idx-n); f2[newChar-'a']++; f2[prevChar-'a']--; if (Arrays.equals(f1, f2)) return true; idx++; } return false; } } ``` ### OPTIMIZED The previous solution will take O(26\*N) time complexity. We can optimize it further by using a `matches` variable to track the number of matched frequencies in s1 and s2. If it equals 26, we can return true. ```java class Solution { public boolean checkInclusion(String s1, String s2) { int n = s1.length(); int m = s2.length(); if(n > m) return false; int[] f1 = new int[26]; int[] f2 = new int[26]; for(int i=0; i<n; i++){ f1[s1.charAt(i)-'a']++; f2[s2.charAt(i)-'a']++; } int matches = initializeMatch(f1, f2); if (matches == 26) return true; int idx = n; // start of next window while(idx < m){ // we have moved the window one step towards right // so freq of char at idx should increase // and freq of left most char in prev window should decrease char newChar = s2.charAt(idx); char prevChar = s2.charAt(idx-n); // update freq for new character in the next window f2[newChar-'a']++; if(f2[newChar-'a'] == f1[newChar-'a']) matches++; // IMPORTANT: // we should reduces matches, if they were equal before the update for this char // one way to check if the freq increased by exactly 1 after update // which means, they must have been same before this update else if(f2[newChar-'a'] - 1 == f1[newChar-'a']) matches--; // IMPORTANT // if we update freq of both newChar and prevChar at the same time, that will not be correct // update freq for prev char (left most) of the prev window f2[prevChar-'a']--; if(f2[prevChar-'a'] == f1[prevChar-'a']) matches++; else if(f2[prevChar-'a'] + 1 == f1[prevChar-'a']) matches--; if(matches == 26) return true; idx++; } return false; } public int initializeMatch(int[] f1, int[] f2){ int count = 0; for(int i=0; i<26; i++){ if(f1[i] == f2[i]) count++; } return count; } } ``` gkgaurav31.github.io/posts/permutation-in-string/
""" 1 / \ 2 3 / \ \ 4 5 6 Initialization res = [] (to store the right side view) q = deque([1]) (initial queue containing the root node) Level 1 rightSide = None qLen = len(q) = 1 Process the level: node = q.popleft() (pops 1 from the queue) rightSide = 1 Add children of 1 to the queue: q.append(2), q.append(3) rightSide is 1, so res.append(1): res = [1] Queue now contains: [2, 3] Level 2 rightSide = None qLen = len(q) = 2 Process the level: node = q.popleft() (pops 2 from the queue) rightSide = 2 Add children of 2 to the queue: q.append(4), q.append(5) node = q.popleft() (pops 3 from the queue) rightSide = 3 Add children of 3 to the queue: q.append(None), q.append(6) rightSide is 3, so res.append(3): res = [1, 3] Queue now contains: [4, 5, None, 6] Level 3 rightSide = None qLen = len(q) = 4 Process the level: node = q.popleft() (pops 4 from the queue) rightSide = 4 No children to add to the queue node = q.popleft() (pops 5 from the queue) rightSide = 5 No children to add to the queue node = q.popleft() (pops None from the queue) Skip since node is None node = q.popleft() (pops 6 from the queue) rightSide = 6 No children to add to the queue rightSide is 6, so res.append(6): res = [1, 3, 6] Queue is now empty, so we exit the while loop Result The final right side view of the binary tree is [1, 3, 6].
""" 1 / \ 2 5 / \ \ 3 4 6 Step 1: Flatten the left subtree of 1 Call: dfs(1) Call: dfs(2) Call: dfs(3) root.left and root.right are None Return 3 (last node in the left subtree of 2) Call: dfs(4) root.left and root.right are None Return 4 (last node in the right subtree of 2) leftTail = 3, rightTail = 4 Set 3.right = 4 Set 2.right = 3, 2.left = None Return 4 (last node in the flattened subtree of 2) Step 2: Flatten the right subtree of 1 Call: dfs(5) Call: dfs(None) Return None Call: dfs(6) root.left and root.right are None Return 6 (last node in the right subtree of 5) leftTail = None, rightTail = 6 Return 6 (last node in the flattened subtree of 5) Step 3: Combine left and right subtrees of 1 leftTail = 4, rightTail = 6 Set 4.right = 5 Set 1.right = 2, 1.left = None Return 6 (last node in the flattened tree) """
The justification for using NoSQL was kind of lacking.Relational database do just fine with high read throughput. I don't think it's necessarily a bad choice, I'd say either SQL or NoSQL would be fine.
if python had int overflows, this would still not have been a bug, but a litation. also, r-l can produce an underflow. if r is relaly low and l really big. this didn't change anything
In place of the visit hashset, you could just set prereq[crs] = None whenever you've added it to the output list. Kind of like what you did for the other problem
The way you write the solution out in code, it seems simple, but I am almost certain the edge cases with this approach would have totally stumped me if I get this in an interview
Yes, but underneath it allocated 32 bits of memory to the value. When you add two of those numbers together, the memory slot doesnt have enough space to store that, causing an error.
@@impossikour3309 If your system has such limited memory that allocating an extra 32 bits crashes with OOM, the bug wasn't in the arithmetic: the bug was choosing python
came up with similar solution, with only 2 parameters for the inner function: res = [] def backtrack(i, total): if i == len(candidates) or sum(total) > target: return if sum(total) == target: res.append(total.copy()) return backtrack(i, total + [candidates[i]]) backtrack(i + 1, total) backtrack(0, []) return res
it's actually a very common bug and it's immediately obvious what went wrong when it does, so it gets fixed quickly. When someone makes an N+1 bug you find it 5 years later when the amount of accumulated data halts the query to a halt.
Thanks for great explanation. I can follow along once we decide l=start and r=end. I was stuck with l=start and l=start+1. How to decide where to place the 2 pointers initially?
Ok I am a full stack developer currently grinding on leetcode. I just don't understand why you don't share code on github. If you have shared then provide the link. Thank you so much for you explanation.
the assign right to left is silly ,it is pointless is easy if we just element the duplicates and assign just a single digit needs to be explained better
I like the solutions by neetcode but this one is particularly very confusing and does not come naturally. The following approach builds each permutation choosing one element at a time and further building up the solution. class Solution: def permute(self, nums: List[int]) -> List[List[int]]: res = [] self.dfsPermute(res,nums,[]) return res def dfsPermute(self,res,nums,curr): if len(curr)==len(nums): # base case when we found one permutation solution res.append(curr.copy()) # go over each element add it to the list for n in nums: # check to avoid dulicate value in the arr if n in curr: continue else: # call recursively for each case curr.append(n) self.dfsPermute(res,nums,curr) #undo the last chosen element and go to the other decision branch tree curr.pop()
void rotate(int *nums, int numsSize, int k) { int t=0; while(t<k){ for(int i=numsSize-1;i>=0;i--){ *(nums + (i+1))=*(nums+i); } numsSize++; *nums=*(nums + numsSize-1); numsSize--; t++; } } This code works fine on compilers but does not work on Leetcode can somebody explain plz 🥲😭🙏
