Generate original array from an array that store the counts of greater elements on right
Given an array of integers greater[] in which every value of array represents how many elements are greater to its right side in an unknown array arr[]. Our task is to generate original array arr[]. It may be assumed that the original array contains elements in range from 1 to n and all elements are unique
Examples:
Input: greater[] = { 6, 3, 2, 1, 0, 0, 0 }
Output: arr[] = [ 1, 4, 5, 6, 7, 3, 2 ]Input: greater[] = { 0, 0, 0, 0, 0 }
Output: arr[] = [ 5, 4, 3, 2, 1 ]
We consider an array of elements temp[] = {1, 2, 3, 4, .. n}. We know value of greater[0] indicates count of elements greater than arr[0]. We can observe that (n – greater[0])-th element of temp[] can be put at arr[0]. So we put this at arr[0] and remove this from temp[]. We repeat above process for remaining elements. For every element greater[i], we put (n – greater[i] – i)-th element of temp[] in arr[i] and remove it from temp[].
Below is the implementation of the above idea
C++
// C++ program to generate original array// from an array that stores counts of// greater elements on right.#include <bits/stdc++.h>using namespace std;void originalArray(int greater[], int n){ // Array that is used to include every // element only once vector<int> temp; for (int i = 0; i <= n; i++) temp.push_back(i); // Traverse the array element int arr[n]; for (int i = 0; i < n; i++) { // find the K-th (n-greater[i]-i) // smallest element in Include_Array int k = n - greater[i] - i; arr[i] = temp[k]; // remove current k-th element // from Include array temp.erase(temp.begin() + k); } // print resultant array for (int i = 0; i < n; i++) cout << arr[i] << " ";}// driver program to test above functionint main(){ int Arr[] = { 6, 3, 2, 1, 0, 1, 0 }; int n = sizeof(Arr) / sizeof(Arr[0]); originalArray(Arr, n); return 0;} |
Java
// Java program to generate original array// from an array that stores counts of// greater elements on right.import java.util.Vector;class GFG { static void originalArray(int greater[], int n) { // Array that is used to include every // element only once Vector<Integer> temp = new Vector<Integer>(); for (int i = 0; i <= n; i++) temp.add(i); // Traverse the array element int arr[] = new int[n]; for (int i = 0; i < n; i++) { // find the K-th (n-greater[i]-i) // smallest element in Include_Array int k = n - greater[i] - i; arr[i] = temp.get(k); // remove current k-th element // from Include array temp.remove(k); } // print resultant array for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); } // Driver code public static void main(String[] args) { int Arr[] = { 6, 3, 2, 1, 0, 1, 0 }; int n = Arr.length; originalArray(Arr, n); }}// This code is contributed by Rajput-Ji |
Python3
# Python3 program original array from an# array that stores counts of greater# elements on rightdef originalArray(greater, n): # array that is used to include # every element only once temp = [] for i in range(n + 1): temp.append(i) # traverse the array element arr = [0 for i in range(n)] for i in range(n): # find the Kth (n-greater[i]-i) # smallest element in Include_array k = n - greater[i] - i arr[i] = temp[k] # remove current kth element # from include array del temp[k] for i in range(n): print(arr[i], end=" ")# Driver codearr = [6, 3, 2, 1, 0, 1, 0]n = len(arr)originalArray(arr, n)# This code is contributed# by Mohit Kumar |
C#
// C# program to generate original array// from an array that stores counts of// greater elements on right.using System;using System.Collections.Generic;class GFG { static void originalArray(int[] greater, int n) { // Array that is used to include every // element only once List<int> temp = new List<int>(); for (int i = 0; i <= n; i++) temp.Add(i); // Traverse the array element int[] arr = new int[n]; for (int i = 0; i < n; i++) { // find the K-th (n-greater[i]-i) // smallest element in Include_Array int k = n - greater[i] - i; arr[i] = temp[k]; // remove current k-th element // from Include array temp.RemoveAt(k); } // print resultant array for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); } // Driver code public static void Main() { int[] Arr = { 6, 3, 2, 1, 0, 1, 0 }; int n = Arr.Length; originalArray(Arr, n); }}/* This code contributed by PrinciRaj1992 */ |
Javascript
<script>// JavaScript program to generate original array // from an array that stores counts of // greater elements on right. function originalArray(greater,n) { // Array that is used to include every // element only once let temp = []; for (let i = 0; i <= n; i++) temp.push(i); // Traverse the array element let arr = new Array(n); for (let i = 0; i < n; i++) { // find the K-th (n-greater[i]-i) // smallest element in Include_Array let k = n - greater[i] - i; arr[i] = temp[k]; // remove current k-th element // from Include array temp.splice(k,1); } // print resultant array for (let i = 0; i < n; i++) document.write(arr[i] + " "); } // Driver code let Arr=[6, 3, 2, 1, 0, 1, 0 ]; let n = Arr.length; originalArray(Arr, n); // This code is contributed by patel2127</script> |
Output
1 4 5 6 7 2 3
Time Complexity: (n2) (Erase operation takes O(n) in vector).
Auxiliary Space: O(n), extra space is required for temp and res arrays.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
