LeetCode: Permutations II (DFS with local and global hash table)
https://leetcode.com/problems/permutations-ii/, problem description:
The approach will be a regular DFS but with a specific change: use a local hash table to keep track locally (not globally) of the elements already added to the current index in order to avoid duplicated elements at that index. That's the purpose of the htUsedNumbersInThisPosition hash table. Not the fastest by any means, but passable. Code is down below, cheers, Marcelo.
public class Solution
{
public IList<IList<int>> PermuteUnique(int[] nums)
{
List<IList<int>> solution = new List<IList<int>>();
PermuteUniqueInternal(0,
new List<int>(),
nums,
new Hashtable(),
solution);
return solution;
}
private void PermuteUniqueInternal(int index,
List<int> current,
int[] nums,
Hashtable htIndexUsed,
List<IList<int>> solution)
{
/*
* Base case:
* 1) make sure to create a deep copy first (the current list is passed by reference)
* */
if (index >= nums.Length)
{
List<int> copy = new List<int>(current);
solution.Add(copy);
return;
}
/*
* Induction:
* 1) make sure you don't repeat the same number at this "index" position. For that use a local hash table
* 2) make sure you don't repeat an index already used. For that use a global hash table
* 3) make sure to delete the element at the "index" position, instead of deleting a value (nuances of the C# language)
* */
Hashtable htUsedNumbersInThisPosition = new Hashtable();
for (int i = 0; i < nums.Length; i++)
{
if (!htIndexUsed.ContainsKey(i) && !htUsedNumbersInThisPosition.ContainsKey(nums[i]))
{
htIndexUsed.Add(i, true);
htUsedNumbersInThisPosition.Add(nums[i], true);
current.Add(nums[i]);
PermuteUniqueInternal(index + 1,
current,
nums,
htIndexUsed,
solution);
current.RemoveAt(index);
htIndexUsed.Remove(i);
}
}
}
}
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:[ [1,1,2], [1,2,1], [2,1,1] ]
The approach will be a regular DFS but with a specific change: use a local hash table to keep track locally (not globally) of the elements already added to the current index in order to avoid duplicated elements at that index. That's the purpose of the htUsedNumbersInThisPosition hash table. Not the fastest by any means, but passable. Code is down below, cheers, Marcelo.
{
public IList<IList<int>> PermuteUnique(int[] nums)
{
List<IList<int>> solution = new List<IList<int>>();
PermuteUniqueInternal(0,
new List<int>(),
nums,
new Hashtable(),
solution);
return solution;
}
private void PermuteUniqueInternal(int index,
List<int> current,
int[] nums,
Hashtable htIndexUsed,
List<IList<int>> solution)
{
/*
* Base case:
* 1) make sure to create a deep copy first (the current list is passed by reference)
* */
if (index >= nums.Length)
{
List<int> copy = new List<int>(current);
solution.Add(copy);
return;
}
/*
* Induction:
* 1) make sure you don't repeat the same number at this "index" position. For that use a local hash table
* 2) make sure you don't repeat an index already used. For that use a global hash table
* 3) make sure to delete the element at the "index" position, instead of deleting a value (nuances of the C# language)
* */
Hashtable htUsedNumbersInThisPosition = new Hashtable();
for (int i = 0; i < nums.Length; i++)
{
if (!htIndexUsed.ContainsKey(i) && !htUsedNumbersInThisPosition.ContainsKey(nums[i]))
{
htIndexUsed.Add(i, true);
htUsedNumbersInThisPosition.Add(nums[i], true);
current.Add(nums[i]);
PermuteUniqueInternal(index + 1,
current,
nums,
htIndexUsed,
solution);
current.RemoveAt(index);
htIndexUsed.Remove(i);
}
}
}
}
very nice Marcelo! I decided to approach this from a different angle though and reduce this problem to another one - finding another lexicographical permutation. Basically I just start with the lexicographically smallest permutation (sorted array) and continue appending new permutations until there is no longer "next" permutation.
ReplyDeleteCode below takes 23ms and beats 82% of submissions:
class Solution {
private:
bool next(vector &nums) {
int idx = nums.size() - 2;
while (idx >= 0 && nums[idx] >= nums[idx+1]) --idx;
if (idx == -1) return false;
auto min_max = upper_bound(nums.rbegin(), nums.rend() - idx - 1, nums[idx]);
swap(nums[idx], *min_max);
reverse(nums.begin() + idx + 1, nums.end());
return true;
}
public:
vector> permuteUnique(vector& nums) {
sort(nums.begin(), nums.end());
vector> result{nums};
while (next(nums)) result.push_back(nums);
return result;
}
};
Thanks for sharing this gem!