Find maximum difference between nearest left and right smaller elements
Given array of integers, the task is to find the maximum absolute difference between nearest left and right smaller element of every element in array.
Note : If there is no smaller element on right side or left side of any element then we take zero as smaller element. For example for leftmost element, nearest smaller element on left side is considered as 0. Similarly for rightmost elements, smaller element on right side is considered as 0.
Examples:
Input : arr[] = {2, 1, 8} Output : 1 Left smaller LS[] {0, 0, 1} Right smaller RS[] {1, 0, 0} Maximum Diff of abs(LS[i]  RS[i]) = 1 Input : arr[] = {2, 4, 8, 7, 7, 9, 3} Output : 4 Left smaller LS[] = {0, 2, 4, 4, 4, 7, 2} Right smaller RS[] = {0, 3, 7, 3, 3, 3, 0} Maximum Diff of abs(LS[i]  RS[i]) = 7  3 = 4 Input : arr[] = {5, 1, 9, 2, 5, 1, 7} Output : 1
A simple solution is to find nearest left and right smaller elements for every element and then update the maximum difference between left and right smaller element , this take O(n^2) time.
An efficient solution takes O(n) time. We use a stack. The idea is based on the approach discussed in next greater element article. The interesting part here is we compute both left smaller and right smaller using same function.
Let input array be 'arr[]' and size of array be 'n' Find all smaller element on left side 1. Create a new empty stack S and an array LS[] 2. For every element 'arr[i]' in the input arr[], where 'i' goes from 0 to n1. a) while S is nonempty and the top element of S is greater than or equal to 'arr[i]': pop S b) if S is empty: 'arr[i]' has no preceding smaller value LS[i] = 0 c) else: the nearest smaller value to 'arr[i]' is top of stack LS[i] = s.top() d) push 'arr[i]' onto S Find all smaller element on right side 3. First reverse array arr[]. After reversing the array, right smaller become left smaller. 4. Create an array RRS[] and repeat steps 1 and 2 to fill RRS (inplace of LS). 5. Initialize result as 1 and do following for every element arr[i]. In the reversed array right smaller for arr[i] is stored at RRS[ni1] return result = max(result, LS[i]RRS[ni1])
Below is implementation of above idea
 C/C++

// C++ program to find the difference b/w left and
// right smaller element of every element in array
#include<bits/stdc++.h>
using
namespace
std;
// Function to fill left smaller element for every
// element of arr[0..n1]. These values are filled
// in SE[0..n1]
void
leftSmaller(
int
arr[],
int
n,
int
SE[])
{
// Create an empty stack
stack<
int
>S;
// Traverse all array elements
// compute nearest smaller elements of every element
for
(
int
i=0; i<n; i++)
{
// Keep removing top element from S while the top
// element is greater than or equal to arr[i]
while
(!S.empty() && S.top() >= arr[i])
S.pop();
// Store the smaller element of current element
if
(!S.empty())
SE[i] = S.top();
// If all elements in S were greater than arr[i]
else
SE[i] = 0;
// Push this element
S.push(arr[i]);
}
}
// Function returns maximum difference b/w Left &
// right smaller element
int
findMaxDiff(
int
arr[],
int
n)
{
int
LS[n];
// To store left smaller elements
// find left smaller element of every element
leftSmaller(arr, n, LS);
// find right smaller element of every element
// first reverse the array and do the same process
int
RRS[n];
// To store right smaller elements in
// reverse array
reverse(arr, arr + n);
leftSmaller(arr, n, RRS);
// find maximum absolute difference b/w LS & RRS
// In the reversed array right smaller for arr[i] is
// stored at RRS[ni1]
int
result = 1;
for
(
int
i=0 ; i< n ; i++)
result = max(result,
abs
(LS[i]  RRS[n1i]));
// return maximum difference b/w LS & RRS
return
result;
}
// Driver program
int
main()
{
int
arr[] = {2, 4, 8, 7, 7, 9, 3};
int
n =
sizeof
(arr)/
sizeof
(arr[0]);
cout <<
"Maximum diff : "
<< findMaxDiff(arr, n) << endl;
return
0;
}
Output:
Maximum Diff : 4
Time complexity : O(n)
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide