In this article, we will solve the problem of counting the number of array elements with at least one smaller element on its left and right sides. We will start with a very intuitive and easy to think brute force solution. Then, we will optimise our approach to arriving at an efficient solution regarding time and space complexities.

Letâ€™s get started with the problem statement.

Problem Statement

You are given an array of N integers.

Find the count of array elements with at least one smaller element on its left and right sides.

Example

Input

N=5
Array[] = {5,7,1,9,4 }

Output

Count=2

Explanation

There are no elements towards the left for the first element, so we move forward to check other elements. For the second element, 7, towards the left element smaller than 7 is 5, and towards the right, 1 & 4 are smaller than 7. So, it is counted.

Then for third element 1, there are no smaller elements on the left & right sides. For the fifth element, 9, the elements 5,7 & 1 are smaller on their left, and towards the right, 4 is smaller, so we count it. For 4, we have 1 smaller than 4 on its left but no element on its right.

Hence the count is 2, and the elements are 7 and 9.

Please try to solve this problem on your own before moving on to the further discussion.

Brute Force Approach

The brute force approach is very simple. Just iterate over the array, and for every element on index i, iterate over the elements on its left side from index=0 to index=i-1. If you find a smaller element, repeat the process for the elements on its right side, i.e. from index=i+1 to index=n-1.

Increase the count if you get an element smaller than the current one in both iterations.

In the next section, letâ€™s see the code implementation and the time and space complexity analysis.

Java Implementation

import java.util.ArrayList;
import java.util.List;
public class Solution {
public static void main(String[] args) {
List<Integer> nums = new ArrayList<>();
nums.add(5);
nums.add(7);
nums.add(1);
nums.add(9);
nums.add(4);
int count = countElements(nums);
System.out.println("Count of elements with at least one smaller element on both sides = " + count);
}
public static int countElements(List<Integer> nums) {
int cnt = 0;
int n = nums.size();
// We don't iterate over the boundary elements i.e. nums.get(0) & nums.get(n-1)
for (int i = 1; i <= n - 2; i++) {
boolean isLeftSmaller = false, isRightSmaller = false;
// Checking if there's at least one smaller element on the left side of nums.get(i)
for (int j = 0; j < i; j++) {
if (nums.get(j) < nums.get(i)) {
isLeftSmaller = true; // Found at least one smaller element on the left
break;
}
}
// Checking if there's at least one smaller element on the right side of nums.get(i)
for (int j = i + 1; j < n; j++) {
if (nums.get(j) < nums.get(i)) {
isRightSmaller = true; // Found at least one smaller element on the right
break;
}
}
// If there's at least one smaller element on both sides of nums.get(i), increment count
if (isLeftSmaller && isRightSmaller) {
cnt++;
}
}
return cnt;
}
}

Output

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;
int countElements(vector<int>& nums) {
int cnt = 0;
int n = nums.size();
// We donâ€™t iterate over the boundary elements i.e. nums[0] & nums[n-1]
for (int i = 1; i <= n - 2; i++) {
bool isLeftSmaller = false, isRightSmaller = false;
// Checking if there's at least one smaller element on the left side of nums[i]
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
isLeftSmaller = true; // Found at least one smaller element on the left
break;
}
}
// Checking if there's at least one smaller element on the right side of nums[i]
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[i]) {
isRightSmaller = true; // Found at least one smaller element on the right
break;
}
}
// If there's at least one smaller element on both sides of nums[i], increment count
if (isLeftSmaller && isRightSmaller) {
cnt++;
}
}
return cnt;
}
int main() {
vector<int> nums = {5, 7, 1, 9, 4};
int count = countElements(nums);
cout << "Count of elements with at least one smaller element on both sides = " << count << endl;
return 0;
}

Output

Complexity

Time Complexity

The Time Complexity is O(n^{2}), as in the function cntElements, we have two nested loops, each of which is of length n.

Space Complexity

The Space Complexity, is O(1), as we do not use any extra space.

Stack-based Approach

