Generate original array from an array that store the counts of greater elements on right

0 0 4 minutes read

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 function
int 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 right
 
 
def 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 code
arr = [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: (n²) (Erase operation takes O(n) in vector).
Auxiliary Space: O(n), extra space is required for temp and res arrays.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!