Convert an array to reduced form | Set 1 (Simple and Hashing) | GeeksforGeeks

This video is contributed by Aditi Bainss

Please Like, Comment and Share the Video among your friends.

Also, Subscribe if you haven't already! :)

[gauravkvtamboli]

An alternate thing which can be done is, after sorting elements, instead of using Hashing, we can do a binary search of the element in sorted temp array
1. After Sorting the temp array, iterate over the original array
2. pick an element of the original array and search in a sorted array
3. return index from binary search and update the same in the original array

Hashing takes O(n) space and searching becomes O(1) and in Binary search, search time is O(log(n)) and space - O(1)

[gabrielzaragoza]

On one hand your code has std:unordered_map which seems relatively modern. On the other hand you pass a C style array with the length, which seems older and error prone. Is there some reason you mix the two styles? Did you want to pass std::vector<int> ?

[wecan]

void convert(int arr[], int n)
{
int t[n];
for(int i=0;i<n;i++)
{
t[i]=arr[i];
}
sort(t, t+n);
map<int, int>mp;
int val=0;
for(int i=0;i<n;i++)
{
mp[t[i]]=val++;
}
for(int i=0;i<n;i++)
{
arr[i]=mp[arr[i]];
}
}

[youd]

Why do we need a map? Cant we just sort the array and then assign them values from 0 to n-1?