Find maximum difference between nearest left and right smaller elements
Last Updated :
06 Jul, 2022
Given an array of integers, the task is to find the maximum absolute difference between the nearest left and the right smaller element of every element in the array.
Note: If there is no smaller element on right side or left side of any element then we take zero as the smaller element. For example for the leftmost element, the nearest smaller element on the left side is considered as 0. Similarly, for rightmost elements, the smaller element on the 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 the nearest left and right smaller elements for every element and then update the maximum difference between left and right smaller element, this takes 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 n-1.
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 (in-place 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[n-i-1]
return result = max(result, LS[i]-RRS[n-i-1])
Below is implementation of above idea
C++
#include<bits/stdc++.h>
using namespace std;
void leftSmaller(int arr[], int n, int SE[])
{
stack<int>S;
for (int i=0; i<n; i++)
{
while (!S.empty() && S.top() >= arr[i])
S.pop();
if (!S.empty())
SE[i] = S.top();
else
SE[i] = 0;
S.push(arr[i]);
}
}
int findMaxDiff(int arr[], int n)
{
int LS[n];
leftSmaller(arr, n, LS);
int RRS[n];
reverse(arr, arr + n);
leftSmaller(arr, n, RRS);
int result = -1;
for (int i=0 ; i< n ; i++)
result = max(result, abs(LS[i] - RRS[n-1-i]));
return result;
}
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;
}
|
Java
import java.util.*;
class GFG
{
static void leftSmaller(int arr[], int n, int SE[])
{
Stack<Integer> S = new Stack<>();
for (int i = 0; i < n; i++)
{
while (!S.empty() && S.peek() >= arr[i])
{
S.pop();
}
if (!S.empty())
{
SE[i] = S.peek();
}
else
{
SE[i] = 0;
}
S.push(arr[i]);
}
}
static int findMaxDiff(int arr[], int n)
{
int[] LS = new int[n];
leftSmaller(arr, n, LS);
int[] RRS = new int[n];
reverse(arr);
leftSmaller(arr, n, RRS);
int result = -1;
for (int i = 0; i < n; i++)
{
result = Math.max(result, Math.abs(LS[i] - RRS[n - 1 - i]));
}
return result;
}
static void reverse(int a[])
{
int i, k, n = a.length;
int t;
for (i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
}
public static void main(String args[])
{
int arr[] = {2, 4, 8, 7, 7, 9, 3};
int n = arr.length;
System.out.println("Maximum diff : "
+ findMaxDiff(arr, n));
}
}
|
Python3
def leftsmaller(arr, n, SE):
sta = []
for i in range(n):
while(sta != [] and sta[len(sta)-1] >= arr[i]):
sta.pop()
if(sta != []):
SE[i]=sta[len(sta)-1]
else:
SE[i]=0
sta.append(arr[i])
def findMaxDiff(arr, n):
ls=[0]*n
rs=[0]*n
leftsmaller(arr, n, ls)
leftsmaller(arr[::-1], n, rs)
res = -1
for i in range(n):
res = max(res, abs(ls[i] - rs[n-1-i]))
return res
if __name__=='__main__':
arr = [2, 4, 8, 7, 7, 9, 3]
print "Maximum Diff :", findMaxDiff(arr, len(arr))
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static void leftSmaller(int []arr, int n, int []SE)
{
Stack<int> S = new Stack<int>();
for (int i = 0; i < n; i++)
{
while (S.Count != 0 && S.Peek() >= arr[i])
{
S.Pop();
}
if (S.Count != 0)
{
SE[i] = S.Peek();
}
else
{
SE[i] = 0;
}
S.Push(arr[i]);
}
}
static int findMaxDiff(int []arr, int n)
{
int[] LS = new int[n];
leftSmaller(arr, n, LS);
int[] RRS = new int[n];
reverse(arr);
leftSmaller(arr, n, RRS);
int result = -1;
for (int i = 0; i < n; i++)
{
result = Math.Max(result, Math.Abs(LS[i] -
RRS[n - 1 - i]));
}
return result;
}
static void reverse(int[] a)
{
int i, k, n = a.Length;
int t;
for (i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
}
public static void Main(String []args)
{
int []arr = {2, 4, 8, 7, 7, 9, 3};
int n = arr.Length;
Console.WriteLine("Maximum diff : " +
findMaxDiff(arr, n));
}
}
|
PHP
<?php
function leftSmaller(&$arr, $n, &$SE)
{
$S = array();
for ($i = 0; $i < $n; $i++)
{
while (!empty($S) && max($S) >= $arr[$i])
array_pop($S);
if (!empty($S))
$SE[$i] = max($S);
else
$SE[$i] = 0;
array_push($S, $arr[$i]);
}
}
function findMaxDiff(&$arr, $n)
{
$LS = array_fill(0, $n, NULL);
leftSmaller($arr, $n, $LS);
$RRS = array_fill(0, $n, NULL);
$k = 0;
for($i = $n - 1; $i >= 0; $i--)
$x[$k++] = $arr[$i];
leftSmaller($x, $n, $RRS);
$result = -1;
for ($i = 0 ; $i < $n ; $i++)
$result = max($result, abs($LS[$i] -
$RRS[$n - 1 - $i]));
return $result;
}
$arr = array(2, 4, 8, 7, 7, 9, 3);
$n = sizeof($arr);
echo "Maximum diff : " .
findMaxDiff($arr, $n) . "\n";
?>
|
Javascript
<script>
function leftSmaller(arr,n,SE)
{
let S=[]
for (let i = 0; i < n; i++)
{
while (S.length!=0 && S[S.length-1] >= arr[i])
{
S.pop();
}
if (S.length!=0)
{
SE[i] = S[S.length-1];
}
else
{
SE[i] = 0;
}
S.push(arr[i]);
}
}
function findMaxDiff(arr,n)
{
let LS = new Array(n);
for(let i=0;i<n;i++)
{
LS[i]=0;
}
leftSmaller(arr, n, LS);
let RRS = new Array(n);
for(let i=0;i<n;i++)
{
RRS[i]=0;
}
reverse(arr);
leftSmaller(arr, n, RRS);
let result = -1;
for (let i = 0; i < n; i++)
{
result = Math.max(result, Math.abs(LS[i] - RRS[n - 1 - i]));
}
return result;
}
function reverse(a)
{
let i, k, n = a.length;
let t;
for (i = 0; i < Math.floor(n / 2); i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
}
let arr=[2, 4, 8, 7, 7, 9, 3];
let n = arr.length;
document.write("Maximum diff : "
+ findMaxDiff(arr, n));
</script>
|
Time complexity: O(n)
Auxiliary Space: O(n).
Please Login to comment...