Convert an array to reduced form | Set 2 (Using vector of pairs)

Given an array with n distinct elements, convert the given array to a form where all elements are in range from 0 to n-1. The order of elements is same, i.e., 0 is placed in place of smallest element, 1 is placed for second smallest element, … n-1 is placed for largest element.

Input:  arr[] = {10, 40, 20}
Output: arr[] = {0, 2, 1}

Input:  arr[] = {5, 10, 40, 30, 20}
Output: arr[] = {0, 1, 4, 3, 2}

We have discussed simple and hashing based solutions.

In this post, a new solution is discussed. The idea is to create a vector of pairs. Every element of pair contains element and index. We sort vector by array values. After sorting, we copy indexes to original array.





// C++ program to convert an array in reduced
// form
#include <bits/stdc++.h>
using namespace std;
// Converts arr[0..n-1] to reduced form.
void convert(int arr[], int n)
    // A vector of pairs. Every element of
    // pair contains array element and its
    // index
    vector <pair<int, int> > v;
    // Put all elements and their index in
    // the vector
        v.push_back(make_pair(arr[i], i));
    // Sort the vector by array values
    sort(v.begin(), v.end());
    // Put indexes of modified vector in arr[]
        arr[v[i].second] = i;
// Utility function to print an array.
void printArr(int arr[], int n)
        cout << arr[i] << " ";
// Driver program to test above method
int main()
    int arr[] = {10, 20, 15, 12, 11, 50};
    cout << "Given Array is \n";
    printArr(arr, n);
    convert(arr , n);
    cout << "\n\nConverted Array is \n";
    printArr(arr, n);
    return 0;


Output :

Given Array is 
10 20 15 12 11 50 

Converted Array is 
0 4 3 2 1 5 

Time Complexity : O(n Log n)
Auxiliary Space : O(n)



My Personal Notes arrow_drop_up

Improved By : aganjali10

Article Tags :
Practice Tags :

