This is the second solution int minIncrementForUnique(vector& nums) { mapm; for(auto it:nums) m[it]++; int n=nums.size(),count=0; while(m.size()1) { int key=it.first; int temp=key; m[key]--; temp++; m[temp]++; count++; break; } } } return count;
In second solution : range(min(nums),max(nums)+len(nums)) instead of range(0,max(nums)+len(nums)).....min and max can be calculated simultaneously in single pass first
You can just iterate to the max(nums) Let carry = count[max(nums)] if carry > 1, then add carry*(carry -1)/2 to the result Here is my C++ solution class Solution { public: int minIncrementForUnique(vector& nums) { vector counter(1e5 + 1); for (const auto& x : nums) { ++counter[x]; } int carry = 0; int res = 0; for (int x = 0; x < counter.size(); ++x) { counter[x] += carry; carry = max(counter[x] - 1, 0); res += carry; } res += max(carry - 1, 0) * carry / 2; return res; } };
Initially, I thought of using Next Greater to Left & Next Greater to Right concepts, & did dry run as per below written code for the test cases, [1,2,2], [3,2,1,2,1,7] & [4,4,4,4,4]. According to the dry run, I got the correct answers, but when I run the test cases on leetcode, I get correct output for [1,2,2], but for [3,2,1,2,1,7] & [4,4,4,4,4], it shows output of 4, which is wrong. My dry run (as per the same code) yielded correct answer, but on running on platform, it fails. Can anyone help me address this issue ? The code is : class Solution { private: vector NGR(vector& arr, int n){ stack st; vector result(n, -1); for (int i = n - 1; i >= 0; i--) { while (!st.empty() && st.top()
To get an O(n) solution, you can also do count sort instead of python's built in sort method in your first solution. Imo, this is easier to understand than your second solution even if it may take more lines of code. this is my python solution. class Solution: def minIncrementForUnique(self, nums: List[int]) -> int: large = max(nums) small = min(nums) counts = Counter(nums) nums = [] for i in range(small, large +1): for j in range(counts[i]): nums.append(i) ans = 0 minimum = nums[0] for i in range(len(nums)): if nums[i] < minimum: ans += minimum - nums[i] minimum += 1 else: minimum = nums[i] + 1 return ans
It's not that hard. I had first tried to use a similar approach but had gotten stuck on where to go next from defining dicts, etc. Probably because I was doing it all in my head, should keep a pen and paper next time.
For a sorted array, by default any element to the left would be less than an element to the right. If an element to the left is greater, that means it's original value was already in the array so it had to be incremented to the point where it is either equal or greater than the element to the right.
class Solution { public int minIncrementForUnique(int[] nums) { Arrays.sort(nums); int res=0; int length=nums.length; int i=0; int j=1; while(j < length) { if(nums[i] >= nums[j]) { int before=nums[j]; nums[j]=nums[i]+1; res=res+nums[j]-before;
} ++i; ++j; } return res; } } 1st solution with different approach
It takes a lot of skill to not only conjur the idea but to bring it into code. I thought of the second solution as in how to fill in the gap but was stuck on how to iterate from key to key in a map.
I came up with the second solution when my naive solution timed out. I managed to finally pass the time constraint, but looking at the code in the video i see that i solved a buch of problems with my code very inefficiently: Neetcode: 8 lines of code Me: me 28 lines of code -.- Same basic algorithm
Why do we have to iterate n+max times? Can't we just iterate until the max number? Knowing that there's no more elements bigger than this one we can just calculate the triangle number of the remaining duplicates on one operation. Something like this: class Solution: def minIncrementForUnique(self, nums: List[int]) -> int: count = Counter(nums) res = 0 for i in range(max(nums)): if count[i] > 1: extra = count[i] - 1 count[i + 1] += extra res += extra n = count[max(nums)]-1 res+= n * (n +1)/2 return res
Neet can you post a video solution on "Leetcode 987. Vertical Order Traversal of a Binary Tree" question
This is the second solution
int minIncrementForUnique(vector& nums) {
mapm;
for(auto it:nums)
m[it]++;
int n=nums.size(),count=0;
while(m.size()1)
{
int key=it.first;
int temp=key;
m[key]--;
temp++;
m[temp]++;
count++;
break;
}
}
}
return count;
}
For the max value we can just add (n*(n-1) /2 in the result where n is the count of the max value
In second solution : range(min(nums),max(nums)+len(nums)) instead of range(0,max(nums)+len(nums)).....min and max can be calculated simultaneously in single pass first
You can just iterate to the max(nums)
Let carry = count[max(nums)]
if carry > 1, then add carry*(carry -1)/2 to the result
Here is my C++ solution
class Solution {
public:
int minIncrementForUnique(vector& nums) {
vector counter(1e5 + 1);
for (const auto& x : nums) {
++counter[x];
}
int carry = 0;
int res = 0;
for (int x = 0; x < counter.size(); ++x) {
counter[x] += carry;
carry = max(counter[x] - 1, 0);
res += carry;
}
res += max(carry - 1, 0) * carry / 2;
return res;
}
};
Initially, I thought of using Next Greater to Left & Next Greater to Right concepts, & did dry run as per below written code for the test cases, [1,2,2], [3,2,1,2,1,7] & [4,4,4,4,4]. According to the dry run, I got the correct answers, but when I run the test cases on leetcode, I get correct output for [1,2,2], but for [3,2,1,2,1,7] & [4,4,4,4,4], it shows output of 4, which is wrong. My dry run (as per the same code) yielded correct answer, but on running on platform, it fails. Can anyone help me address this issue ? The code is :
class Solution {
private:
vector NGR(vector& arr, int n){
stack st;
vector result(n, -1);
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && st.top()
To get an O(n) solution, you can also do count sort instead of python's built in sort method in your first solution. Imo, this is easier to understand than your second solution even if it may take more lines of code.
this is my python solution.
class Solution:
def minIncrementForUnique(self, nums: List[int]) -> int:
large = max(nums)
small = min(nums)
counts = Counter(nums)
nums = []
for i in range(small, large +1):
for j in range(counts[i]):
nums.append(i)
ans = 0
minimum = nums[0]
for i in range(len(nums)):
if nums[i] < minimum:
ans += minimum - nums[i]
minimum += 1
else:
minimum = nums[i] + 1
return ans
using a counter makes the complexity O(n log n) though
@@turskaah what, neetcode also uses a counter in his O(n) solution.
I take NlogN solution. 2nd solution is what discourage beginners because it is really hard to come up with 2nd solution.
it really isnt especially because of the context of the previous problems that were all solvable using counting sort
It's not that hard. I had first tried to use a similar approach but had gotten stuck on where to go next from defining dicts, etc. Probably because I was doing it all in my head, should keep a pen and paper next time.
if we take the first solution, but use radix sort, will the solution improve to O(n + d), where n - length array, d - max number
Only catch of this problem is how you prove if value at i is less than value i - 1 means there was a duplicate.
For a sorted array, by default any element to the left would be less than an element to the right. If an element to the left is greater, that means it's original value was already in the array so it had to be incremented to the point where it is either equal or greater than the element to the right.
That is a brilliant solution..
Isn't just iterating !empty() over a hash map while you remove any with counts of 1 better? Then its O(n) and not O(N+max)
BEST EVER!!!!!!!!!!!!!!!!
why hash set is failed here?
class Solution {
public int minIncrementForUnique(int[] nums) {
Arrays.sort(nums);
int res=0;
int length=nums.length;
int i=0;
int j=1;
while(j < length)
{
if(nums[i] >= nums[j])
{
int before=nums[j];
nums[j]=nums[i]+1;
res=res+nums[j]-before;
}
++i;
++j;
}
return res;
}
}
1st solution with different approach
It takes a lot of skill to not only conjur the idea but to bring it into code. I thought of the second solution as in how to fill in the gap but was stuck on how to iterate from key to key in a map.
I came up with the second solution when my naive solution timed out. I managed to finally pass the time constraint, but looking at the code in the video i see that i solved a buch of problems with my code very inefficiently:
Neetcode: 8 lines of code
Me: me 28 lines of code -.-
Same basic algorithm
Why do we have to iterate n+max times? Can't we just iterate until the max number? Knowing that there's no more elements bigger than this one we can just calculate the triangle number of the remaining duplicates on one operation.
Something like this:
class Solution:
def minIncrementForUnique(self, nums: List[int]) -> int:
count = Counter(nums)
res = 0
for i in range(max(nums)):
if count[i] > 1:
extra = count[i] - 1
count[i + 1] += extra
res += extra
n = count[max(nums)]-1
res+= n * (n +1)/2
return res
I came with the optimal solution easily, but I still must watch your videos
how do u know all of this
So clear thx bro
Interesting, The clever way is less efficient.
Can someone explain to me the time complexity for the first solution ?
My guess is it takes N*logN from sorting and N when we iterate the array
That's correct.
Yes
You're right.
nlogn is the most significant so you can ignore the other n from iteration and just say the time complexity is nlogn
In the second solution, I added this line inside the for loop, which makes it a bit faster:
if i>max(nums) and count[i]==0:
break
thanks
First!!🎉
did both by myself 🤧🤧
9:54 exrta 🤣🤣🤣🤣
we got autistic neetcode before gta vi
@@anandsharma16 lmao
Finally I am first comment!❤🎉🎉