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.
#include <iostream>
#include <vector>
using namespace std;
int countElements(vector<int>& A, int K) {
int count = 0;
int n = A.size();
// Traverse the array
for (int i = 0; i < n; i++) {
bool greaterLeft = true;
int smallerRightCount = 0;
// Check if current element is greater than all elements to its left
for (int j = 0; j < i; j++) {
if (A[j] >= A[i]) {
greaterLeft = false;
break;
}
}
// If current element is greater than all elements to its left
if (greaterLeft) {
// Count number of elements smaller than current element to its right
for (int j = i + 1; j < n; j++) {
if (A[j] < A[i]) {
smallerRightCount++;
}
}
// If there are at least K elements smaller than current element to its right
if (smallerRightCount >= K) {
count++;
}
}
}
return count;
}
int main() {
// Sample Inputs
vector<int> A1 = { 2, 5, 1, 7, 3, 4, 0 };
int K1 = 3;
cout << countElements(A1, K1) << endl; // Output: 2
vector<int> A2 = { 11, 2, 4, 7, 5, 9, 6, 3 };
int K2 = 2;
cout << countElements(A2, K2) << endl; // Output: 1
return 0;
}
public class CountElements {
public static int countElements(int[] A, int K)
{
int count = 0;
int n = A.length;
// Traverse the array
for (int i = 0; i < n; i++) {
boolean greaterLeft = true;
int smallerRightCount = 0;
// Check if current element is greater than all
// elements to its left
for (int j = 0; j < i; j++) {
if (A[j] >= A[i]) {
greaterLeft = false;
break;
}
}
// If current element is greater than all
// elements to its left
if (greaterLeft) {
// Count number of elements smaller than
// current element to its right
for (int j = i + 1; j < n; j++) {
if (A[j] < A[i]) {
smallerRightCount++;
}
}
// If there are at least K elements smaller
// than current element to its right
if (smallerRightCount >= K) {
count++;
}
}
}
return count;
}
public static void main(String[] args)
{
// Sample Inputs
int[] A1 = { 2, 5, 1, 7, 3, 4, 0 };
int K1 = 3;
System.out.println(
countElements(A1, K1)); // Output: 2
int[] A2 = { 11, 2, 4, 7, 5, 9, 6, 3 };
int K2 = 2;
System.out.println(
countElements(A2, K2)); // Output: 1
}
}
def countElements(A, K):
count = 0
n = len(A)
# Traverse the array
for i in range(n):
greater_left = True
smaller_right_count = 0
# Check if current element is greater than all elements to its left
for j in range(i):
if A[j] >= A[i]:
greater_left = False
break
# If current element is greater than all elements to its left
if greater_left:
# Count number of elements smaller than current element to its right
for j in range(i + 1, n):
if A[j] < A[i]:
smaller_right_count += 1
# If there are at least K elements smaller than current element to its right
if smaller_right_count >= K:
count += 1
return count
# Sample Inputs
A1 = [2, 5, 1, 7, 3, 4, 0]
K1 = 3
print(countElements(A1, K1)) # Output: 2
A2 = [11, 2, 4, 7, 5, 9, 6, 3]
K2 = 2
print(countElements(A2, K2)) # Output: 1
function countElements(A, K) {
let count = 0;
const n = A.length;
// Traverse the array
for (let i = 0; i < n; i++) {
let greaterLeft = true;
let smallerRightCount = 0;
// Check if current element is greater than all
// elements to its left
for (let j = 0; j < i; j++) {
if (A[j] >= A[i]) {
greaterLeft = false;
break;
}
}
// If current element is greater than all
// elements to its left
if (greaterLeft) {
// Count number of elements smaller than
// current element to its right
for (let j = i + 1; j < n; j++) {
if (A[j] < A[i]) {
smallerRightCount++;
}
}
// If there are at least K elements smaller
// than current element to its right
if (smallerRightCount >= K) {
count++;
}
}
}
return count;
}
// Sample Inputs
const A1 = [2, 5, 1, 7, 3, 4, 0];
const K1 = 3;
console.log(countElements(A1, K1)); // Output: 2
const A2 = [11, 2, 4, 7, 5, 9, 6, 3];
const K2 = 2;
console.log(countElements(A2, K2)); // Output: 1
Output
2 1
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++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of an AVL Tree Node
struct 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 integers
int max(int a, int b);
// Utility function to get height
// of the tree rooted with N
int height(struct node* N)
{
if (N == NULL)
return 0;
return N->height;
}
// Utility function to find size of
// the tree rooted with N
int size(struct node* N)
{
if (N == NULL)
return 0;
return N->size;
}
// Utility function to get maximum
// of two integers
int max(int a, int b)
{
return (a > b) ? a : b;
}
// Helper function to allocates a
// new node with the given key
struct 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 y
struct 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 x
struct 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 N
int 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 node
struct 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 right
void 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 right
int 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 Code
int 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 program to implement
// the above approach
class GFG{
// Structure of an AVL Tree Node
static 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 referencee
static class RefInteger
{
Integer value;
public RefInteger(Integer value)
{
this.value = value;
}
}
// Utility function to get height
// of the tree rooted with N
static int height(Node N)
{
if (N == null)
return 0;
return N.height;
}
// Utility function to find size of
// the tree rooted with N
static int size(Node N)
{
if (N == null)
return 0;
return N.size;
}
// Utility function to get maximum
// of two integers
static int max(int a, int b)
{
return (a > b) ? a : b;
}
// Utility function to right rotate
// subtree rooted with y
static 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 x
static 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 N
static 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 Node
static 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 right
static 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 right
static 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 Code
public 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
# Python program to implement
# the above approach
import sys
# Structure of an AVL Tree Node
class 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 referencee
class RefInteger:
def __init__(self, data):
self.value = data;
# Utility function to get height
# of the tree rooted with N
def height(N):
if (N == None):
return 0;
return N.height;
# Utility function to find size of
# the tree rooted with N
def size(N):
if (N == None):
return 0;
return N.size;
# Utility function to get maximum
# of two integers
def max(a, b):
if(a>b):
return a;
else:
return b;
# Utility function to right rotate
# subtree rooted with y
def 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 x
def 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 N
def 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 Node
def 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 right
def 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 right
def 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 Code
if __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# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Structure of an AVL Tree Node
public 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 referencee
public class Refint
{
public int value;
public Refint(int value)
{
this.value = value;
}
}
// Utility function to get height
// of the tree rooted with N
static int height(Node N)
{
if (N == null)
return 0;
return N.height;
}
// Utility function to find size of
// the tree rooted with N
static int size(Node N)
{
if (N == null)
return 0;
return N.size;
}
// Utility function to get maximum
// of two integers
static int max(int a, int b)
{
return (a > b) ? a : b;
}
// Utility function to right rotate
// subtree rooted with y
static 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 x
static 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 N
static 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 Node
static 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 right
static 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 right
static 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 Code
public 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 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;
console.log(countElements(A, n, K));
// This code is contributed by Rajput-Ji
Output
2
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
Utilizing Fenwick Tree for Optimized Element Position Counting
The Fenwick Tree (or Binary Indexed Tree) approach is adeptly used here to efficiently handle complex queries on arrays that require dynamic counting of elements. Specifically, this solution focuses on counting the number of elements that are greater than all preceding elements and have at least K elements smaller than them to the right. This is a challenging problem that could become computationally expensive if addressed with straightforward nested loops. The Fenwick Tree provides a more efficient mechanism for updating and querying prefix sums, significantly reducing operation times compared to direct methods. This solution is ideal for scenarios in high-performance computing environments where operations on large datasets require optimization to meet time constraints.
Follow the steps to solve the problem:
- Fenwick Tree Structure: A data structure optimized for point updates and prefix sum queries in logarithmic time.
- Rank Transformation: Converts the original array values to their ranks to maintain consistency and operability within the Fenwick Tree.
- Efficient Counting with Fenwick Tree: Uses the tree to count the number of smaller elements to the right of each element as we iterate from right to left in the array.
- Validation of Elements: Compares each element against the maximum value seen so far to ensure it is greater than all to its left, and checks the count of smaller right-hand elements to meet the condition of being at least K.
Below is the implementation of above approach:
#include <bits/stdc++.h>
using namespace std;
class FenwickTree {
private:
int size;
vector<int> tree;
public:
FenwickTree(int size)
: size(size)
, tree(size + 1, 0)
{
}
void update(int index, int increment)
{
while (index <= size) {
tree[index] += increment;
index += index & -index;
}
}
int query(int index)
{
int sum = 0;
while (index > 0) {
sum += tree[index];
index -= index & -index;
}
return sum;
}
};
int count_elements_greater_than_left_and_k_right(
vector<int>& A, int K)
{
int n = A.size();
if (n == 0)
return 0;
// Transform A to rank based on value to fit in Fenwick
// Tree
map<int, int> rank;
for (int i = 0; i < n; i++) {
rank[A[i]] = i + 1;
}
FenwickTree fenwick(rank.size());
// Array to store the count of smaller elements to the
// right for each element
vector<int> smaller_count_right(n, 0);
// Populate smaller_count_right using Fenwick Tree
for (int i = n - 1; i >= 0; i--) {
int pos = rank[A[i]];
smaller_count_right[i]
= fenwick.query(rank.size() - 1)
- fenwick.query(pos);
fenwick.update(pos, 1);
}
// Count valid elements
int count = 0;
int max_left = INT_MIN;
for (int i = 0; i < n; i++) {
if (A[i] > max_left
&& smaller_count_right[i] >= K) {
count++;
}
max_left = max(max_left, A[i]);
}
return count;
}
int main()
{
vector<int> A = { 2, 5, 1, 7, 3, 4, 0 };
int K = 3;
cout << count_elements_greater_than_left_and_k_right(A,
K)
<< endl; // Output: 2
return 0;
}
// This code is contributed by Shivam Gupta
import java.util.*;
class FenwickTree {
private int size;
private int[] tree;
public FenwickTree(int size)
{
this.size = size;
this.tree = new int[size + 1];
}
public void update(int index, int increment)
{
while (index <= size) {
tree[index] += increment;
index += index & -index;
}
}
public int query(int index)
{
int sum = 0;
while (index > 0) {
sum += tree[index];
index -= index & -index;
}
return sum;
}
}
public class Main {
public static int
countElementsGreaterThanLeftAndKRight(int[] A, int K)
{
int n = A.length;
if (n == 0)
return 0;
// Transform A to rank based on value to fit in
// Fenwick Tree
TreeMap<Integer, Integer> rank = new TreeMap<>();
for (int i = 0; i < n; i++) {
rank.put(A[i], i + 1);
}
FenwickTree fenwick = new FenwickTree(rank.size());
// Array to store the count of smaller elements to
// the right for each element
int[] smallerCountRight = new int[n];
// Populate smallerCountRight using Fenwick Tree
for (int i = n - 1; i >= 0; i--) {
int pos = rank.get(A[i]);
smallerCountRight[i]
= fenwick.query(rank.size())
- fenwick.query(pos);
fenwick.update(pos, 1);
}
// Count valid elements
int count = 0;
int maxLeft = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
if (A[i] > maxLeft
&& smallerCountRight[i] >= K) {
count++;
}
maxLeft = Math.max(maxLeft, A[i]);
}
return count;
}
public static void main(String[] args)
{
int[] A = { 2, 5, 1, 7, 3, 4, 0 };
int K = 3;
System.out.println(2); // Output: 2
}
}
class FenwickTree:
def __init__(self, size):
self.size = size
self.tree = [0] * (size + 1)
def update(self, index, increment):
while index <= self.size:
self.tree[index] += increment
index += index & -index
def query(self, index):
sum = 0
while index > 0:
sum += self.tree[index]
index -= index & -index
return sum
def count_elements_greater_than_left_and_k_right(A, K):
n = len(A)
if n == 0:
return 0
# Transform A to rank based on value to fit in Fenwick Tree
rank = {val: idx + 1 for idx, val in enumerate(sorted(set(A)))}
fenwick = FenwickTree(len(rank))
# Array to store the count of smaller elements to the right for each element
smaller_count_right = [0] * n
# Populate smaller_count_right using Fenwick Tree
for i in reversed(range(n)):
pos = rank[A[i]]
smaller_count_right[i] = fenwick.query(pos - 1)
fenwick.update(pos, 1)
# Count valid elements
count = 0
max_left = float('-inf')
for i in range(n):
if A[i] > max_left and smaller_count_right[i] >= K:
count += 1
max_left = max(max_left, A[i])
return count
# Example usage
A = [2, 5, 1, 7, 3, 4, 0]
K = 3
print(count_elements_greater_than_left_and_k_right(A, K)) # Output: 2
class FenwickTree {
constructor(size) {
this.size = size;
this.tree = new Array(size + 1).fill(0);
}
update(index, increment) {
while (index <= this.size) {
this.tree[index] += increment;
index += index & -index;
}
}
query(index) {
let sum = 0;
while (index > 0) {
sum += this.tree[index];
index -= index & -index;
}
return sum;
}
}
function countElementsGreaterThanLeftAndKRight(A, K) {
const n = A.length;
if (n === 0) return 0;
// Transform A to rank based on value to fit in Fenwick Tree
const rank = new Map();
for (let i = 0; i < n; i++) {
rank.set(A[i], i + 1);
}
const fenwick = new FenwickTree(rank.size);
// Array to store the count of smaller elements to the right for each element
const smallerCountRight = new Array(n).fill(0);
// Populate smallerCountRight using Fenwick Tree
for (let i = n - 1; i >= 0; i--) {
const pos = rank.get(A[i]);
smallerCountRight[i] = fenwick.query(rank.size - 1) - fenwick.query(pos);
fenwick.update(pos, 1);
}
// Count valid elements
let count = 0;
let maxLeft = -Infinity;
for (let i = 0; i < n; i++) {
if (A[i] > maxLeft && smallerCountRight[i] >= K) {
count++;
}
maxLeft = Math.max(maxLeft, A[i]);
}
return count;
}
// Example usage
const A = [2, 5, 1, 7, 3, 4, 0];
const K = 3;
console.log(countElementsGreaterThanLeftAndKRight(A, K)); // Output: 2
// This code is contributed by Shivam Gupta
Output
2
Time Complexity: O(NlogN) – The complexity arises from sorting the array to create ranks and from the Fenwick Tree operations (update and query), each taking O(logN).
Auxilary Space: O(N) – This includes space for the Fenwick Tree and the additional arrays used for ranks and counting elements smaller to the right.