Count of larger elements on right side of each element in an array

0 0 13 minutes read

Given an array arr[] consisting of N integers, the task is to count the number of greater elements on the right side of each array element.

Examples:

Input: arr[] = {3, 7, 1, 5, 9, 2}
Output: {3, 1, 3, 1, 0, 0}
Explanation: For arr[0], the elements greater than it on the right are {7, 5, 9}. For arr[1], the only element greater than it on the right is {9}. For arr[2], the elements greater than it on the right are {5, 9, 2}. For arr[3], the only element greater than it on the right is {9}. For arr[4] and arr[5], no greater elements exist on the right.

Input: arr[] = {5, 4, 3, 2}
Output: {0, 0, 0, 0}

Naive Approach: The simplest approach is to iterate all array elements using two loops and for each array element, count the number of elements greater than it on its right side and then print it.
Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Approach: The problem can be solved using the concept of Merge Sort in descending order. Follow the steps given below to solve the problem:

Initialize an array count[] where count[i] store the respective count of greater elements on the right for every arr[i]
Take the indexes i and j, and compare the elements in an array.
If higher index element is greater than the lower index element then, all the higher index element will be greater than all the elements after that lower index.
Since the left part is already sorted, add the count of elements after the lower index element to the count[] array for the lower index.
Repeat the above steps until the entire array is sorted.
Finally print the values of count[] array.

Below is the implementation of the above approach:

Java

// Java program for the above approach
 
import java.util.*;
 
public class GFG {
 
    // Stores the index & value pairs
    static class Item {
 
        int val;
        int index;
 
        public Item(int val, int index)
        {
            this.val = val;
            this.index = index;
        }
    }
 
    // Function to count the number of
    // greater elements on the right
    // of every array element
    public static ArrayList<Integer>
    countLarge(int[] a)
    {
        // Length of the array
        int len = a.length;
 
        // Stores the index-value pairs
        Item[] items = new Item[len];
 
        for (int i = 0; i < len; i++) {
            items[i] = new Item(a[i], i);
        }
 
        // Stores the count of greater
        // elements on right
        int[] count = new int[len];
 
        // Perform MergeSort operation
        mergeSort(items, 0, len - 1,
                  count);
 
        ArrayList<Integer> res = new ArrayList<>();
 
        for (int i : count) {
            res.add(i);
        }
 
        return res;
    }
 
    // Function to sort the array
    // using Merge Sort
    public static void mergeSort(
        Item[] items, int low ,int high,
        int[] count)
    {
 
        // Base Case
        if (low >= high) {
            return;
        }
 
        // Find Mid
        int mid = low + (high - low) / 2;
 
        mergeSort(items, low, mid,
                  count);
        mergeSort(items, mid + 1,
                  high, count);
 
        // Merging step
        merge(items, low, mid,
              mid + 1, high, count);
    }
 
    // Utility function to merge sorted
    // subarrays and find the count of
    // greater elements on the right
    public static void merge(
        Item[] items, int low, int lowEnd,
        int high, int highEnd, int[] count)
    {
        int m = highEnd - low + 1; // mid
 
        Item[] sorted = new Item[m];
 
        int rightCounter = 0;
        int lowInd = low, highInd = high;
        int index = 0;
 
        // Loop to store the count of
        // larger elements on right side
        // when both array have elements
        while (lowInd <= lowEnd
               && highInd <= highEnd) {
 
            if (items[lowInd].val
                < items[highInd].val) {
                rightCounter++;
                sorted[index++]
                    = items[highInd++];
            }
            else {
                count[items[lowInd].index] += rightCounter;
                sorted[index++] = items[lowInd++];
            }
        }
 
        // Loop to store the count of
        // larger elements in right side
        // when only left array have
        // some element
        while (lowInd <= lowEnd) {
 
            count[items[lowInd].index] += rightCounter;
            sorted[index++] = items[lowInd++];
        }
 
        // Loop to store the count of
        // larger elements in right side
        // when only right array have
        // some element
        while (highInd <= highEnd) {
 
            sorted[index++] = items[highInd++];
        }
 
        System.arraycopy(sorted, 0, items,
                         low, m);
    }
 
