Count array elements having at least one smaller element on its left and right side

Yukti Kumari
Last Updated: May 13, 2022

Introduction

In this article, we will solve the problem to count the number of array elements having at least one smaller element on its left and right side. We will start with a very intuitive and easy to think brute force solution. Then, we will try to optimize our approach further to arrive at an efficient solution in terms of 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 having at least one smaller element on its left and right side.

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 to 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 fifth element 9, the elements 5,7 & 1 are smaller on its 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

If you get an element smaller than the current one in both iterations, then increase the count.
 

Let’s see the code implementation and the time and space complexity analysis in the next section.

C++ Implementation

/*C++ code to count the total number of array elements having at least
one smaller element on its left and right side*/
#include <bits/stdc++.h>
using namespace std;


int cntElements(int array[], int n)
{
    int cnt = 0;
    // we don’t iterate over the boundary elements i.e. arr[0] & arr[n-1]
    for (int i = 1; i <= n - 2; i++)
    {
        bool leftSmaller, rightSmaller;
        leftSmaller = rightSmaller = false;
        // checking on left side
        for (int j = 0; j < i; j++)
        {
            if (array[j] < array[i])
            {
                leftSmaller = true; // got atleast one smaller on left
                break;
            }
        }
        // checking on right side
        for (int j = i + 1; j < n; j++)
        {
            if (array[j] < array[i])
            {
                rightSmaller = true; // got atleast one smaller on right
                break;
            }
        }
        if (leftSmaller == true && rightSmaller == true)
        {
            cnt++;
        }
    }
    return cnt;
}


int main()
{
    int n = 5;
    int array[n] = {5, 7, 1, 9, 4};
    int count = cntElements(array, n);


    cout << "The count of array elements having at least one smaller element on its left and right side is " << count << endl;
}

 

Output

The count of array elements having at least one smaller element on its left and right side is 2 

Time Complexity

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

Space Complexity 

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 grows, 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.

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

Let's see the algorithm step by step-

  1. Iterate over the array elements one by one.
  2. 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 1; 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 side. As the current element is smaller than the stack top and is 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. 
     
  3. Push the current element to the stack.

Illustration

 

 

 

 

Let’s see the code implementation and the time and space complexity analysis in the next section.

C++ Implementation

/*C++ code to count the total number of array elements having at least
one smaller element on its left and right side*/
#include <bits/stdc++.h>
using namespace std;


int cntElements(int array[], int n)
{
    int cnt = 0;
    stack<int> stack;
    for (int i = 0; i < n; i++)
    {
        while (!stack.empty() && array[i] < stack.top())
        {
            if (stack.size() > 1)
            {
                /* the element at stack top has at least one smaller element towards the right
                Which is array[i] on the right, and since stack size is more than 1, then
                it implies that there is at least one element smaller on the left because the stack is
                maintained in increasing order*/
                cnt++;
            }
            stack.pop();
        }
        stack.push(array[i]);
    }
    return cnt;
}


int main()
{
    int n = 7;
    int array[n] = {5, 7, 1, 9, 4, 7, 5};
    int count = cntElements(array, n);


    cout << "The count of array elements having at least one smaller element on its left and right side is " << count << endl;
}

 

Output

The count of array elements having at least one smaller element on its left and right side is 3.

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

  1. What is the difference between stack and queue?
    Stack has only one open end, so it follows the principle of Last in First out(LIFO), and the queue has both ends opened it follows the First in first out(FIFO) principle.
     
  2. What type of data structure a stack is?
    A stack is an abstract data type that holds an ordered, linear sequence of items.
     
  3. When would you use a stack in data structure?
    Stack data structures are useful when the order of actions is important. They ensure that a system does not move onto a new action before completing those before.

Key Takeaways

In this article, we learnt 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 which you can solve optimally using stacks-

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on CodeStudio now!

Was this article helpful ?
1 upvote

Comments

I think the takeaway from this problem can be the intuition to use stack here which is “we needed track of previous elements for the current element (to check smaller on left side)”   So in general stacks can be used in the scenarios where track of previous elements are required for the current solution.

0 upvotes
0 replies
Reply
Published on 24 May, 2022