Count the number of elements which are greater than any of element on right side of an array
Given an array Arr[]. The task is to count the number of elements Arr[i] in the given array such that one or more smaller elements are present on the right side of the element Arr[i] in array.
Examples:
Input: Arr[] = { 3, 9, 4, 6, 7, 5 }
Output: 3
Numbers that counts are: 9, 6, 7
9 – As all numbers are present after 9 are smaller than 9,
6 – 5 is smaller element present after it,
7 – 5 is smaller element which is present after it.Input: Arr[] = { 3, 2, 1, 2, 3, 4, 5 }
Output: 2
Approach:
Start traversing array from the last till first element of the array. While traversing maintain a min variable which stores the minimum element till now and a counter variable. Compare min variable with the current element. If min variable is smaller than current element Arr[i], increase the counter and if min is greater than Arr[i] then update the min.
Below is the implementation of the above approach:
C++
// C++ implementation #include <bits/stdc++.h> using namespace std; // function to return the count int count_greater( int arr[], int n) { int min = INT_MAX; int counter = 0; // Comparing the given element // with minimum element till // occurred till now. for ( int i = n - 1; i >= 0; i--) { if (arr[i] > min) { counter++; } // Updating the min variable if (arr[i] <= min) { min = arr[i]; } } return counter; } // Driver code int main() { int arr[] = { 3, 2, 1, 2, 3, 4, 5 }; int n = sizeof (arr) / sizeof ( int ); cout << count_greater(arr, n) << endl; return 0; } |
Java
// Java implementation of the approach class GFG { // function to return the count static int count_greater( int arr[], int n) { int min = Integer.MAX_VALUE; int counter = 0 ; // Comparing the given element // with minimum element till // occurred till now. for ( int i = n - 1 ; i >= 0 ; i--) { if (arr[i] > min) { counter++; } // Updating the min variable if (arr[i] <= min) { min = arr[i]; } } return counter; } // Driver code public static void main(String[] args) { int arr[] = { 3 , 2 , 1 , 2 , 3 , 4 , 5 }; int n = arr.length; System.out.println(count_greater(arr, n)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation for the above approach import sys # function to return the count def count_greater(arr, n) : min = sys.maxsize; counter = 0 ; # Comparing the given element # with minimum element till # occurred till now. for i in range (n - 1 , - 1 , - 1 ) : if (arr[i] > min ) : counter + = 1 ; # Updating the min variable if (arr[i] < = min ) : min = arr[i]; return counter; # Driver code if __name__ = = "__main__" : arr = [ 3 , 2 , 1 , 2 , 3 , 4 , 5 ]; n = len (arr); print (count_greater(arr, n)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; class GFG { // function to return the count static int count_greater( int []arr, int n) { int min = int .MaxValue; int counter = 0; // Comparing the given element // with minimum element till // occurred till now. for ( int i = n - 1; i >= 0; i--) { if (arr[i] > min) { counter++; } // Updating the min variable if (arr[i] <= min) { min = arr[i]; } } return counter; } // Driver code static public void Main () { int []arr = { 3, 2, 1, 2, 3, 4, 5 }; int n = arr.Length; Console.Write(count_greater(arr, n)); } } // This code is contributed by ajit. |
Javascript
<script> // Javascript implementation // Function to return the count function count_greater(arr, n) { let min = Number.MAX_VALUE; let counter = 0; // Comparing the given element // with minimum element till // occurred till now. for (let i = n - 1; i >= 0; i--) { if (arr[i] > min) { counter++; } // Updating the min variable if (arr[i] <= min) { min = arr[i]; } } return counter; } // Driver code let arr = [ 3, 2, 1, 2, 3, 4, 5 ]; let n = arr.length; document.write(count_greater(arr, n) + "<br>" ); // This code is contributed by rishavmahato348 </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us