    // Utility function that prints
    // the count of greater elements
    // on the right
    public static void
    printArray(ArrayList<Integer> countList)
    {
 
        for (Integer i : countList)
            System.out.print(i + " ");
 
        System.out.println();
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given array
        int arr[] = { 3, 7, 1, 5, 9, 2 };
        int n = arr.length;
 
        // Function Call
        ArrayList<Integer> countList
            = countLarge(arr);
 
        printArray(countList);
    }
}

Python3

from typing import List
 
class Item:
    def __init__(self, val: int, index: int):
        self.val = val
        self.index = index
 
def count_large(a: List[int]) -> List[int]:
    # Length of the array
    length = len(a)
 
    # Stores the index-value pairs
    items = [Item(a[i], i) for i in range(length)]
 
    # Stores the count of greater elements on right
    count = [0] * length
 
    # Perform MergeSort operation
    merge_sort(items, 0, length - 1, count)
 
    res = count.copy()
 
    return res
 
def merge_sort(items: List[Item], low: int, high: int, count: List[int]) -> None:
    # Base Case
    if low >= high:
        return
 
    # Find Mid
    mid = low + (high - low) // 2
 
    merge_sort(items, low, mid, count)
    merge_sort(items, mid + 1, high, count)
 
    # Merging step
    merge(items, low, mid, mid + 1, high, count)
 
def merge(items: List[Item], low: int, low_end: int, high: int, high_end: int, count: List[int]) -> None:
    m = high_end - low + 1  # mid
 
    sorted_items = [None] * m
 
    right_counter = 0
    low_ind = low
    high_ind = high
    index = 0
 
    # Loop to store the count of larger elements on right side
    # when both array have elements
    while low_ind <= low_end and high_ind <= high_end:
        if items[low_ind].val < items[high_ind].val:
            right_counter += 1
            sorted_items[index] = items[high_ind]
            index += 1
            high_ind += 1
        else:
            count[items[low_ind].index] += right_counter
            sorted_items[index] = items[low_ind]
            index += 1
            low_ind += 1
 
    # Loop to store the count of larger elements in right side
    # when only left array have elements
    while low_ind <= low_end:
        count[items[low_ind].index] += right_counter
        sorted_items[index] = items[low_ind]
        index += 1
        low_ind += 1
 
    # Loop to store the count of larger elements in right side
    # when only right array have elements
    while high_ind <= high_end:
        sorted_items[index] = items[high_ind]
        index += 1
        high_ind += 1
 
    items[low:low + m] = sorted_items
 
def print_array(count_list: List[int]) -> None:
    print(' '.join(str(i) for i in count_list))
 
# Driver Code
if __name__ == '__main__':
    # Given array
    arr = [3, 7, 1, 5, 9, 2]
 
    # Function Call
    count_list = count_large(arr)
 
    print_array(count_list)
 
# This code is contributed by Aditya Sharma

C#

using System;
using System.Collections.Generic;
 
public class GFG {
    // Stores the index & value pairs
    public class Item {
        public int val;
        public int index;
 
        public Item(int val, int index)
        {
            this.val = val;
            this.index = index;
        }
    }
 
    // Function to count the number of
    // greater elements on the right
    // of every array element
    public static List<int> CountLarge(int[] a)
    {
        // Length of the array
        int len = a.Length;
 
        // Stores the index-value pairs
        Item[] items = new Item[len];
 
        for (int i = 0; i < len; i++) {
            items[i] = new Item(a[i], i);
        }
 
        // Stores the count of greater
        // elements on right
        int[] count = new int[len];
 
        // Perform MergeSort operation
        MergeSort(items, 0, len - 1, count);
 
        List<int> res = new List<int>();
 
        foreach(int i in count) { res.Add(i); }
 
        return res;
    }
 
    // Function to sort the array
    // using Merge Sort
    public static void MergeSort(Item[] items, int low,
                                 int high, int[] count)
    {
        // Base Case
        if (low >= high) {
            return;
        }
 
        // Find Mid
        int mid = low + (high - low) / 2;
 
        MergeSort(items, low, mid, count);
        MergeSort(items, mid + 1, high, count);
 
        // Merging step
        Merge(items, low, mid, mid + 1, high, count);
    }
 
