Convert an array to reduced form

Difficulty Level Medium
Frequently asked in LinkedIn Snapchat Xome Yahoo
Array Hash SortingViews 2694

Problem Statement

Problem “Convert an array to reduced form” states that you are given an array of integers of size n distinct elements. The problem statement asked to reduce the array in such a way that the new numbers be placed in the array within the range 0 to n-1. The smallest number of the array should be considered as 0, greater than that is 1. And continuously n-1 number is the largest element of the array.

Example

arr[]={20,10,35,42,8}
2 1 3 4 0

Explanation: We have to place the array number in the reduced form within 0 to the n-1 range. We can look 8 is the smallest, so it is 0. 10 is next so it is 1, 20 is 2 and so on.

 

Algorithm to convert an array to reduced form

1. Declare a temporary array of size the same as the original array.
2. Copy all the values of the given array into the declared array.
3. Sort that array in which we have copied the value of the original array.
4. Declare a map and set an integer variable ‘val’ to 0.
5. Traverse the array and store the value of the temp array’ element as a key into the map and a val value and increasing the count of ‘val’ by 1 every time.
6. Traverse the original array from 0 to n-1.
  1. Place the value of the map’s key into the array.
7. Print the original array in which we replace the value of the map.

Explanation

We have given an array of integers, we have to reduce the array in such a way that each number in the original array would take a value from range 0 to n-1 without missing any value from the range. It means if we have given 5 numbers in the array then we will place the number from 0 to 4 inclusively at each position of an element of the original array.

For that, we will be using the one extra array of size n, what we are going to do is we will copy the original array from the original array. Because we are going to perform the operation on it. We will sort the copied array in non-decreasing order. Because we have to make each element reduced to a number which is suitable from the given range. We will declare a map and a variable called ‘val’ to 0.

The map is going to store the values of the temporary array which we created as a key and also now temporary array is sorted so we can place the number from o to n-1.  We will traverse the array and place the elements as key and val to the value of the key. The value of val we will be increasing by 1 every time we traverse with a new value, so it automatically ranges from 0 to n-1.

Traverse the original array and insert all the values of the map to the original array or we can say we will replace the original array with these new values. Print those elements of the original array as we have already reduced it into the form of range 0 to n-1.

Convert an array to reduced form

Code

C++ code to convert an array to reduced form

#include<iostream>
#include<unordered_map>
#include<algorithm>

using namespace std;

void convert(int arr[], int n)
{
    int temp[n];
    memcpy(temp, arr, n*sizeof(int));

    sort(temp, temp + n);

    unordered_map<int, int> umap;

    int val = 0;
    for (int i = 0; i < n; i++)
        umap[temp[i]] = val++;

    for (int i = 0; i < n; i++)
        arr[i] = umap[arr[i]];
}
void printArr(int arr[], int n)
{
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {20,10,35,42,8};
    int n = sizeof(arr)/sizeof(arr[0]);

    convert(arr, n);
    cout << "Converted Array is : \n";
    printArr(arr, n);
    return 0;
}

Converted Array is :
2 1 3 4 0

 

Java code to convert an array to reduced form

import java.util.HashMap;
import java.util.Arrays;

class ReducedArray
{
    public static void convert(int arr[], int n)
    {
        int temp[] = arr.clone();

        Arrays.sort(temp);

        HashMap<Integer, Integer> umap = new HashMap<>();

        int val = 0;
        for (int i = 0; i < n; i++)
            umap.put(temp[i], val++);


        System.out.println("Converted Array is : ");
        for (int i = 0; i < n; i++)
        {
            arr[i] = umap.get(arr[i]);
            System.out.print(arr[i] + " ");
        }
    }
    public static void main(String[] args)
    {

        int arr[] = {20,10,35,42,8};
        int n = arr.length;
        convert(arr, n);

    }
}

Converted Array is :
2 1 3 4 0

 

Complexity Analysis

Time Complexity

We sorted our input array. That’s why O(n Log n) where “n” is the size of the array.

Space Complexity

Because we stored an input array, we achieved O(n) where “n” is the size of the array.

Translate »