Count of Array elements greater than all elements on its left and at least K elements on its right

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.Â
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:Â
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;Â
// Structure of an AVL Tree Nodestruct node {    int key;    struct node* left;    struct node* right;    int height;    // Size of the tree rooted    // with this node    int size;};Â
// Utility function to get maximum// of two integersint max(int a, int b);Â
// Utility function to get height// of the tree rooted with Nint height(struct node* N){Â Â Â Â if (N == NULL)Â Â Â Â Â Â Â Â return 0;Â Â Â Â return N->height;}Â
// Utility function to find size of// the tree rooted with Nint size(struct node* N){Â Â Â Â if (N == NULL)Â Â Â Â Â Â Â Â return 0;Â Â Â Â return N->size;}Â
// Utility function to get maximum// of two integersint max(int a, int b){Â Â Â Â return (a > b) ? a : b;}Â
// Helper function to allocates a// new node with the given keystruct node* newNode(int key){    struct node* node        = (struct node*)            malloc(sizeof(struct node));    node->key = key;    node->left = NULL;    node->right = NULL;    node->height = 1;    node->size = 1;    return (node);}Â
// Utility function to right rotate// subtree rooted with ystruct node* rightRotate(struct node* y){Â Â Â Â struct node* x = y->left;Â Â Â Â struct 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 xstruct node* leftRotate(struct node* x){Â Â Â Â struct node* y = x->right;Â Â Â Â struct 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 Nint getBalance(struct 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 nodestruct node* insert(struct node* node, int key,                    int* count){    // Perform the normal BST rotation    if (node == NULL)        return (newNode(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 = *count + 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 rightvoid constructLowerArray(int arr[],                         int countSmaller[],                         int n){    int i, j;    struct node* root = NULL;Â
    for (i = 0; i < n; i++)        countSmaller[i] = 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 rightint countElements(int A[], int n, int K){Â
    int count = 0;Â
    // Stores the count of smaller    // elements on its right    int* countSmaller        = (int*)malloc(sizeof(int) * n);    constructLowerArray(A, countSmaller, n);Â
    int maxi = INT_MIN;    for (int i = 0; i <= (n - K - 1); i++) {        if (A[i] > maxi && countSmaller[i] >= K) {            count++;            maxi = A[i];        }    }Â
    return count;}Â
// Driver Codeint main(){Â
    int A[] = { 2, 5, 1, 7, 3, 4, 0 };    int n = sizeof(A) / sizeof(int);    int K = 3;Â
    cout << countElements(A, n, K);Â
    return 0;} |
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 referenceestatic 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 |
Python3
# Python program to implement# the above approachimport sysÂ
# Structure of an AVL Tree Nodeclass Node: Â Â Â Â def __init__(self, key):Â Â Â Â Â Â Â Â self.key = key; Â Â Â Â Â Â Â Â self.left = None;Â Â Â Â Â Â Â Â self.right = None;Â Â Â Â Â Â Â Â self.height = 1;Â Â Â Â Â Â Â Â self.size = 1;Â
# Helper class to pass Integer# as referenceeclass RefInteger:Â Â Â Â def __init__(self, data):Â Â Â Â Â Â Â Â self.value = data;Â Â Â Â Â # Utility function to get height# of the tree rooted with Ndef height(N):Â Â Â Â if (N == None):Â Â Â Â Â Â Â Â return 0;Â
    return N.height;Â
# Utility function to find size of# the tree rooted with Ndef size(N):Â Â Â Â if (N == None):Â Â Â Â Â Â Â Â return 0;Â
    return N.size;Â
# Utility function to get maximum# of two integersdef max(a, b):Â Â Â Â if(a>b):Â Â Â Â Â Â Â Â return a;Â Â Â Â else:Â Â Â Â Â Â Â Â return b;Â
# Utility function to right rotate# subtree rooted with ydef rightRotate(y):Â Â Â Â x = y.left;Â Â Â Â 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 xdef leftRotate(x):Â Â Â Â y = x.right;Â Â Â Â 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 Ndef getBalance(N):Â Â Â Â if (N == None):Â Â Â Â Â Â Â Â return 0;Â
    return height(N.left) - height(N.right);Â
