1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation
2.3.
Time Complexity
2.4.
Space Complexity
3.
3.1.
What is a hashtable?
3.2.
How do we store data in a hashmap?
3.3.
What is reduced form?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Convert an array to reduced form(using hashtable)

Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## 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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

### What is a hashtable?

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.

### How do we store data in a hashmap?

In hashmap data is stored in the form of the key value pair. Means every key will have some  value or data mapped to it.

### What is reduced form?

The reduced form is replacing the elements in an array with 0 to n-1 according to the order of the elements means the smallest element will be 0, and the largest element will be n-1.

You can also read about the topic -  hash function in data structure

## Conclusion

In this article, we learned about how we can convert an array into a reduced form with the help of a hash table, and we can learn that in three different programming languages with the time complexity of O(n).

Arrays

hashmap

Problems on hashmap

Recommended problems -

About DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Please upvote our blog to help other ninjas grow.

Happy Learning

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems