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

Introduction

This blog finds the number of array elements greater than all on its left and at least K elements on its right.

Problem Statement

The problem states that you are given an array arr[ ] of N distinct elements and integer K; you have to find a number of elements greater than all elements on its left and at least K elements on its right.

Let's take some examples to understand this problem better.

Sample Examples

Example 1:

Given Array- arr[] = { 4, 3, 6, 1, 2}, K = 2
Output - 2

Explanation: 

There are two elements greater than all elements on its left and at least K elements on its right

1. arr[0] = 4, 4 is first element in array and greater than 2,3,1
2. arr[2] = 6, greater than its left elements and on the right greater than 1 and 2 

Example 2:

Given Array- arr[ ] = {11, 2, 4, 10, 0}, K=3
Output - 1

Explanation:

11 is the only element that is greater than all elements on its left and greater at least 3 elements on its right.

Approach

In this problem, we have to find the number of array elements greater than all elements on its left and at least K elements on its right. From traversing left to the right, we easily track the maximum element; for every maximum element, we have to find a number of elements smaller than that element.

The idea is to use merge sort at the time of merging two arrays. When a greater index element is less than the lower index element, it represents that the greater index element is smaller than all the elements after that lower index because all elements on its left are already sorted. Hence add all the elements after the lower index element for the required count. 

Implementation in C++

//Count of Array elements greater than all elements on its left and at least K elements on its right
#include <bits/stdc++.h>
using namespace std;
vector<int> res;	// store the count of smaller element
void mergeSort(vector<int> &arr, int left, int right, vector<int> &tmp, vector< int > &index)
{
	// return if left is greater then its right
	if (left >= right) return;
	int mid = left + (right - left) / 2;
	// call function from left to mid
	mergeSort(arr, left, mid, tmp, index);
	// call function from mid+1 to right
	mergeSort(arr, mid + 1, right, tmp, index);
	int i = left, j = mid + 1, k = left;
	int count = 0;
	while (i <= mid)
	{
		while (j <= right && arr[index[j]] < arr[index[i]])
		{
			count++;
			tmp[k++] = index[j++];
		}
		res[index[i]] += count;
		tmp[k++] = index[i++];
	}
	// for remaining elements 
	while (j <= right)
	{
		tmp[k++] = index[j++];
	}
	for (i = left; i <= right; i++)
	{
		index[i] = tmp[i];
	}
}
vector<int> countSmaller(vector<int> &arr)
{
	res.resize(arr.size());
	vector<int> tmp(arr.size(), 0);
	vector<int> index;
	for (int i = 0; i < arr.size(); i++)
	{
		index.push_back(i);
	}
	mergeSort(arr, 0, arr.size() - 1, tmp, index);
	return res;
}
// function find number elements greater than all elements on its left and at least K elements on its right
int count_elements(vector<int> &arr, int n, int k)
{
	// array res store count of smaller element on its right
	countSmaller(arr);
	int max_element = INT_MIN;
	int answer = 0;
	for (int i = 0; i < n; i++)
	{

		if (arr[i] > max_element)
		{
			if (res[i] >= k)
				answer++;
		}
		max_element = max(max_element, arr[i]);
	}
	return answer;
}
// Driver code
int main()
{
	int n;
	cin >> n;	// number of element in Array
	vector<int> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	int k;
	cin >> k;
	// function to find count 
	int answer = count_elements(arr, n, k);
	cout << answer;
}

You can also try this code with Online C++ Compiler

Run Code

Input:

9
1 4 2 7 2 4 221 54 23
1

Output:

3

Complexity Analysis

Time complexity - O(N*logN), O(n) for traversing the array, and O(N log N) for store count of next smaller element .

Space complexity - O(N). 

Check out this problem - Count Inversions

Also check out - Inorder Predecessor