We can solve the problem easily in O(n^{2}) time complexity. But as n increases, our algorithm will become slow and thus inefficient.

In this section, we will see how we can use stacks to get a solution working in linear time complexity.

We will have all the elements in increasing order from bottom to top in the stack. So, the element at the top of the stack will be maximum, and at the bottom, minimum.

Algorithm

Iterate over the array of elements one by one.

For each element, while the stack is not empty and the current element is less than the stack top, check if the stack size is greater than one, then increase the count by 1.

Why are we doing this? Because the stack top element has one smaller element on its left and right sides. The current element is smaller than the stack top and towards the right. Also, since the stack is maintained in increasing order and the size of the stack is greater than 1, a smaller element exists towards the left. After this, pop the stack top.

Push the current element to the stack.

Dry Run

Suppose we have an array of length 5 as below:

For i=0, i=1 and count=0.

For i=2.

For i =3 and count= 1.

For i=4 and count =1.

Ans is count = 2

Java Implementation

import java.util.*;
public class Main {
static int countElementsWithSmallerNeighbors(int[] nums) {
int count = 0;
Stack<Integer> stk = new Stack<>();
for (int i = 0; i < nums.length; i++) {
/*
Pop all elements greater than the current element from the stack
and count the number of such elements
*/
while (!stk.empty() && nums[i] < stk.peek()) {
stk.pop();
if (!stk.empty()) {
count++;
}
}
// Push the current element onto the stack
stk.push(nums[i]);
}
return count;
}
public static void main(String[] args) {
// Test the countElementsWithSmallerNeighbors() function
int[] nums = {5, 7, 1, 9, 4};
int count = countElementsWithSmallerNeighbors(nums);
System.out.println("Count of elements with at least one smaller element on both sides = " + count);
}
}

Output

C++ Implementation

#include <iostream>
#include <stack>
using namespace std;
int countElementsWithSmallerNeighbors(int nums[], int n) {
int count = 0;
stack<int> stk;
for (int i = 0; i < n; i++) {
/*
Pop all elements greater than the current element from the stack
and count the number of such elements
*/
while (!stk.empty() && nums[i] < stk.top()) {
stk.pop();
//Increment count if the last element popped is the leftmost element.
if(!stk.empty()){
count++;
}
}
// Push the current element onto the stack
stk.push(nums[i]);
}
return count;
}
int main() {
// Test the countElementsWithSmallerNeighbors() function
int nums[] = {5, 7, 1, 9, 4};
int n = sizeof(nums) / sizeof(nums[0]);
int count = countElementsWithSmallerNeighbors(nums, n);
cout << "Count of elements with at least one smaller element on both sides = " << count << endl;
return 0;
}

Output

Complexity

Time Complexity

O(N), as we only iterate once over the array, and every element is pushed and popped at most once only.

Space Complexity

O(N), since we use the stack as an auxiliary space and in the worst-case maximum N number of elements can be there in the stack.

Frequently Asked Questions

What is the space complexity of the optimised approach?

The space complexity of the optimised approach is O(N) for storing the two separate arrays.

Can we further optimise the space complexity?

We can further optimise the space complexity by using two pointers to store the minimum and maximum elements from the left and right sides of the current element, respectively.

What type of data structure is a stack?

A stack is an abstract data type with an ordered, linear sequence of items.

What is the difference between an array and a list?

An array has a fixed size and can store elements of the same data type, while a list can dynamically change in size and can store elements of different data types.

What is the time complexity of binary search?

The time complexity of a binary search algorithm measures how fast the algorithm runs as the size of the input data increases. It is denoted by the notation O(log n), where n is the number of elements searched in the array. This means that the time taken to search for an element using binary search increases slower than the size of the input array. This is because binary search divides the array in half and discards the half that does not contain the target element, which helps to narrow down the search space quickly.

Conclusion

In this article, we learned to solve the problem to count the number of array elements having at least one smaller element on its left and right side.

Stacks proved to be very helpful to get a solution having linear time complexity.

Many problems can be solved easily using the stack data structure.

Problems that you can solve optimally using stacks-