Make array elements unique. Geeks For Geeks
Problem Link:
https://practice.geeksforgeeks.org/problems/6e63df6d2ebdf6408a9b364128bb1123b5b13450/1
It is also the problem of the day for 11-01-2023
Solution:
class Solution {
public long minIncrements(int[] arr, int n) {
long count=0;
Arrays.sort(arr);
// for(int a:arr){
// System.out.print(a+" ");
// }
HashMap<Integer,Integer>map=new HashMap<Integer,Integer>();
int index=1;
for(int a:arr){
if(index<a){
index=a;
index++;
map.put(a,1);
//condition1
}
else if(index==a){
index++;
map.put(index,1);
//condition2
}
else{
map.put(index,1);
count+=index-a;
index++;
//condition3
}
// System.out.print(count+" ");
}
// System.out.println(map);
return count;
}
}
Time Complexity:O(nlogn)[GFG Time:0.68]
Space Complexity:O(n)[Array is used]
Auxiliary Space:O(N)[HashMap is used]
Approach Explained:
The question asks for one thing - just to have all elements unique.
By reading the 'unique' word, the first thing that comes into our mind is the usage of the map, and that too is correct.
The thing is map will have unique values only when it will be provided with unique elements, which means that every element in the array should be unique so that all map entries will be unique.
The question is how to make every element in the array unique as there will be duplicates and too many.
So for that one thing, we should know that the question asks for a counter so by this we can get a hint that it does not matter with the order of elements in an array(firstly) and secondly, we want unique elements for which we can sort them and can see what all are a unique element.
So after sorting, we will get the sorted array.
Now we just simply need to insert the elements but with the condition, they should not be present earlier in the map.
So for that, we take a variable named 'index' which will store the value of the last input element.
Why this variable 'index'?
By this variable, we will get to know about the status of the map that what element was last inserted which also means that all elements comping should have more value than this index element. If we do not take this then we might not be able to get the information on the uniqueness of the map in O(1) time (variable is constant). It will act as a flag to inform us about the status of the map.
For example:
an array of size 9
array: 4 5 4 1 3 7 6 3 3
Now solution:
1. sort array 1 3 3 3 4 4 5 6 7
make index=1 and count=0 (declaration and definition at the start);
Now for each loop over the array and store into a.
1.a=1 and index=1
going into condition 2 in code
index++ so index=2
map={1}
2. a=3 and index=2
going to condition 1
index=a ie index=3
index++; ie index=4 so it means now we can not insert any value less than 4 in the map
map={1,3}
3. a=3 index=4
condition 3
count=count+index-a; ie count=0+4-3 ie count=1;
map:{1,3,4}
index=5;
4. a=3 index=5;
condition 3
count=1+5-3 ie count=3
map={1,3,4,5}
index=6;
5.a=4 index=6
condition 3
count=3+6-4 ie count=5
map:{1,3,4,5,6}
index=7
6 a=4 index=7
condition 3
count=5+7-4 ie count=8
map:{1,3,4,5,6,7}
index=8
7.a=5 index=8
condition 3
count=8+8-5 ie count=11
map={1,3,4,5,6,7,8}
index=9
8.a=6 index=9
count=11+9-6 ie count=14
map={1,3,4,5,6,7,8,9}
index=10
9.a=7 index=10
count=14+10-7 ie count=17
map:{1,3,4,5,6,7,8,9,10}
index=11;
Now as a result, we can clearly see that
the map consists of 9 unique elements.
so it proves we have done it correctly and return count.
=========================================================================
Without Using HashMap:
The main point to observe in the above code is that the map is used to give us a view of how the array will look if we perform the following operation specified in the question.
However is that we require an answer,
No, we require just the count so we have no need for a map.
And if the question asked for a modified array with unique elements then our map will be the answer.
So for this question, we can further reduce the auxiliary space and some amount of time.
class Solution {
public long minIncrements(int[] arr, int n) {
long count=0;
Arrays.sort(arr);
// for(int a:arr){
// System.out.print(a+" ");
// }
// HashMap<Integer,Integer>map=new HashMap<Integer,Integer>();
int index=1;
for(int a:arr){
if(index<a){
index=a;
index++;
// map.put(a,1);
}
else if(index==a){
index++;
// map.put(index,1);
}
else{
// map.put(index,1);
count+=index-a;
index++;
}
// System.out.print(count+" ");
}
// System.out.println(map);
return count;
}
}
Time Complexity:O(nlogn)[GFG time: 0.44]
Space Complexity:O(n)[Array is used]
Auxiliary Space:O(1)[HashMap is not used]
Questions:
The reason for not using a set in getting unique elements to count is that if we insert all the elements in the set then it will lead to a loss of elements as all the duplicates will be stored as one entry only, however, it may give us the correct count of unique elements.
"Thanks For Reading.😇"
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment