My intial approach was sorting the elements and when the element is similar to the previous element , we can just ignore. Oh am i so wrong. When you try to select an element through swapping , the sorted nature of the array is lost therefore , it is impossible to know whether the current element is already used or not. that is why hashmap is neccessary.This enables us to know whether the element is already used or not
3:15 why a regular brute force decision tree doesn’t work (produces duplicate permutations because the original array had duplicate numbers) This happens because you start off two recursive trees with the same number so these sub trees produce duplicates. At the root of the tree you would have two paths that start with 1 and these would produce duplicate permutations. So we used hashmap (inputNumber to countInInputArray) representation of the input array and work with that, so that instead of the root having two nodes that start with 1, it only has 1 node that starts with 1. This constraint is what prunes duplicate paths from decision tree. It is also applied recursively at all levels
There is no such thing, leetcode style problems require you to know the solution first and expect yourself to be able to solve similar problem in the future. Most of the time it is practicing first before solving a problem rather than solving a problem to practice.
If anyone is having problems with perm.copy() saying with an Attribute Error: List object has no Attribute to copy, you can use the List keyword "List(perm)" OR you can do what I did which is to take a slice of the list instead: "perm[:]". Either way, excellent solution. The idea of using a Hashmap came to mind but I was struggling with how to make use of it but your video did an amazing job explaining how to utilize it well.
I usually pick up my leetcode problems if you have made a solution video on them because I find your approach quite intutive and easy to follow. But for this one, I think this is simpler approach: class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: ans=[] def dfs(num,scope): if len(scope)==0: ans.append(num.copy())
visited=set() for i in range(len(scope)): if scope[i] not in visited: visited.add(scope[i]) dfs(num+[scope[i]], scope[:i]+scope[i+1:]) dfs([],nums) return ans
@@priyankrajvansh8428 because you are using the same location in memory and you are making changes to it, that is ans willl just have a pointer to the nums arrray. If you dont make a copy, at the end, ans willl be pointing to an empty arrray. Making a copy is like taking a screeenshot of the arrray at that point in time and it is stored in a new mem location
Why can't you just do the same algorithm as in Permutations 1 but make your result a set? Then the duplicate permutations would be avoided and you can convert to a list before returning? Could you also just sort the input and then in the recursion just check if the current decision is the same as the previous one, because that should theoretically get rid of the redundant branches.
Was pulling my hair wondering why my solution wasn't working so I decided to check here, I was just missing .copy() and now it works, smh. Can anyone explain the importance of .copy() and why it wouldn't work without it, ty!
So, you do a DFS, which goes depth wise, when you reach base case of last level n, you have to go down the 2nd branch of n-1 level. We call it popping back. So we have to make the Items as they should be for that level. Just about basic DFS and backtracking, would be easy to understand this
I solve this problem by modify the solution from Permutation I (still using Tree). - if array.length === 1 then return the array - place unique integers (uniqueArray acquired from duplicatesArray) for nodes - then, for the next nodes, delete from the duplicatesArray of node's number - recurse(deletedDuplicatesArray) 😁
Instead of using a hashmap why cant we just avoid duplicates to the result array? Is it to have better TC we eliminate the hassle of exploring duplicate paths?
I have problem understanding the line 11: res.append(perm.copy()) Why should we make a copy of the "perm" list? The program won't work if I did not make a copy of the "perm" list. I don't understand the reason explained in the video. Can someone help me out?
if you simply append, python is passing only the reference of perm into res. This means that if perm is changed (it is in the next step), it will change the value of perm inside res too, which is not desirable.
No, this wouldn't work. For cases like [0,1,0,0,9] after sorting it, it becomes [0,0,0,1,9], after a few permutations, we get [0,9,0,1,0] we can see that at this point, we don't have duplicates adjacent to each other, which breaks the algorithm. ex. the last 3 elemts 0,1,0 lets permute them, and we can see that duplicate permutations are produced even if we skip duplicate adjancent numbers: 0,1,0 0,0,1 1,0,0 0,1,0 see? 0,1,0 is produced again. I got stuck why your solution doesn't work for quite a while and came up with this explaination, hope this helps!
Cant we do something similar to the permutations I solution but instead before adding it to the resPerms, in the solution below, we check if that list is already in the result? if pcopy not in resPerms: resPerms.append(pcopy). I know you cant use a set because lists are mutable so would checking the existence of the list in the resPerms list be invalid? LC seems to accept the answer. class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: def helper(i): if i == len(nums): return [[]] resPerms = [] perms = helper(i + 1) for p in perms: for j in range(len(p) + 1): pcopy = p.copy() pcopy.insert(j, nums[i]) if pcopy not in resPerms: resPerms.append(pcopy) return resPerms return helper(0)
res=[] perm=[] nums.sort() def dfs(loop): if not loop: res.append(perm.copy()) return for i in range(len(loop)): if i > 0 and loop[i] == loop[i-1]: continue perm.append(loop[i]) dfs(loop[:i] + loop[i+1:]) perm.pop() dfs(nums) return res
Can someone explain to me why we did perm.pop(). And am I correct in assuming that we we count[n] += 1 after calling dfs() to restore the count for the next half of the decision tree? Please help me out 😅
think of it this way,you have appended the value and decremented its entry in the dictionary/hashmap.When you return back to this point after the function call is executed you would want to pop out the added value and increment the entry in the hashmap before going for the next entry in the loop ,otherwise you may miss some numbers in the permutation because for the next iteration of the loop the dictionary would have changed!..basically your logic is correct ! if you want more insight try dry running with this example nums=[1,2,2]
When you use res.append(perm) you're appending a reference to perm, so any changes you make to perm will also change all of the permutations in result. You create and append a copy of perm to avoid this.
IMHO, the complexity is O(N!), when all elements are unique (number of permutations of ordering n numbers in a row is n!). If you were interviewing with this question, explaining and solving it so elegantly but messing up the complexity, it would likely change your rating from "Hire" to "Leaning hire". It is more important than getting everything right in your code.
What if instead of the hashmap you used index of the array and just performed permutation as before but while appending in index array appeneded the value at the index?
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
My intial approach was sorting the elements and when the element is similar to the previous element , we can just ignore. Oh am i so wrong. When you try to select an element through swapping , the sorted nature of the array is lost therefore , it is impossible to know whether the current element is already used or not. that is why hashmap is neccessary.This enables us to know whether the element is already used or not
Thank you bro for this explanation
Same approach with me. I were pretty confident to solve this problem but after many hours, I give up
As always great way to describing the problem statement and then implementing it in code.
3:15 why a regular brute force decision tree doesn’t work (produces duplicate permutations because the original array had duplicate numbers)
This happens because you start off two recursive trees with the same number so these sub trees produce duplicates. At the root of the tree you would have two paths that start with 1 and these would produce duplicate permutations.
So we used hashmap (inputNumber to countInInputArray) representation of the input array and work with that, so that instead of the root having two nodes that start with 1, it only has 1 node that starts with 1. This constraint is what prunes duplicate paths from decision tree. It is also applied recursively at all levels
did any of you get this solution on your own? i feel like its impossible to do a problem unless we have encountered them or similar problems before
I feel the same, I'm hoping i'll be able to solve these on my own as I practice more
There is no such thing, leetcode style problems require you to know the solution first and expect yourself to be able to solve similar problem in the future. Most of the time it is practicing first before solving a problem rather than solving a problem to practice.
Worst time complexity should be O(N * N!) in case there's no duplicates in input array.
Do we have more efficient solution for this
O(N * N!) is O(N!) in big-O notation... Also we will always have O(N!) when the problem is about permutations.
If anyone is having problems with perm.copy() saying with an Attribute Error: List object has no Attribute to copy, you can use the List keyword "List(perm)" OR you can do what I did which is to take a slice of the list instead: "perm[:]". Either way, excellent solution. The idea of using a Hashmap came to mind but I was struggling with how to make use of it but your video did an amazing job explaining how to utilize it well.
using .copy() is slower anyways I think so you're just better off using [:]
Another excellent video, with amazingly clear explanations. The problem analysis part is extremely educational. Thank you
You can also use Counter from collections, and just super clear video btw! thank you for the neet explanation :3
It's always that one hater that dislikes something--annoying. Great Conceptual Overview.
your explanations are much better than algoexpert lol
I usually pick up my leetcode problems if you have made a solution video on them because I find your approach quite intutive and easy to follow. But for this one, I think this is simpler approach:
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
ans=[]
def dfs(num,scope):
if len(scope)==0:
ans.append(num.copy())
visited=set()
for i in range(len(scope)):
if scope[i] not in visited:
visited.add(scope[i])
dfs(num+[scope[i]], scope[:i]+scope[i+1:])
dfs([],nums)
return ans
I did a similar approach, with a set for every invocation of dfs (y) Nice
how is it going now dude ?
could you please tell me why do we need to make a copy of num before appending it to ans?been struggling with it really!
@@priyankrajvansh8428 because you are using the same location in memory and you are making changes to it, that is ans willl just have a pointer to the nums arrray. If you dont make a copy, at the end, ans willl be pointing to an empty arrray. Making a copy is like taking a screeenshot of the arrray at that point in time and it is stored in a new mem location
@@Mr.Bombastic-tl5ic thank you very much
Why can't you just do the same algorithm as in Permutations 1 but make your result a set? Then the duplicate permutations would be avoided and you can convert to a list before returning? Could you also just sort the input and then in the recursion just check if the current decision is the same as the previous one, because that should theoretically get rid of the redundant branches.
you could do this, then store each permutation in a set as a tuple, and before appending check if that tuple exists in the set
I did this as my initial approach, kinda felt like cheating, and it was slow - beats 7%
The best explanation, everything is crystal clear now.
Commenting for better reach so that youtube algorithm rank this video higher
Python make it look so easy. Java is honestly a nightmare
feeling dumb everyday, thanks for the explanation
Very clear description and explanation. Thank you!
Can you also simulate the order in which the output will be generated, it will help to imagine the process.
Was pulling my hair wondering why my solution wasn't working so I decided to check here, I was just missing .copy() and now it works, smh. Can anyone explain the importance of .copy() and why it wouldn't work without it, ty!
Don't get the incrementing of count[n]
Bro that's backtracking step
So, you do a DFS, which goes depth wise, when you reach base case of last level n, you have to go down the 2nd branch of n-1 level. We call it popping back. So we have to make the Items as they should be for that level. Just about basic DFS and backtracking, would be easy to understand this
I solve this problem by modify the solution from Permutation I (still using Tree).
- if array.length === 1 then return the array
- place unique integers (uniqueArray acquired from duplicatesArray) for nodes
- then, for the next nodes, delete from the duplicatesArray of node's number
- recurse(deletedDuplicatesArray)
😁
Instead of using a hashmap why cant we just avoid duplicates to the result array? Is it to have better TC we eliminate the hassle of exploring duplicate paths?
I have problem understanding the line 11: res.append(perm.copy())
Why should we make a copy of the "perm" list?
The program won't work if I did not make a copy of the "perm" list.
I don't understand the reason explained in the video. Can someone help me out?
if you simply append, python is passing only the reference of perm into res. This means that if perm is changed (it is in the next step), it will change the value of perm inside res too, which is not desirable.
Hi, what if you sort the array first? then if nums[i] = nums[i-1], you could directly jump to next loop
No, this wouldn't work.
For cases like [0,1,0,0,9]
after sorting it, it becomes [0,0,0,1,9],
after a few permutations, we get [0,9,0,1,0]
we can see that at this point, we don't have duplicates adjacent to each other, which breaks the algorithm.
ex. the last 3 elemts 0,1,0
lets permute them, and we can see that duplicate permutations are produced even if we skip duplicate adjancent numbers:
0,1,0
0,0,1
1,0,0
0,1,0
see? 0,1,0 is produced again.
I got stuck why your solution doesn't work for quite a while and came up with this explaination, hope this helps!
Thanks for the explanation, i was able to write the code by my own
Cant we do something similar to the permutations I solution but instead before adding it to the resPerms, in the solution below, we check if that list is already in the result? if pcopy not in resPerms: resPerms.append(pcopy). I know you cant use a set because lists are mutable so would checking the existence of the list in the resPerms list be invalid? LC seems to accept the answer.
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def helper(i):
if i == len(nums):
return [[]]
resPerms = []
perms = helper(i + 1)
for p in perms:
for j in range(len(p) + 1):
pcopy = p.copy()
pcopy.insert(j, nums[i])
if pcopy not in resPerms:
resPerms.append(pcopy)
return resPerms
return helper(0)
C#, a bit more straightforward, imo:
public class Solution {
public IList PermuteUnique(int[] nums) {
List global = new();
FindPermutations(nums, 0, global);
return global;
}
private void FindPermutations(int[] nums, int start, List global)
{
if (start > nums.Length - 1)
{
global.Add(new List(nums));
return;
}
HashSet used = new();
for (int i = start; i < nums.Length; i++)
{
if (used.Contains(nums[i])) continue;
(nums[start], nums[i]) = (nums[i], nums[start]);
FindPermutations(nums, start + 1, global);
(nums[start], nums[i]) = (nums[i], nums[start]);
used.Add(nums[i]);
}
}
}
also we can just remember which nums we handled. Set is good for this task. Runtime will be still n * n! and memory O(n)
explained very well !
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
res = set()
n = len(nums)
def back_track(i):
if i==n:
res.add(tuple(nums[:]))
for j in range(i, n):
nums[i], nums[j] = nums[j], nums[i]
back_track(i+1)
nums[i], nums[j] = nums[j], nums[i]
back_track(0)
return res
Nice solution. If we run "for n in nums" in stead of "for n in count" then we have normal permutation.
I believe we take the 'for n in count' because we want the unique values. The keys in the count are unique, whereas the the elements in nums arent.
Very good explanation of this problem. Thank you ❤️
I really need to get better at DFS
Brilliant explanation thank you so much❤
Thanks for the easy approach bhaiya
res=[]
perm=[]
nums.sort()
def dfs(loop):
if not loop:
res.append(perm.copy())
return
for i in range(len(loop)):
if i > 0 and loop[i] == loop[i-1]:
continue
perm.append(loop[i])
dfs(loop[:i] + loop[i+1:])
perm.pop()
dfs(nums)
return res
can't we use set to store combinations in backtracking approach?
Java sol
class Solution {
public List < List < Integer >> permuteUnique(int[] nums) {
List < List < Integer >> results = new ArrayList < > ();
Map < Integer, Integer > map = new HashMap < > ();
for (int n: nums)
map.put(n, map.getOrDefault(n, 0) + 1);
helper(map, new Integer[nums.length], 0, results);
return results;
}
private void helper(Map < Integer, Integer > map, Integer[] p, int i, List < List < Integer >> result) {
if (i == p.length)
result.add(Arrays.asList(Arrays.copyOf(p, p.length)));
for (int key: map.keySet()) {
if (map.get(key) > 0) {
map.put(key, map.get(key) - 1);
p[i] = key;
helper(map, p, i + 1, result);
map.put(key, map.get(key) + 1);
}
}
}
}
Wrong sol
@@molikaagarwal1135 lol it worked when I posted it which test case fails?
excellent solution!!!
Man wish I could make a copy of you to mentor me a little bit.
You may have skipped "Why use a hashmap" AND i think can 'mention' an alternative, if it's possible without that
Thanks for the explanation... Awesome
this solution is smart
why are we only appending a copy of perm to result?
best ever
Without set/hash simple backtrack
class Solution {
private:
vector ans;
void f(vector nums,int i,int n)
{
if(i==n)
{
ans.push_back(nums);
return ;
}
for(int j=i;j
Can someone explain to me why we did perm.pop(). And am I correct in assuming that we we count[n] += 1 after calling dfs() to restore the count for the next half of the decision tree? Please help me out 😅
think of it this way,you have appended the value and decremented its entry in the dictionary/hashmap.When you return back to this point after the function call is executed you would want to pop out the added value and increment the entry in the hashmap before going for the next entry in the loop ,otherwise you may miss some numbers in the permutation because for the next iteration of the loop the dictionary would have changed!..basically your logic is correct ! if you want more insight try dry running with this example nums=[1,2,2]
Lucid! Thanks.
thanks
can someone please tell me why did we have to create a new copy of perm before appending it to the result??
When you use res.append(perm) you're appending a reference to perm, so any changes you make to perm will also change all of the permutations in result. You create and append a copy of perm to avoid this.
@@_gkc thank you ;
IMHO, the complexity is O(N!), when all elements are unique (number of permutations of ordering n numbers in a row is n!).
If you were interviewing with this question, explaining and solving it so elegantly but messing up the complexity, it would likely change your rating from "Hire" to "Leaning hire". It is more important than getting everything right in your code.
Why is this complexity?
What's the worst case scenario?
2^m where m is the unique elements in nums in worst case it will be 2^n where all the elements are unique in nums
It's O(n!) in the worst-case, when all elements are unique.
What if instead of the hashmap you used index of the array and just performed permutation as before but while appending in index array appeneded the value at the index?
If duplicate, is present in ans array we don't append that or something
@@programming1734 yeah i thought of that like set map function we will simply remove duplicates in result array.
thank you
me using the solution from permutations 1: return list([list(y) for y in (set([tuple(x) for x in perm1solution])])
lmao
can you please code in c++/java as python is dumb
Very clear description and explanation. Thank you