Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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)

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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.

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

Frequently Asked Questions

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

To learn more about array and hash map related concepts, please look into these articles:

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

Previous article
Find All Pairs (a, b) In An Array Such That a % b = k
Next article
Longest Subarray not having more than K Distinct Elements
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass