Count Array Elements having at Least One Smaller Element on its Left and Right Side

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²), 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²) 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

1. Iterate over the array of 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 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. 
    
3. 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-

• Reverse a Stack using Recursion.
   

Recommended Reading:

• Count Subarray for Every Element in an Array in which they are Minimum.
   
• Count Days Remaining for Next Day with Higher Temperature.
   
• Check if an Array is Stack Sortable.
   
• K stacks in a single array.
   
• Distance from Next Greater element
   

Check out The Interview guide for Product Based Companies and some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!