Given an array A[ ] consisting of N distinct integers, the task is to find the number of elements which are strictly greater than all the elements preceding it and strictly greater than at least K elements on its right.
Examples:
Input: A[] = {2, 5, 1, 7, 3, 4, 0}, K = 3
Output: 2
Explanation:
The only array elements satisfying the given conditions are:
- 5: Greater than all elements on its left {2} and at least K(= 3) elements on its right {1, 3, 4, 0}
- 7: Greater than all elements on its left {2, 5, 1} and at least K(= 3) elements on its right {3, 4, 0}
Therefore, the count is 2.
Input: A[] = {11, 2, 4, 7, 5, 9, 6, 3}, K = 2
Output: 1
Naive Approach:
The simplest approach to solve the problem is to traverse the array and for each element, traverse all the elements on its left and check if all of them are smaller than it or not and traverse all elements on its right to check if at least K elements are smaller than it or not. For every element satisfying the conditions, increase count. Finally, print the value of count.
Java
// Java program to find the count of elements// which are strictly greater than all the// elements preceding it and strictly greater// than at least k elements on its rightpublic class GFG { public static int countElements(int[] arr, int k) { int n = arr.length; int count = 0; // Looping through each element in the array for (int i = 0; i < n; i++) { boolean greaterThanAll = true; // Checking if current element is greater than // all elements on its left for (int j = 0; j < i; j++) { if (arr[j] >= arr[i]) { greaterThanAll = false; break; } } // If the current element is greater than all // elements on its left if (greaterThanAll) { int smallerCount = 0; // Checking if the current element is // greater than at least k elements on its // right for (int j = i + 1; j < n; j++) { if (arr[j] < arr[i]) { smallerCount++; } } // If the current element is greater than at // least k elements on its right, increment // the count if (smallerCount >= k) { count++; } } } return count; } public static void main(String[] args) { int[] arr = { 2, 5, 1, 7, 3, 4, 0 }; int k = 3; System.out.println( countElements(arr, k)); // Output: 2 }} |
Output
2
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach:
The above approach can be further optimized by using Self-Balancing BST. Follow the steps below:
- Traverse the array from right to left and insert all elements one by one in an AVL Tree
- Using the AVL Tree generate an array countSmaller[] which contains the count of smaller elements on the right of every array element.
- Traverse the array and for every ith element, check if it is the maximum obtained so far and countSmaller[i] is greater than or equal to K.
- If so, increase count.
- Print the final value of count as the answer.
Below is the implementation of the above approach:
Java
// Java program to implement// the above approachclass GFG{// Structure of an AVL Tree Nodestatic class Node{ int key; Node left; Node right; int height; // Size of the tree rooted // with this Node int size; public Node(int key) { this.key = key; this.left = this.right = null; this.size = this.height = 1; }};// Helper class to pass Integer// as referencestatic class RefInteger { Integer value; public RefInteger(Integer value) { this.value = value; }}// Utility function to get height// of the tree rooted with Nstatic int height(Node N) { if (N == null) return 0; return N.height;}// Utility function to find size of// the tree rooted with Nstatic int size(Node N) { if (N == null) return 0; return N.size;}// Utility function to get maximum// of two integersstatic int max(int a, int b){ return (a > b) ? a : b;}// Utility function to right rotate// subtree rooted with ystatic Node rightRotate(Node y) { Node x = y.left; Node T2 = x.right; // Perform rotation x.right = y; y.left = T2; // Update heights y.height = max(height(y.left), height(y.right)) + 1; x.height = max(height(x.left), height(x.right)) + 1; // Update sizes y.size = size(y.left) + size(y.right) + 1; x.size = size(x.left) + size(x.right) + 1; // Return new root return x;}// Utility function to left rotate// subtree rooted with xstatic Node leftRotate(Node x){ Node y = x.right; Node T2 = y.left; // Perform rotation y.left = x; x.right = T2; // Update heights x.height = max(height(x.left), height(x.right)) + 1; y.height = max(height(y.left), height(y.right)) + 1; // Update sizes x.size = size(x.left) + size(x.right) + 1; y.size = size(y.left) + size(y.right) + 1; // Return new root return y;}// Function to obtain Balance factor// of Node Nstatic int getBalance(Node N){ if (N == null) return 0; return height(N.left) - height(N.right);}// Function to insert a new key to the// tree rooted with Nodestatic Node insert(Node Node, int key, RefInteger count) { // Perform the normal BST rotation if (Node == null) return (new Node(key)); if (key < Node.key) Node.left = insert(Node.left, key, count); else { Node.right = insert(Node.right, key, count); // Update count of smaller elements count.value = count.value + size(Node.left) + 1; } // Update height and size of the ancestor Node.height = max(height(Node.left), height(Node.right)) + 1; Node.size = size(Node.left) + size(Node.right) + 1; // Get the balance factor of the ancestor int balance = getBalance(Node); // Left Left Case if (balance > 1 && key < Node.left.key) return rightRotate(Node); // Right Right Case if (balance < -1 && key > Node.right.key) return leftRotate(Node); // Left Right Case if (balance > 1 && key > Node.left.key) { Node.left = leftRotate(Node.left); return rightRotate(Node); } // Right Left Case if (balance < -1 && key < Node.right.key) { Node.right = rightRotate(Node.right); return leftRotate(Node); } return Node;}// Function to generate an array which// contains count of smaller elements // on the rightstatic void constructLowerArray(int arr[], RefInteger[] countSmaller, int n) { int i, j; Node root = null; for(i = 0; i < n; i++) countSmaller[i] = new RefInteger(0); // Insert all elements in the AVL Tree // and get the count of smaller elements for(i = n - 1; i >= 0; i--) { root = insert(root, arr[i], countSmaller[i]); }}// Function to find the number// of elements which are greater// than all elements on its left// and K elements on its rightstatic int countElements(int A[], int n, int K) { int count = 0; // Stores the count of smaller // elements on its right RefInteger[] countSmaller = new RefInteger[n]; constructLowerArray(A, countSmaller, n); int maxi = Integer.MIN_VALUE; for(int i = 0; i <= (n - K - 1); i++) { if (A[i] > maxi && countSmaller[i].value >= K) { count++; maxi = A[i]; } } return count;}// Driver Codepublic static void main(String[] args) { int A[] = { 2, 5, 1, 7, 3, 4, 0 }; int n = A.length; int K = 3; System.out.println(countElements(A, n, K));}}// This code is contributed by sanjeev2552 |
Output:
2
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
Please refer complete article on Count of Array elements greater than all elements on its left and at least K elements on its right for more details!
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!
