Find maximum difference between nearest left and right smaller elements

Difficulty Level Easy
Frequently asked in Fourkites
Array StackViews 1422

Problem Statement

Given an array a[ ] of size n. The problem “Find maximum difference between nearest left and right smaller elements” asks us to create a function. Such that it creates two arrays left[ ] and right[ ] representing nearest smaller element to the left and nearest smaller element to the right respectively. Then find the maximum of the absolute difference of arrays left [i] – right [i].

Find maximum difference between nearest left and right smaller elements

Example

a[ ] = {2, 1, 8}
1
a[ ] = {2, 4, 8, 7, 7, 9, 3}
4

Algorithm to Find maximum difference between nearest left and right smaller elements

  1. Initialize an array a[ ] of size n.
  2. Create a function to find the smaller elements for array left and right which accept an array, it’s size, and an array to store smaller elements as it’s parameters.
  3. Create a stack data structure of integer type.
  4. Traverse through the array a[ ]. While the stack is not empty and the element at the top of the stack is greater than or equal to the element in array a[ ] at current index, pop the element at the tp of the stack.
  5. Check if the stack is not empty, update the value at current index in array for smaller elements as the element at the top of the stack. Else update the value at current index in array for smaller elements as 0.
  6. Push / insert the value at current index in array a[ ] in the stack.
  7. Similarly, create another function to find the maximum of difference which accepts an array and it’s size as it’s parameter.
  8. Create an array left[ ] of size n to store the nearest smaller element to the left. Call the function for smaller elements with the given array, it’s size, and the left array as it’s parameter.
  9. Similarly, create an array right[ ] of size n to store the nearest smaller element to the right. Reverse the original array a[ ] and call the function for smaller elements with the given array, it’s size, and the right array as it’s parameter.
  10. Traverse from 0 to n-1 and find the maximum of absolute difference of left and right array.
  11. Print the result.

Code

C++ Program to find maximum difference between nearest left and right smaller elements

#include<bits/stdc++.h> 
using namespace std; 
  
void SmallerElement(int a[], int n, int SE[]){ 
    stack<int>S; 
  
    for(int i=0; i<n; i++){ 
        
        while(!S.empty() && S.top() >= a[i]){ 
            S.pop(); 
        }
  
        if(!S.empty()){ 
            SE[i] = S.top();
        }
  
        else{
            SE[i] = 0;
        }
  
        S.push(a[i]); 
    } 
} 
  
int findMaxDiff(int a[], int n){ 
    int left[n]; 
  
    SmallerElement(a, n, left); 
  
    int right[n]; 
    
    reverse(a, a + n); 
    SmallerElement(a, n, right); 
  
    int result = -1; 
    for(int i=0 ; i< n ; i++){ 
        result = max(result, abs(left[i] - right[n-1-i]));
    }
   
    return result; 
} 
  
int main(){ 
    int a[] = {2, 4, 8, 7, 7, 9, 3}; 
    int n = sizeof(a)/sizeof(a[0]);
    
    cout << findMaxDiff(a, n) << endl; 
    
    return 0; 
}
4

Java Program to find maximum difference between nearest left and right smaller elements

import java.util.*; 
  
class MaximumOfDifference{ 
  
    static void SmallerElement(int a[], int n, int SE[]){ 
        
        Stack<Integer> S = new Stack<>(); 
  
        for(int i = 0; i < n; i++){ 
            
            while(!S.empty() && S.peek() >= a[i]){ 
                S.pop(); 
            } 
  
            if(!S.empty()){ 
                SE[i] = S.peek(); 
            }  
            
            else{ 
                SE[i] = 0; 
            } 
  
            S.push(a[i]); 
        } 
    } 
  
    static int findMaxDiff(int a[], int n){ 
        int[] left = new int[n]; 
  
        SmallerElement(a, n, left); 
  
        int[] right = new int[n]; 
        
        reverse(a); 
        SmallerElement(a, n, right); 
  
        int result = -1; 
        for(int i = 0; i < n; i++){ 
            result = Math.max(result, Math.abs(left[i] - right[n - 1 - i])); 
        } 
 
        return result; 
    } 
  
    static void reverse(int a[]){ 
        int i, k, n = a.length, 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 a[] = {2, 4, 8, 7, 7, 9, 3}; 
        int n = a.length; 
        
        System.out.println(findMaxDiff(a, n)); 
    } 
}
4

Complexity Analysis

Time Complexity

O(n) where n is the number of integers in the given array a[ ]. Because we have just traversed the array thus the time complexity is linear.

Space Complexity

O(n) because we used space for n elements. We have created two arrays left and right. Thus the space complexity is also linear.

Translate »