Minimum Increment to Make Array Unique - Leetcode 945 - Python 

That is a brilliant solution..

I take NlogN solution. 2nd solution is what discourage beginners because it is really hard to come up with 2nd solution.

Neet can you post a video solution on "Leetcode 987. Vertical Order Traversal of a Binary Tree" question

BEST EVER!!!!!!!!!!!!!!!!

So clear thx bro

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

Only catch of this problem is how you prove if value at i is less than value i - 1 means there was a duplicate.

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()

For the max value we can just add (n*(n-1) /2 in the result where n is the count of the max value

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

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)

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

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

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.

why hash set is failed here?

First!!🎉

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

how do u know all of this

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

did both by myself 🤧🤧

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

Finally I am first comment!❤🎉🎉

9:54 exrta 🤣🤣🤣🤣