Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Implementation in C++
2.1.1.
Complexity Analysis
3.
Frequently Asked Questions
4.
Key takeaways
Last Updated: Mar 27, 2024

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

Author Ayush Tiwari
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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;
}

 

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

Q1. What is another application of the Merge sort algorithm? 

 Ans. The application of merge-sort are as follows: 

    1 . Merge sort is used for sorting an array and linked-list in O(n log n) time.
    2. It is used for counting inversions in a list.
    3. It can be implemented without extra space for linked lists. 


Q2. What is an application of recursion? 
Ans. Many well-known sorting algorithms (Quick sort, Merge sort, etc.) use recursion.


Q3. What is the difference between ordered_set and unordered_set?
Ans. Ordered_set using a red-black tree and unordered_set using the concept of hashing. Ordered stores the element in sorted order whereas unordered stores in random order.

Key takeaways

This blog finds the number of array elements greater than all elements on its left and at least K elements on its right. We hope you have gained a better understanding of the solution to this problem and, now it is your responsibility to solve the problem and try some new and different approaches to this problem. 

You can learn more about Merge-sortUntil then, Keep practicing, Keep Learning and Keep Coding and practicing in Code studio.

Keep Learning, Keep Going.

Happy Coding!

Previous article
Find the Minimum number of nodes in an AVL Tree
Next article
Sort the big sized array where there are many repetitions of elements
Live masterclass