Open In App

Surpasser Count of Each Element in Array

Last Updated : 25 Nov, 2024
Comments
Improve
Suggest changes
Like Article
Like
Report

Given an array of distinct integers arr[], the task is to find the surpasser count for each element of the array.

A surpasser of an element in an array is any element to its right that is greater than it, i.e., arr[j] is a surpasser of arr[i] if i < j and arr[i] < arr[j]. The surpasser count of an element is the number of surpassers.

Examples: 

Input: arr[] = [2, 7, 5, 3, 8, 1]
Output: [4, 1, 1, 1, 0, 0]
Explanation:

  • For 2, there are 4 greater elements to its right: [7, 5, 3, 8]
  • For 7, there is 1 greater element to its right: [8]
  • For 5, there is 1 greater element to its right: [8]
  • For 3, there is 1 greater element to its right: [8]
  • For 8, there is no greater element to its right: [0]
  • For 1, there is no greater element to its right: [0]

Input: arr[] = [4, 5, 1]
Output: [1, 0, 0]
Explanation:

  • For 4, there is 1 greater element to its right: [5]
  • For 5, there is no greater element to its right: [0]
  • For 1, there is no greater element to its right: [0]

[Naive Approach] – Using Two Nested Loops – O(n^2) Time and O(1) Space

The simplest approach is to iterate through the array, and for each element count the number of elements to its right that is greater than it.

C++
// C++ program to find the surpasser count of 
// each element using two nested loops

#include <iostream>
#include <vector>
using namespace std;

vector<int> findSurpasser(vector<int> &arr) {
    int n = arr.size();
  
    // array to store surpasser counts
    vector<int> res(n, 0);
    
    for (int i = 0; i < n; i++) {
      
        // Find surpasser for arr[i]
        int count = 0;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] > arr[i])
                count++;
        }
       
        res[i] = count; 
    }
    return res;
}

int main() {
    vector<int> arr = {2, 7, 5, 3, 8, 1};
    vector<int> res = findSurpasser(arr);    
    for (int count : res) 
        cout << count << " ";
  
    return 0;
}
C
// C program to find the surpasser count of each
// element using two nested loops

#include <stdio.h>
#include <stdlib.h>

int* findSurpasser(int arr[], int n) {
  
    // Array to store surpasser counts
    int* res = (int*)malloc(n * sizeof(int));
  
    for (int i = 0; i < n; i++) {

        // Find surpasser for arr[i]
        int count = 0;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] > arr[i])
                count++;
        }
        res[i] = count;
    }
  
    return res;
}

int main() {
    int arr[] = {2, 7, 5, 3, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int* res = findSurpasser(arr, n);
    for (int i = 0; i < n; i++)
        printf("%d ", res[i]);
    
    return 0;
}
Java
// Java program to find the surpasser count of each
// element using two nested loops

import java.util.ArrayList;
import java.util.List;

class GfG {
    static List<Integer> findSurpasser(int[] arr) {
        int n = arr.length;
        
        // List to store surpasser counts
        List<Integer> res = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            
            // Find surpasser for arr[i]
            int count = 0;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[i])
                    count++;
            }
            
            res.add(count);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {2, 7, 5, 3, 8, 1};
        List<Integer> res = findSurpasser(arr);        
        for (int count : res)
            System.out.print(count + " ");
    }
}
Python
# Python program to find the surpasser count  
# of each element using two nested loops

def findSurpasser(arr):
    n = len(arr)
  
    # List to store surpasser counts
    res = [0] * n
    
    for i in range(n):
        
        # Find surpasser for arr[i]
        count = 0
        for j in range(i + 1, n):
            if arr[j] > arr[i]:
                count += 1
        
        res[i] = count
    return res

arr = [2, 7, 5, 3, 8, 1]
result = findSurpasser(arr)
print(result)
C#
// C# program to find the surpasser count of each
// element using two nested loops

using System;
using System.Collections.Generic;

class GfG {
    static List<int> FindSurpasser(int[] arr) {
        int n = arr.Length;
      
        // List to store surpasser counts
        List<int> res = new List<int>();
        
        for (int i = 0; i < n; i++) {
          
            // Find surpasser for arr[i]
            int count = 0;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[i])
                    count++;
            }
            