    // Utility function to merge sorted
    // subarrays and find the count of
    // greater elements on the right
    public static void Merge(Item[] items, int low,
                             int lowEnd, int high,
                             int highEnd, int[] count)
    {
        int m = highEnd - low + 1; // mid
 
        Item[] sorted = new Item[m];
 
        int rightCounter = 0;
        int lowInd = low, highInd = high;
        int index = 0;
 
        // Loop to store the count of
        // larger elements on right side
        // when both array have elements
        while (lowInd <= lowEnd && highInd <= highEnd) {
            if (items[lowInd].val < items[highInd].val) {
                rightCounter++;
                sorted[index++] = items[highInd++];
            }
            else {
                count[items[lowInd].index] += rightCounter;
                sorted[index++] = items[lowInd++];
            }
        }
 
        // Loop to store the count of
        // larger elements in right side
        // when only left array have
        // some element
        while (lowInd <= lowEnd) {
            count[items[lowInd].index] += rightCounter;
            sorted[index++] = items[lowInd++];
        }
 
        // Loop to store the count of
        // larger elements in right side
        // when only right array have
        // some element
        while (highInd <= highEnd) {
            sorted[index++] = items[highInd++];
        }
 
        Array.Copy(sorted, 0, items, low, m);
    }
 
    // Utility function that prints
    // the count of greater elements
    // on the right
    public static void PrintArray(List<int> countList)
    {
        foreach(int i in countList)
        {
            Console.Write(i + " ");
        }
        Console.WriteLine();
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        // Given array
        int[] arr = { 3, 7, 1, 5, 9, 2 };
        int n = arr.Length;
 
        // Function Call
        List<int> countList = CountLarge(arr);
 
        PrintArray(countList);
    }
}
// This code is contributed by akashish__

Javascript

//Javascript equivalent
 
//Define an object Item
class Item {
  constructor(val, index) {
    this.val = val
    this.index = index
  }
}
 
//Function to count large elements
function countLarge(arr) {
  // Length of the array
  const length = arr.length
 
  // Stores the index-value pairs
  const items = []
  for (let i = 0; i < length; i++) {
    items.push(new Item(arr[i], i))
  }
 
  // Stores the count of greater elements on right
  const count = []
  for (let i = 0; i < length; i++) {
    count.push(0)
  }
 
  // Perform MergeSort operation
  mergeSort(items, 0, length - 1, count)
 
  const res = count.slice(0)
 
  return res
}
 
//Merge Sort function
function mergeSort(items, low, high, count) {
  // Base Case
  if (low >= high) return
 
  // Find Mid
  const mid = low + Math.floor((high - low) / 2)
 
  mergeSort(items, low, mid, count)
  mergeSort(items, mid + 1, high, count)
 
  // Merging step
  merge(items, low, mid, mid + 1, high, count)
}
 
//Merge function
function merge(items, low, lowEnd, high, highEnd, count) {
  const mid = highEnd - low + 1 // mid
 
  const sortedItems = []
  for (let i = 0; i < mid; i++) {
    sortedItems.push(null)
  }
 
  let rightCounter = 0
  let lowInd = low
  let highInd = high
  let index = 0
 
  // Loop to store the count of larger elements on right side
  // when both array have elements
  while (lowInd <= lowEnd && highInd <= highEnd) {
    if (items[lowInd].val < items[highInd].val) {
      rightCounter++
      sortedItems[index] = items[highInd]
      index++
      highInd++
    } else {
      count[items[lowInd].index] += rightCounter
      sortedItems[index] = items[lowInd]
      index++
      lowInd++
    }
  }
 
  // Loop to store the count of larger elements in right side
  // when only left array have elements
  while (lowInd <= lowEnd) {
    count[items[lowInd].index] += rightCounter
    sortedItems[index] = items[lowInd]
    index++
    lowInd++
  }
 
  // Loop to store the count of larger elements in right side
  // when only right array have elements
  while (highInd <= highEnd) {
    sortedItems[index] = items[highInd]
    index++
    highInd++
  }
 
  for (let i = 0; i < mid; i++) {
    items[low + i] = sortedItems[i]
  }
}
 