# Function to insert a new key to the# tree rooted with Nodedef insert(node, key, count):Â
    # Perform the normal BST rotation    if (node == None):        return 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    balance = getBalance(node);Â
    # Left Left Case    if (balance > 1 and key < node.left.key):        return rightRotate(node);Â
    # Right Right Case    if (balance < -1 and key > node.right.key):        return leftRotate(node);Â
    # Left Right Case    if (balance > 1 and key > node.left.key):        node.left = leftRotate(node.left);        return rightRotate(node);     Â
    # Right Left Case    if (balance < -1 and 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 rightdef constructLowerArray(arr, countSmaller, n):Â Â Â Â root = None;Â
    for i in range(n):        countSmaller[i] = RefInteger(0);Â
    # Insert all elements in the AVL Tree    # and get the count of smaller elements    for i in range(n - 1, -1,-1):        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 rightdef countElements(A, n, K):    count = 0;Â
    # Stores the count of smaller    # elements on its right    countSmaller = [0 for i in range(n)];    constructLowerArray(A, countSmaller, n);Â
    maxi = -sys.maxsize;    for i in range(n - K):        if (A[i] > maxi and countSmaller[i].value >= K):            count += 1;            maxi = A[i];             return count;Â
# Driver Codeif __name__ == '__main__':Â Â Â Â A = [ 2, 5, 1, 7, 3, 4, 0 ];Â Â Â Â n = len(A);Â Â Â Â K = 3;Â
    print(countElements(A, n, K));Â
# This code is contributed by Rajput-Ji |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;Â
class GFG{Â
// Structure of an AVL Tree Nodepublic class Node{    public int key;    public Node left;    public Node right;    public int height;         // Size of the tree rooted    // with this Node    public int size;Â
    public Node(int key)     {        this.key = key;        this.left = this.right = null;        this.size = this.height = 1;    }};Â
// Helper class to pass int// as referenceepublic class Refint {Â Â Â Â public int value;Â Â Â Â Â Â Â Â Â public Refint(int 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,                    Refint 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, Â Â Â Â Â Â Â Â Â Refint[] countSmaller, int n) {Â Â Â Â int i; Â Â Â Â //int j;Â Â Â Â Node root = null;Â
    for(i = 0; i < n; i++)        countSmaller[i] = new Refint(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    Refint[] countSmaller = new Refint[n];    constructLowerArray(A, countSmaller, n);Â
    int maxi = int.MinValue;    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;Â
    Console.WriteLine(countElements(A, n, K));}}Â
// This code is contributed by Princi Singh |
Javascript
<script>// javascript program to implement// the above approach   Â
// Structure of an AVL Tree Node     class Node     {Â
        // Size of the tree rooted        // with this Node        constructor(key) {            this.key = key;            this.left = this.right = null;            this.size = this.height = 1;        }    };Â
    // Helper class to pass Integer    // as referencee     class RefInteger {         constructor(value) {            this.value = value;        }    }Â
    // Utility function to get height    // of the tree rooted with N    function height(N) {        if (N == null)            return 0;Â
        return N.height;    }Â
    // Utility function to find size of    // the tree rooted with N    function size(N) {        if (N == null)            return 0;Â
        return N.size;    }Â
    // Utility function to get maximum    // of two integers    function max(a , b) {        return (a > b) ? a : b;    }Â
    // Utility function to right rotate    // subtree rooted with y    function rightRotate(y)     {        var x = y.left;        var 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 x    function leftRotate(x)    {        var y = x.right;        var 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 N    function getBalance(N) {        if (N == null)            return 0;Â
        return height(N.left) - height(N.right);    }Â
    // Function to insert a new key to the    // tree rooted with Node    function insert(node , key, 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        var 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 right    function constructLowerArray(arr, countSmaller , n)     {        var i, j;        var 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 right    function countElements(A , n , K) {        var count = 0;Â
        // Stores the count of smaller        // elements on its right        var countSmaller = [];        constructLowerArray(A, countSmaller, n);Â
        var maxi = Number.MIN_VALUE;        for (i = 0; i <= (n - K - 1); i++) {            if (A[i] > maxi && countSmaller[i].value >= K) {                count++;                maxi = A[i];            }        }        return count;    }Â
    // Driver Code             var A = [ 2, 5, 1, 7, 3, 4, 0 ];        var n = A.length;        var K = 3;Â
        document.write(countElements(A, n, K));Â
// This code is contributed by Rajput-Ji</script> |
2
Â
Time Complexity: O(NlogN)Â
Auxiliary Space: O(N)
Â
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!


