Given an array A[], the task is to find the number of positions i in the array such that all elements before A[i] are greater than A[i].
Note: First element is always counted as there is no other element before it.
Examples:
Input: N = 4, A[] = {2, 1, 3, 5}
Output: 2
The valid positions are 1, 2.
Input : N = 3, A[] = {7, 6, 5}
Output: 3
All three positions are valid positions.
The idea is to calculate the minimum element every time while traversing the array. That is:
- Initialize the first element as the minimum element.
- Every time a new element arrives, check if this is the new minimum, if so, increment number of valid positions and also initialize minimum to the new minimum.
Below is the implementation of the above approach:
CPP
// C++ Program to count positions such that all// elements before it are greater#include <bits/stdc++.h>using namespace std;// Function to count positions such that all// elements before it are greaterint getPositionCount(int a[], int n){ // Count is initially 1 for the first element int count = 1; // Initial Minimum int min = a[0]; // Traverse the array for(int i=1; i<n; i++) { // If current element is new minimum if(a[i] <= min) { // Update minimum min = a[i]; // Increment count count++; } } return count;}// Driver Codeint main(){ int a[] = { 5, 4, 6, 1, 3, 1 }; int n = sizeof(a) / sizeof(a[0]); cout<<getPositionCount(a, n); return 0;} |
Java
// Java Program to count positions such that all// elements before it are greaterclass GFG{// Function to count positions such that all// elements before it are greaterstatic int getPositionCount(int a[], int n){ // Count is initially 1 for the first element int count = 1; // Initial Minimum int min = a[0]; // Traverse the array for(int i = 1; i < n; i++) { // If current element is new minimum if(a[i] <= min) { // Update minimum min = a[i]; // Increment count count++; } } return count;}// Driver Codepublic static void main(String[] args){ int a[] = { 5, 4, 6, 1, 3, 1 }; int n = a.length; System.out.print(getPositionCount(a, n));}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 Program to count positions such that all # elements before it are greater # Function to count positions such that all # elements before it are greater def getPositionCount(a, n) : # Count is initially 1 for the first element count = 1; # Initial Minimum min = a[0]; # Traverse the array for i in range(1, n) : # If current element is new minimum if(a[i] <= min) : # Update minimum min = a[i]; # Increment count count += 1; return count; # Driver Code if __name__ == "__main__" : a = [ 5, 4, 6, 1, 3, 1 ]; n = len(a); print(getPositionCount(a, n)); # This code is contributed by AnkitRai01 |
C#
// C# Program to count positions such that all// elements before it are greaterusing System;class GFG{ // Function to count positions such that all // elements before it are greater static int getPositionCount(int []a, int n) { // Count is initially 1 for the first element int count = 1; // Initial Minimum int min = a[0]; // Traverse the array for(int i = 1; i < n; i++) { // If current element is new minimum if(a[i] <= min) { // Update minimum min = a[i]; // Increment count count++; } } return count; } // Driver Code public static void Main() { int []a = { 5, 4, 6, 1, 3, 1 }; int n = a.Length; Console.WriteLine(getPositionCount(a, n)); }}// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript Program to count positions such that all// elements before it are greater// Function to count positions such that all// elements before it are greaterfunction getPositionCount(a, n){ // Count is initially 1 for the first element var count = 1; // Initial Minimum var min = a[0]; // Traverse the array for(var i = 1; i < n; i++) { // If current element is new minimum if(a[i] <= min) { // Update minimum min = a[i]; // Increment count count++; } } return count;}// Driver Codevar a = [5, 4, 6, 1, 3, 1];var n = a.length;document.write( getPositionCount(a, n));// This code is contributed by itsok.</script> |
Output:
4
Time Complexity: 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
