Given an array arr[] of N positive integers, the task is to find the count of indices i such that all the elements from arr[0] to arr[i – 1] are smaller than arr[i].
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: 4
All indices satisfy the given condition.
Input: arr[] = {4, 3, 2, 1}
Output: 1
Only i = 0 is the valid index.
Approach: The idea is to traverse the array from left to right and keep track of the current maximum, whenever this maximum changes then the current index is a valid index so increment the resulting counter.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count// of indices that satisfy// the given conditionint countIndices(int arr[], int n){ // To store the result int cnt = 0; // To store the current maximum // Initialized to 0 since there are only // positive elements in the array int max = 0; for (int i = 0; i < n; i++) { // i is a valid index if (max < arr[i]) { // Update the maximum so far max = arr[i]; // Increment the counter cnt++; } } return cnt;}// Driver codeint main(){ int arr[] = { 1, 2, 3, 4 }; int n = sizeof(arr) / sizeof(int); cout << countIndices(arr, n); return 0;} |
Java
// Java implementation of the approachclass GFG {// Function to return the count// of indices that satisfy// the given conditionstatic int countIndices(int arr[], int n){ // To store the result int cnt = 0; // To store the current maximum // Initialized to 0 since there are only // positive elements in the array int max = 0; for (int i = 0; i < n; i++) { // i is a valid index if (max < arr[i]) { // Update the maximum so far max = arr[i]; // Increment the counter cnt++; } } return cnt;}// Driver codepublic static void main(String[] args) { int arr[] = { 1, 2, 3, 4 }; int n = arr.length; System.out.println(countIndices(arr, n));}}// This code is contributed by Rajput-Ji |
Python3
# Python implementation of the approach# Function to return the count# of indices that satisfy# the given conditiondef countIndices(arr, n): # To store the result cnt = 0; # To store the current maximum # Initialized to 0 since there are only # positive elements in the array max = 0; for i in range(n): # i is a valid index if (max < arr[i]): # Update the maximum so far max = arr[i]; # Increment the counter cnt += 1; return cnt;# Driver codeif __name__ == '__main__': arr = [ 1, 2, 3, 4 ]; n = len(arr); print(countIndices(arr, n));# This code is contributed by 29AjayKumar |
C#
// C# implementation of the approachusing System; class GFG {// Function to return the count// of indices that satisfy// the given conditionstatic int countIndices(int []arr, int n){ // To store the result int cnt = 0; // To store the current maximum // Initialized to 0 since there are only // positive elements in the array int max = 0; for (int i = 0; i < n; i++) { // i is a valid index if (max < arr[i]) { // Update the maximum so far max = arr[i]; // Increment the counter cnt++; } } return cnt;}// Driver codepublic static void Main(String[] args) { int []arr = { 1, 2, 3, 4 }; int n = arr.Length; Console.WriteLine(countIndices(arr, n));}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// javascript implementation of the approach // Function to return the count // of indices that satisfy // the given condition function countIndices(arr , n) { // To store the result var cnt = 0; // To store the current maximum // Initialized to 0 since there are only // positive elements in the array var max = 0; for (i = 0; i < n; i++) { // i is a valid index if (max < arr[i]) { // Update the maximum so far max = arr[i]; // Increment the counter cnt++; } } return cnt; } // Driver code var arr = [ 1, 2, 3, 4 ]; var n = arr.length; document.write(countIndices(arr, n));// This code contributed by aashish1995 </script> |
Output:
4
Time Complexity: O(n)
Auxiliary Space: O(1)
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!
