Find Maximum Difference Between Nearest Left and Right Smaller Elements

In this article, we will solve the problem of finding the maximum absolute difference between the nearest left and right smaller elements of every element in an array.

So in simple words, we are given an array of integers, and our job is to simply find the maximum absolute difference between the nearest left and the nearest right smaller element of every element that is present in the array.

Examples:

Input: arr = [2, 1, 8, 3, 5]

Output: 3

Explanation:

For arr[0] = 2, there is no left smaller element, and the nearest right smaller element is 1.

For arr[1] = 1, there is no left smaller element, and there is no right smaller element.

For arr[2] = 8, the nearest left smaller element is 1, and the nearest right smaller element is 3.

For arr[3] = 3, the nearest left smaller element is 1, and the nearest right smaller element is 2.

For arr[4] = 5, the nearest left smaller element is 3, and there is no right smaller element.

The maximum absolute difference is |3 - 0| = 3.

Solution:

To solve this problem, we will use stacks to efficiently find the nearest smaller elements on both the left and right sides.

Steps to Solve:

1.    Create Two Stacks:

o   One stack to find the nearest smaller elements on the left side.

o   One stack to find the nearest smaller elements on the right side.

2.    Find Nearest Smaller Elements on the Left Side:

o   Iterate through the array from left to right.

o   For each element, use the stack to find the nearest smaller element on the left side and store it in an array.

3.    Find Nearest Smaller Elements on the Right Side:

o   Iterate through the array from right to left.

o   For each element, use the stack to find the nearest smaller element on the right side and store it in an array.

4.    Calculate Maximum Absolute Difference:

o   Iterate through the array and calculate the absolute difference between the nearest left and right smaller elements for each element.

o   Calculate the maximum absolute difference.

Time Complexity: O(N)

Space Complexity: O(N)