Convert an array to reduced form(using hashtable)

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]<<" ";
    }
}

You can also try this code with Online C++ Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

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); 
  
    } 
}

You can also try this code with Online Java Compiler

Run Code

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.