            res.Add(count); 
        }
        return res;
    }

    static void Main(string[] args) {
        int[] arr = { 2, 7, 5, 3, 8, 1 };
        List<int> result = FindSurpasser(arr);        
        foreach (int count in result)
            Console.Write(count + " ");
    }
}
JavaScript
// JavaScript program to find the surpasser count  
// of each element using two nested loops

function findSurpasser(arr) {
    const n = arr.length;
  
    // array to store surpasser counts
    let res = new Array(n).fill(0);
    
    for (let i = 0; i < n; i++) {
        
        // Find surpasser for arr[i]
        let count = 0;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] > arr[i])
                count++;
        }
        
        res[i] = count;
    }
    return res;
}

// Driver Code
const arr = [2, 7, 5, 3, 8, 1];
const result = findSurpasser(arr);
console.log(result.join(" "));

Output
4 1 1 1 0 0 

[Expected Approach] – Using Merge Step of Merge Sort – O(n Log n) Time and O(n) Space

In this approach, we use the merge step of merge sort. During the merge, if the ith element in the left half is smaller than the jth element in the right half, it means that all remaining elements in the right half (from j to end) are greater than the ith element in the left half (since both halves are sorted). Therefore, we add the number of remaining elements in the right half to the surpasser count of the ith element of the left half. This process is repeated for all elements in the left half as they are merged with the right half.

Since all the elements in the array are distinct, we use a hash map to keep store of the surpasser count for each element. After the merge sort is complete, we fill the result array with the surpasser counts, maintaining the same order as the original input.


C++
// C++ program to find the surpasser count of each element
// using merge step of merge sort

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// Merge function to sort the array and update surpasser counts
int merge(vector<int> &arr, int lo, int mid, int hi, 
                            unordered_map<int, int> &m) {
  
    int n1 = mid - lo + 1;
    int n2 = hi - mid;
    vector<int> left(n1), right(n2); 
    
    // Copy data into temporary arrays left[] and right[]
    for (int i = 0; i < n1; i++)
        left[i] = arr[lo + i]; 
        
    for (int j = 0; j < n2; j++)
        right[j] = arr[mid + 1 + j]; 

    int i = 0, j = 0, k = lo;
    
    // Merging two halves
    while (i < n1 && j < n2) {
      
        // All elements in right[j..n2] are greater than left[i]
        // So add n2 - j, in surpasser count of left[i]
        if (left[i] < right[j]) {
            m[left[i]] += n2 - j;  
            arr[k++] = left[i++];
        } 
        else {
            arr[k++] = right[j++];
        }
    }

    // Copy remaining elements of left[] if any
    while (i < n1)
        arr[k++] = left[i++];

    // Copy remaining elements of right[] if any
    while (j < n2)
        arr[k++] = right[j++];
}

void mergeSort(vector<int> &arr, int lo, int hi, 
               unordered_map<int, int> &m) {
    if (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        
        // Sort left and right half
        mergeSort(arr, lo, mid, m); 
        mergeSort(arr, mid + 1, hi, m);
        
        // Merge them
        merge(arr, lo, mid, hi, m);  
    }
}

vector<int> findSurpasser(vector<int>& arr) {
    int n = arr.size();
    
    // Map to store surpasser counts
    unordered_map<int, int> m;
    
    // Duplicate array to perform merge Sort
    // so that orginial array is not modified
    vector<int> dup = arr;  

    mergeSort(dup, 0, n - 1, m);  

    // Store surpasser counts in result array
    // in the same order as given array
    vector<int> res(n);
    for (int i = 0; i < n; i++)
        res[i] = m[arr[i]]; 
    
    return res;
}

int main() {
    vector<int> arr = {2, 7, 5, 3, 8, 1};
    vector<int> res = findSurpasser(arr);  
    for (int count : res)
        cout << count << " ";
    return 0;
}
Java
// Java program to find the surpasser count of each element using
// merge step of merge sort

import java.util.*;

class GfG {

