Convert an Array to reduced form 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++
#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 for ( int i = 0; i < n; i++) 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[] for ( int i = 0; i < n; i++) arr[v[i].second] = i; } // Utility function to print an array. void printArr( int arr[], int n) { for ( int i = 0; i < n; i++) cout << arr[i] << " " ; } // Driver program to test above method int main() { int arr[] = { 10, 20, 15, 12, 11, 50 }; int n = sizeof (arr) / sizeof (arr[0]); cout << "Given Array is \n" ; printArr(arr, n); convert(arr, n); cout << "\n\nConverted Array is \n" ; printArr(arr, n); return 0; } |
Java
// Java equivalent of the code import java.util.*; public class Main { // Converts arr[0..n-1] to reduced form. static void convert( int arr[], int n) { // A vector of pairs. Every element of // pair contains array element and its // index List<Pair> v = new ArrayList<>(); // Put all elements and their index in // the vector for ( int i = 0 ; i < n; i++) v.add( new Pair(arr[i], i)); // Sort the vector by array values Collections.sort(v, new SortByVal()); // Put indexes of modified vector in arr[] for ( int i = 0 ; i < n; i++) arr[v.get(i).getIndex()] = i; } // Utility function to print an array. static void printArr( int arr[], int n) { for ( int i = 0 ; i < n; i++) System.out.print(arr[i] + " " ); } // Driver program to test above method public static void main (String[] args) { int arr[] = { 10 , 20 , 15 , 12 , 11 , 50 }; int n = arr.length; System.out.println( "Given Array is \n" ); printArr(arr, n); convert(arr, n); System.out.println( "\n\nConverted Array is \n" ); printArr(arr, n); } // class to store array elements and its // index. static class Pair { int val; int index; public Pair( int val, int index) { this .val = val; this .index = index; } public int getVal() { return val; } public int getIndex() { return index; } } // Comparator to sort the vector elements // according to their values static class SortByVal implements Comparator<Pair> { public int compare(Pair a, Pair b) { return a.getVal() - b.getVal(); } } } |
Python3
# Converts arr[0..n-1] to reduced form. def convert(arr, n): # A list of tuples. Every element of # tuple contains array element and its # index v = [] # Put all elements and their index in # the list for i in range (n): v.append((arr[i], i)) # Sort the list by array values v.sort() # Put indexes of modified list in arr[] for i in range (n): arr[v[i][ 1 ]] = i # Utility function to print an array. def printArr(arr, n): for i in range (n): print (arr[i], end = " " ) # Driver program to test above method arr = [ 10 , 20 , 15 , 12 , 11 , 50 ] n = len (arr) print ( "Given Array is " ) printArr(arr, n) convert(arr, n) print ( "\n\nConverted Array is " ) printArr(arr, n) # This code is contributed by Prasad Kandekar(prasad264) |
C#
using System; using System.Collections.Generic; public class Program { // Converts arr[0..n-1] to reduced form. static void Convert( int [] arr, int n) { // A list of pairs. Every element of pair contains // array element and its index List<Pair> v = new List<Pair>(); // Put all elements and their index in the list for ( int i = 0; i < n; i++) v.Add( new Pair(arr[i], i)); // Sort the list by array values v.Sort( new SortByVal()); // Put indexes of modified list in arr[] for ( int i = 0; i < n; i++) arr[v[i].GetIndex()] = i; } // Utility function to print an array. static void PrintArr( int [] arr, int n) { for ( int i = 0; i < n; i++) Console.Write(arr[i] + " " ); } // Driver program to test above method public static void Main() { int [] arr = { 10, 20, 15, 12, 11, 50 }; int n = arr.Length; Console.WriteLine( "Given Array is " ); PrintArr(arr, n); Convert(arr, n); Console.WriteLine( "\n\nConverted Array is" ); PrintArr(arr, n); } // class to store array elements and its index. class Pair { int val; int index; public Pair( int val, int index) { this .val = val; this .index = index; } public int GetVal() { return val; } public int GetIndex() { return index; } } // Comparator to sort the list elements // according to their values class SortByVal : IComparer<Pair> { public int Compare(Pair a, Pair b) { return a.GetVal() - b.GetVal(); } } } |
Javascript
// Converts arr[0..n-1] to reduced form. function convert(arr, n) { // An array of pairs. Every element of // pair contains array element and its // index let v = []; // Put all elements and their index in // the array for (let i = 0; i < n; i++) v.push([arr[i], i]); // Sort the array by array values v.sort((a, b) => a[0] - b[0]); // Put indexes of modified array in arr[] for (let i = 0; i < n; i++) arr[v[i][1]] = i; } // Utility function to print an array. function printArr(arr, n) { for (let i = 0; i < n; i++) console.log(arr[i] + " " ); } // Driver program to test above method let arr = [10, 20, 15, 12, 11, 50]; let n = arr.length; console.log( "Given Array is " ); printArr(arr, n); convert(arr, n); console.log( "\n\nConverted Array is " ); printArr(arr, n); // This code is contributed by prasad264 |
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)
Another Approach:
1) Create a copy of the input array and sort it in non-decreasing order.
2) Create a map where each element of the sorted array is mapped to its corresponding index in the range 0 to n-1.
3) Traverse the input array and for each element, replace it with the value obtained from the map.
C++
#include <bits/stdc++.h> using namespace std; // Converts arr[0..n-1] to reduced form. void convert( int arr[], int n) { // Make a copy of the input array int sorted_arr[n]; copy(arr, arr+n, sorted_arr); // Sort the copy in non-decreasing order sort(sorted_arr, sorted_arr+n); // Map each element of the sorted array to its index in the range 0 to n-1 unordered_map< int , int > mp; for ( int i = 0; i < n; i++) { mp[sorted_arr[i]] = i; } // Replace each element of the input array with its corresponding index for ( int i = 0; i < n; i++) { arr[i] = mp[arr[i]]; } } // Utility function to print an array. void printArr( int arr[], int n) { for ( int i = 0; i < n; i++) cout << arr[i] << " " ; } // Driver program to test above method int main() { int arr[] = { 10, 20, 15, 12, 11, 50 }; int n = sizeof (arr) / sizeof (arr[0]); cout << "Given Array is \n" ; printArr(arr, n); convert(arr, n); cout << "\n\nConverted Array is \n" ; printArr(arr, n); return 0; } |
Java
import java.util.*; public class Main { // Converts arr[0..n-1] to reduced form. public static void convert( int arr[], int n) { // Make a copy of the input array int [] sorted_arr = Arrays.copyOf(arr, n); // Sort the copy in non-decreasing order Arrays.sort(sorted_arr); // Map each element of the sorted array to its index // in the range 0 to n-1 HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); for ( int i = 0 ; i < n; i++) { mp.put(sorted_arr[i], i); } // Replace each element of the input array with its // corresponding index for ( int i = 0 ; i < n; i++) { arr[i] = mp.get(arr[i]); } } // Utility function to print an array. public static void printArr( int arr[], int n) { for ( int i = 0 ; i < n; i++) { System.out.print(arr[i] + " " ); } } // Driver program to test above method public static void main(String[] args) { int arr[] = { 10 , 20 , 15 , 12 , 11 , 50 }; int n = arr.length; System.out.println( "Given Array is " ); printArr(arr, n); convert(arr, n); System.out.println( "\n\nConverted Array is " ); printArr(arr, n); } } // This code is contributed by Prajwal Kandekar |
Python3
def convert(arr, n): # Make a copy of the input array sorted_arr = arr.copy() # Sort the copy in non-decreasing order sorted_arr.sort() # Map each element of the sorted array to its index in the range 0 to n-1 mp = {} for i in range (n): mp[sorted_arr[i]] = i # Replace each element of the input array with its corresponding index for i in range (n): arr[i] = mp[arr[i]] def print_arr(arr, n): for i in range (n): print (arr[i], end = ' ' ) print () # Driver program to test above method if __name__ = = '__main__' : arr = [ 10 , 20 , 15 , 12 , 11 , 50 ] n = len (arr) print ( "Given Array is " ) print_arr(arr, n) convert(arr, n) print ( "\nConverted Array is " ) print_arr(arr, n) # This code is contributed by Prajwal Kandekar |
C#
using System; using System.Collections.Generic; public class GFG { // Converts arr[0..n-1] to reduced form. static void Convert( int [] arr, int n) { // Make a copy of the input array int [] sortedArr = new int [n]; Array.Copy(arr, sortedArr, n); // Sort the copy in ascending order Array.Sort(sortedArr); // Map each element of the sorted array to its index // in the range 0 to n-1 Dictionary< int , int > mp = new Dictionary< int , int >(); for ( int i = 0; i < n; i++) { mp.Add(sortedArr[i], i); } // Replace each element of the input array with its // corresponding index for ( int i = 0; i < n; i++) { arr[i] = mp[arr[i]]; } } // Utility function to print an array. static void PrintArr( int [] arr, int n) { for ( int i = 0; i < n; i++) { Console.Write(arr[i] + " " ); } } // Driver program to test above method static public void Main() { int [] arr = { 10, 20, 15, 12, 11, 50 }; int n = arr.Length; Console.WriteLine( "Given Array is " ); PrintArr(arr, n); Convert(arr, n); Console.WriteLine( "\n\nConverted Array is " ); PrintArr(arr, n); } } //This code is contributed by Rohit Singh |
Javascript
function convert(arr, n) { // Make a copy of the input array let sorted_arr = [...arr]; // Sort the copy in non-decreasing order sorted_arr.sort((a, b) => a - b); // Map each element of the sorted array to its index in the range 0 to n-1 let mp = {}; for (let i = 0; i < n; i++) { mp[sorted_arr[i]] = i; } // Replace each element of the input array with its corresponding index for (let i = 0; i < n; i++) { arr[i] = mp[arr[i]]; } } function print_arr(arr, n) { for (let i = 0; i < n; i++) { process.stdout.write(`${arr[i]} `); } console.log(); } // Driver program to test above method let arr = [10, 20, 15, 12, 11, 50]; let n = arr.length; process.stdout.write( "Given Array is \n" ); print_arr(arr, n); convert(arr, n); process.stdout.write( "\nConverted Array is \n" ); print_arr(arr, n); |
Given Array is 10 20 15 12 11 50 Converted Array is 0 4 3 2 1 5
Time Complexity: O(n log n) where n is the size of the input array. This is because the function creates a copy of the input array using the “copy” function, which takes O(n) time, sorts the copy using the “sort” function, which has a time complexity of O(n log n)
Space Complexity: O(n) we are using extra space as a map.
Contact Us