## Introduction

In this article, we are going to learn how we can reduce a given array with the help of a hashtable in three different programming languages.

A Hash table is one of the essential data structures that uses a particular function known as a hash function that maps a given value with a key to retrieve the elements faster.

A hash table is one of the data structures used to store information. The information is composed mostly of keys and values. The effectiveness of the hash function used for mapping determines how efficient the mapping process is.

### Problem Statement

The problem statement is that we have an array of n elements, and we need to convert them into the reduced form with the help of a hashtable. The meaning of reduced form is here that the smallest element in the array will be 0 and the second smallest element will be 1, and so on until n-1 elements. Array in the reduced form will be incrementing with 1.

### Sample Examples

**Input:** [44,5,67,12,32,10]

**Output:**[4,0,5,2,3,1]

**Explanation**

## Approach

We will be using the hashtable approach to convert the Array into the reduced form, and it is quite easy to do. We just need to have a temp[ ] array that will have the elements of the original array, and after that sort, the array in ascending order and then map the values from 0 to n-1 (where n is the size of the array) with the temp[ ] array elements. After mapping the values, the last step will be to replace the original value array with hash table values and display the result.

### Algorithm

- Declare an array of name ar[ ] with n elements
- Create a temp[ ] array of size n
- Create a hashmap for the same datatype of the array
- Copy the elements of array ar [ ] to temp[ ] array
- Sort the temp[ ] array in ascending order
- After sorting, mapping the values from 0 to n-1 with the temp array.
- Replace the ar[ ] element with the hashtable values.
- Print the ar[ ]

### Implementation

**C++**

```
#include<bits/stdc++.h>
using namespace std;
int main()
{
int ar[] = {12,34,5,6,8};
/* calculating the size of the given array */
int size = sizeof(ar)/sizeof(ar[0]);
/* creating temp array to sort and manipulate the array*/
int temp[size],val=0;
/* creating an unordered_map*/
unordered_map<int,int> mapped;
/* copying the elements from ar to temp array*/
for(int i=0;i<size;i++)
{
temp[i] = ar[i];
}
/*sorting the temp array using the sort method*/
sort(temp,temp+size);
/*mapping the values*/
for(int i=0;i<size;i++)
{
mapped[temp[i]] = val++;
}
/* reducing the elements of original array and printing them*/
cout<<"Reduced array:"<<endl;
for(int i=0;i<size;i++)
{
ar[i] = mapped[ar[i]];
cout<<ar[i]<<" ";
}
}
```

**Python**

```
if __name__ == '__main__':
ar =[12,34,5,6,8]
print("Given array: ",ar)
size = len(ar)
val = 0
#copying the elements in tmp array using the copy method
tmp = ar.copy()
#sorting the tmp array
tmp.sort()
#creating the map
mapvalues = {}
#mapping the reduced values
for i in range(size):
mapvalues[tmp[i]] = val
val+=1
#reducing the original array and printing it
for j in range(size):
ar[j] = mapvalues[ar[j]]
print("Reduced array:",ar)
```

**Java**

```
import java.util.*;
class Main
{
public static void reducing(int ar[], int size)
{
/*Create a temp array and copy contents
of ar[] to temp */
int temp[] = ar.clone();
/* Sort temp array */
Arrays.sort(temp);
/* Create a hash table. */
HashMap<Integer, Integer> mapped = new HashMap<>();
/* One by one insert elements of sorted
temp[] and assign them values from 0
to n-1 */
int val = 0;
for (int i = 0; i < size; i++)
mapped.put(temp[i], val++);
/* Convert array by taking positions from
Umap */
for (int i = 0; i < size; i++)
ar[i] = mapped.get(ar[i]);
}
public static void printArr(int ar[], int size)
{
for (int i = 0; i < size; i++)
System.out.print(ar[i] + " ");
}
public static void main(String[] args)
{
int ar[] = {12,34,5,6,8};
int size = ar.length;
System.out.println("Given Array :");
printArr(ar, size);
reducing(ar, size);
System.out.println("\nReduced Array:");
printArr(ar, size);
}
}
```

**Input: **[12,34,5,6,8]

**Output:**

### Time Complexity

Every iteration in the above programs is done in n times of the given array. Whether it is to print to or to mapped the values with the elements of array it is looped in n times. So that why the time complexity is:

**O(n)** here n is the size of the given array

### Space Complexity

**O(n) **here n is the size of the given array and auxiliary space used by temp array to store the array is also n.so total space complexity is n.

You can also read about the __Longest Consecutive Sequence__.