    // Merge function to sort the array 
    // and update surpasser counts
    static int merge(int[] arr, int lo, int mid, int hi, 
                            Map<Integer, Integer> m) {

        int n1 = mid - lo + 1;
        int n2 = hi - mid;
        int[] left = new int[n1];
        int[] right = new int[n2];

        // Copy data into temporary arrays left[] and right[]
        for (int i = 0; i < n1; i++)
            left[i] = arr[lo + i];

        for (int j = 0; j < n2; j++)
            right[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = lo;

        // Merging two halves
        while (i < n1 && j < n2) {

            // All elements in right[j..n2] are greater than left[i]
            // So add n2 - j, in surpasser count of left[i]
            if (left[i] < right[j]) {
                m.put(left[i], m.getOrDefault(left[i], 0) + n2 - j);
                arr[k++] = left[i++];
            } 
            else {
                arr[k++] = right[j++];
            }
        }

        // Copy remaining elements of left[] if any
        while (i < n1)
            arr[k++] = left[i++];

        // Copy remaining elements of right[] if any
        while (j < n2)
            arr[k++] = right[j++];

        return 0;
    }

    static void mergeSort(int[] arr, int lo, int hi, 
                                 Map<Integer, Integer> m) {
        if (lo < hi) {
            int mid = lo + (hi - lo) / 2;

            // Sort left and right half
            mergeSort(arr, lo, mid, m); 
            mergeSort(arr, mid + 1, hi, m);

            // Merge them
            merge(arr, lo, mid, hi, m);
        }
    }

    static List<Integer> findSurpasser(int[] arr) {
        int n = arr.length;

        // Map to store surpasser counts
        Map<Integer, Integer> m = new HashMap<>();

        // Duplicate array to perform merge Sort
        // so that original array is not modified
        int[] dup = arr.clone();

        mergeSort(dup, 0, n - 1, m);

        // Store surpasser counts in result array
        // in the same order as given array
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++)
            res.add(m.getOrDefault(arr[i], 0));

        return res;
    }

    public static void main(String[] args) {
        int[] arr = {2, 7, 5, 3, 8, 1};
        List<Integer> res = findSurpasser(arr);
        for (int count : res)
            System.out.print(count + " ");
    }
}
Python
# Python program to find the surpasser count of each element
# using merge step of merge sort

def merge(arr, lo, mid, hi, m):
    n1 = mid - lo + 1
    n2 = hi - mid
    left = arr[lo:lo+n1]
    right = arr[mid+1:mid+1+n2]

    i = j = 0
    k = lo

    # Merging two halves
    while i < n1 and j < n2:
      
        # All elements in right[j..n2] are greater than left[i]
        # So add n2 - j, in surpasser count of left[i]
        if left[i] < right[j]:
            m[left[i]] += n2 - j
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    # Copy remaining elements of left[] if any
    while i < n1:
        arr[k] = left[i]
        i += 1
        k += 1

    # Copy remaining elements of right[] if any
    while j < n2:
        arr[k] = right[j]
        j += 1
        k += 1

def mergeSort(arr, lo, hi, m):
    if lo < hi:
        mid = lo + (hi - lo) // 2

        # Sort left and right half
        mergeSort(arr, lo, mid, m)
        mergeSort(arr, mid + 1, hi, m)

        # Merge them
        merge(arr, lo, mid, hi, m)

def findSurpasser(arr):
    n = len(arr)
    
    # Map to store surpasser counts
    m = {key: 0 for key in arr}

    # Duplicate array to perform merge Sort
    # so that original array is not modified
    dup = arr[:]
    
    mergeSort(dup, 0, n - 1, m)
    
    # Store surpasser counts in result array
    # in the same order as given array
    res = [m[arr[i]] for i in range(n)]
    
    return res

if __name__ == "__main__":
    arr = [2, 7, 5, 3, 8, 1]    
    result = findSurpasser(arr)    
    print(result)
C#
// C# program to find the surpasser count of each element using
// merge step of merge sort

using System;
using System.Collections.Generic;

class GfG {

