leetcode problem 945
- Level: Medium
- Description: Given an array of integers
A, a move consists of choosing any A[i], and incrementing it by 1.
- Tags: Array
Straight Forward
- sort the original array
- iterate the sorted array while adding the cost of each element in order to satisfy the given requirement.
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
sort(A.begin(), A.end());
int res=0, next=0;
for(auto a: A){
res += max(next-a, 0);
next = max(a, next) + 1;
}
return res;
}
};
|
- Time Complexity:
O(Nlog(N))
- Space Complexity:
O(1)
O(Klog(k)) by using map
Same idea as the first one, only difference is that now we count occurrences of each elements and calculate total cost for the same element.
- Time Complexity:
O(N+Klog(K)) using TreeMap in C+++
- Space Complexity:
O(K)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int minIncrementForUnique(vector<int>& A) {
map<int,int> map;
for(auto e: A) map[e]+=1;
int res=0, next=0;
for(auto it: map){
res += max(next-it.first, 0)*it.second + (it.second-1)*it.second/2;
next = max(next, it.first) + it.second;
}
return res;
}
};
|