Maximum Difference

Given an integer array arr of integers, the task is to find the maximum absolute difference between the nearest left smaller element and the nearest right smaller element of every element in array arr. If for any component of the arr, the nearest smaller element doesn’t exist then consider it as 0.

Examples :

Input: arr = [2, 1, 8]
Output: 1
Explanation: left smaller array ls = [0, 0, 1], right smaller array rs = [1, 0, 0]. Maximum Diff of abs(ls[i] - rs[i]) = 1

Input: arr = [2, 4, 8, 7, 7, 9, 3]
Output: 4
Explanation: left smaller array 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]) = abs(7 - 3) = 4

Expected Time Complexity: O(n)
Expected Space Complexity: O(n)

Get Subhankar’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Constraints:
1 <= arr.size() <= 10⁶
1<= arr[i] <=10⁹

Solution:

//{ Driver Code Starts
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());

        while (t-- > 0) {
            String input = br.readLine();
            String[] inputs = input.split(" ");
            int[] arr = new int[inputs.length];

            for (int i = 0; i < inputs.length; i++) {
                arr[i] = Integer.parseInt(inputs[i]);
            }

            Solution ob = new Solution();
            System.out.println(ob.findMaxDiff(arr));
        }
    }
}

// } Driver Code Ends


class Solution {
    public int findMaxDiff(int[] arr) {
        // code here
        int n = arr.length;
        int maxDiff = 0;
        for(int i=0; i<n; i++){
            int leftSmaller =0;
            int rightSmaller =0;
            //Find left smaller.
            for(int j = i-1; j>=0; j--){
                if(arr[j] < arr[i]){
                    leftSmaller = arr[j];
                    break;
                }
            }
            //Find right smaller.
            for(int j= i+1; j<n; j++){
                if(arr[j] < arr[i]){
                    rightSmaller= arr[j];
                    break;
                }
            }
            maxDiff= Math.max(maxDiff, Math.abs(leftSmaller - rightSmaller));
        }
        return maxDiff;
    }
}

Tip or Donate