    // Merge function to sort the array 
    // and update surpasser counts
    static void Merge(List<int> arr, int lo, int mid, int hi, 
                                Dictionary<int, int> m) {

        int n1 = mid - lo + 1;
        int n2 = hi - mid;
        
        // Use fixed-size arrays for left and right halves
        int[] left = new int[n1];
        int[] right = new int[n2];

        // Copy data into temporary arrays left[] and right[]
        for (int i1 = 0; i1 < n1; i1++)
            left[i1] = arr[lo + i1];
        
        for (int j1 = 0; j1 < n2; j1++)
            right[j1] = arr[mid + 1 + j1];

        int i = 0, j = 0, k = lo;

        // Merging two halves
        while (i < n1 && j < n2) {

            // All elements in right[j..n2] are greater than left[i]
            // So add n2 - j to surpasser count of left[i]
            if (left[i] < right[j]) {
                if (!m.ContainsKey(left[i])) 
                    m[left[i]] = 0;
                m[left[i]] += n2 - j;
                arr[k++] = left[i++];
            } 
            else {
                arr[k++] = right[j++];
            }
        }

        // Copy remaining elements of left[] if any
        while (i < n1)
            arr[k++] = left[i++];

        // Copy remaining elements of right[] if any
        while (j < n2)
            arr[k++] = right[j++];
    }

    static void MergeSort(List<int> arr, int lo, int hi, 
                        Dictionary<int, int> m) {
        if (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            
            // Sort left and right half
            MergeSort(arr, lo, mid, m); 
            MergeSort(arr, mid + 1, hi, m);
            
            // Merge them
            Merge(arr, lo, mid, hi, m);  
        }
    }

    static List<int> FindSurpasser(List<int> arr) {
        int n = arr.Count;

        // Map to store surpasser counts
        Dictionary<int, int> m = new Dictionary<int, int>();

        // Duplicate array to perform merge sort
        // so that original array is not modified
        List<int> dup = new List<int>(arr);

        MergeSort(dup, 0, n - 1, m);

        // Store surpasser counts in result array
        // in the same order as given array
        List<int> res = new List<int>();
        for (int i = 0; i < n; i++) {
            if (m.ContainsKey(arr[i]))
                res.Add(m[arr[i]]);
            else
                res.Add(0);
        }

        return res;
    }

    static void Main() {
        List<int> arr = new List<int> {2, 7, 5, 3, 8, 1};
        List<int> res = FindSurpasser(arr);
        foreach (int count in res)
            Console.Write(count + " ");
    }
}
JavaScript
// JavaScript program to find the surpasser count of each element
// using merge step of merge sort

function merge(arr, lo, mid, hi, m) {
    const n1 = mid - lo + 1;
    const n2 = hi - mid;
    const left = [];
    const right = [];

    // Copy data into temporary arrays left[] and right[]
    for (let i = 0; i < n1; i++)
        left[i] = arr[lo + i];

    for (let j = 0; j < n2; j++)
        right[j] = arr[mid + 1 + j];

    let i = 0, j = 0, k = lo;

    // Merging two halves
    while (i < n1 && j < n2) {

        // All elements in right[j..n2] are greater than left[i]
        // So add n2 - j, in surpasser count of left[i]
        if (left[i] < right[j]) {
            m[left[i]] = (m[left[i]] || 0) + n2 - j;
            arr[k++] = left[i++];
        } 
        else {
            arr[k++] = right[j++];
        }
    }

    // Copy remaining elements of left[] if any
    while (i < n1)
        arr[k++] = left[i++];

    // Copy remaining elements of right[] if any
    while (j < n2)
        arr[k++] = right[j++];
}

function mergeSort(arr, lo, hi, m) {
    if (lo < hi) {
        const mid = Math.floor(lo + (hi - lo) / 2);

        // Sort left and right half
        mergeSort(arr, lo, mid, m);
        mergeSort(arr, mid + 1, hi, m);

        // Merge them
        merge(arr, lo, mid, hi, m);
    }
}

function findSurpasser(arr) {
    const n = arr.length;

    // Map to store surpasser counts
    const m = {};

    // Duplicate array to perform merge Sort
    // so that original array is not modified
    const dup = arr.slice();

    mergeSort(dup, 0, n - 1, m);

    // Store surpasser counts in result array
    // in the same order as given array
    const res = [];
    for (let i = 0; i < n; i++)
        res.push(m[arr[i]] || 0);

    return res;
}

const arr = [2, 7, 5, 3, 8, 1];
const res = findSurpasser(arr);
console.log(res.join(' '));

Output
4 1 1 1 0 0 

Related Articles:



Next Article
Article Tags :
Practice Tags :

Similar Reads