//Function to print array
function printArray(countList) {
  let str = ''
  for (let i = 0; i < countList.length; i++) {
    str += countList[i] + ' '
  }
  console.log(str)
}
 
// Driver Code
  // Given array
  const arr = [3, 7, 1, 5, 9, 2]
 
  // Function Call
  const countList = countLarge(arr)
 
  printArray(countList)

Output

3 1 3 1 0 0

Time Complexity: O(N*log N)
Auxiliary Space: O(N)

Another approach: We can use binary search to solve this. The idea is to create a sorted list of input and then for each element of input we first remove that element from the sorted list and then apply the modified binary search to find the element just greater than the current element and then the number of large elements will be the difference between the found index & the length of sorted list.

C++

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
// Helper function to count the number of elements greater than 'item' in the sorted 'list'
int CountLargeNumbers(int item, vector<int>& list) {
    int l=0;
    int r=list.size()-1;
    int mid = 0;
    while(l<r){
        mid = l + (r-l)/2;
        if(list[mid] > item){
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }
    if(l==r && item > list[l]){
        return 0;
    }
    return list.size()-l;
}
 
// Helper function to delete the first occurrence of 'item' from the sorted 'list'
void DeleteItemFromSortedList(vector<int>& list, int item) {
    int index = lower_bound(list.begin(), list.end(), item) - list.begin();
    list.erase(list.begin() + index);
}
 
// Function to count the number of elements greater than each element in the input list 'list'
vector<int> CountLarge(vector<int>& list) {
    // Create a sorted copy of the input list
    vector<int> sortedList = list;
    sort(sortedList.begin(), sortedList.end());
 
    // For each element in the input list, count the number of elements greater than it
    for (int i = 0; i < list.size(); i++) {
        DeleteItemFromSortedList(sortedList, list[i]);
        list[i] = CountLargeNumbers(list[i], sortedList);
    }
    return list;
}
 
// Helper function to print the contents of a vector
void PrintArray(vector<int>& list) {
    for (int i = 0; i < list.size(); i++) {
        cout << list[i] << " ";
    }
    cout << endl;
}
 
// Main function
int main() {
    // Create an input vector
    vector<int> arr = {3, 7, 1, 5, 9, 2};
 
    // Call the 'CountLarge' function to count the number of elements greater than each element in 'arr'
    vector<int> res = CountLarge(arr);
 
    // Print the result vector
    PrintArray(res);
 
    return 0;
}

Java

import java.util.*;
 
public class Main {
    // Helper function to count the number of elements greater than 'item' in the sorted 'list'
    public static int countLargeNumbers(int item, List<Integer> list) {
        int l = 0;
        int r = list.size() - 1;
        int mid = 0;
        while (l < r) {
            mid = l + (r - l) / 2;
            if (list.get(mid) > item) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (l == r && item > list.get(l)) {
            return 0;
        }
        return list.size() - l;
    }
 
    // Helper function to delete the first occurrence of 'item' from the sorted 'list'
    public static void deleteItemFromSortedList(List<Integer> list, int item) {
        int index = Collections.binarySearch(list, item);
        if (index >= 0) {
            list.remove(index);
        }
    }
 
    // Function to count the number of elements greater than each element in the input list 'list'
    public static List<Integer> countLarge(List<Integer> list) {
        // Create a sorted copy of the input list
        List<Integer> sortedList = new ArrayList<>(list);
        Collections.sort(sortedList);
 
        // For each element in the input list, count the number of elements greater than it
        for (int i = 0; i < list.size(); i++) {
            deleteItemFromSortedList(sortedList, list.get(i));
            list.set(i, countLargeNumbers(list.get(i), sortedList));
        }
        return list;
    }
 
    // Helper function to print the contents of a list
    public static void printList(List<Integer> list) {
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
    }
 
    // Main function
    public static void main(String[] args) {
        // Create an input list
        List<Integer> arr = new ArrayList<>(Arrays.asList(3, 7, 1, 5, 9, 2));
 
        // Call the 'countLarge' function to count the number of elements greater than each element in 'arr'
        List<Integer> res = countLarge(arr);
 
        // Print the result list
        printList(res);
    }
}

Python3

def CountLarge(list):
    sortedList = sorted(list)
    for i in range(len(list)):
        DeleteItemFromSortedList(sortedList, list[i])
        list[i] = CountLargeNumbers(list[i], sortedList)
    return list
 
def CountLargeNumbers(item, list):
    l=0
    r=len(list)-1
    mid = 0
    while(l<r):
        mid = l + (r-l)//2
        if(list[mid] > item):
            r = mid
        else:
            l = mid + 1
    if(l==r and item > list[l]):
        return 0
    return len(list)-l
 
def DeleteItemFromSortedList(list, item):
    index = BinarySearch(list, item)
    list.pop(index)
 
def BinarySearch(list, item):
    l=0
    r=len(list)-1
    mid = 0
    while(l<=r):
        mid = l + (r-l)//2
        if(list[mid] == item):
            return mid
        elif(list[mid] < item):
            l = mid + 1
        else:
            r = mid - 1
    return -1
 
def PrintArray(list):
    for item in list:
        print(item, end=" ")
 
arr = [3, 7, 1, 5, 9, 2]
 
res = CountLarge(arr)
 
PrintArray(res)

C#

using System;
using System.Collections.Generic;
 
public class GFG{
    static public void Main (){
        //Code
          var arr = new List<int>(){3, 7, 1, 5, 9, 2};
        var res = CountLarge(arr);
        PrintArray(res);
    }
    public static List<int> CountLarge(List<int> list)
    {
        var sortedList = new List<int>(list);
        sortedList.Sort();
        for(int i=0;i<list.Count;i++){
            DeleteItemFromSortedList(sortedList, list[i]);
            list[i] = CountLargeNumbers(list[i], sortedList);
        }
        return list;
    }
    public static int CountLargeNumbers(int item, List<int> list){
        int l=0,r=list.Count-1,mid;
        while(l<r){
            mid = l + (r-l)/2;
            if(list[mid] > item)
                r = mid;
            else
                l = mid + 1;
        }
        if(l==r && item > list[l])
            return 0;
        return list.Count-l;
    }
    public static void DeleteItemFromSortedList(List<int> list, int item){
        var index = BinarySearch(list, item);
        list.RemoveAt(index);
    }
    public static int BinarySearch(List<int> list, int item){
        int l=0,r=list.Count-1,mid;
        while(l<=r){
            mid = l + (r-l)/2;
            if(list[mid] == item)
                return mid;
            else if(list[mid] < item)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return -1;
    }
    public static void PrintArray(List<int> list)
    {
        foreach(var item in list)
            Console.Write(item + " ");
    }
}

Javascript

<script>
function main() {
  //Code
  const arr = [3, 7, 1, 5, 9, 2];
  const res = countLarge(arr);
  printArray(res);
}
 
function countLarge(list) {
  const sortedList = [...list];
  sortedList.sort();
  for (let i = 0; i < list.length; i++) {
    deleteItemFromSortedList(sortedList, list[i]);
    list[i] = countLargeNumbers(list[i], sortedList);
  }
  return list;
}
 
function countLargeNumbers(item, list) {
  let l = 0;
  let r = list.length - 1;
  let mid;
  while (l < r) {
    mid = l + Math.floor((r - l) / 2);
    if (list[mid] > item) r = mid;
    else l = mid + 1;
  }
  if (l === r && item > list[l]) return 0;
  return list.length - l;
}
 
function deleteItemFromSortedList(list, item) {
  const index = binarySearch(list, item);
  list.splice(index, 1);
}
 
function binarySearch(list, item) {
  let l = 0;
  let r = list.length - 1;
  let mid;
  while (l <= r) {
    mid = l + Math.floor((r - l) / 2);
    if (list[mid] === item) return mid;
    else if (list[mid] < item) l = mid + 1;
    else r = mid - 1;
  }
  return -1;
}
 
function printArray(list) {
  for (const item of list) {
    document.write(item + " ");
  }
}
 
main();
 
</script>

Output

3 1 3 1 0 0

Time Complexity: O(N^2)
Auxiliary Space: O(N)

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!