DSA Sheet by Technical Mickey

MAX and MIN

Problem Description

Given an array of integers A, we need to calculate the sum of values for all possible subarrays, where each subarray’s value is defined as the difference between its maximum and minimum elements. The final sum should be computed modulo 10⁹ + 7.

Solution Approach Overview

The solution uses monotonic stacks to efficiently calculate how each element contributes to the final sum. Here’s a detailed breakdown:

Key Concepts

Each array element contributes to multiple subarrays, sometimes as the maximum value and sometimes as the minimum value.
For each element, we need to determine:
- How many subarrays have it as their maximum element
- How many subarrays have it as their minimum element

Implementation Strategy

Finding Boundary Elements We use monotonic stacks to find four critical indices for each element A[i]:

Nearest greater element to the left
Nearest greater element to the right
Nearest smaller element to the left
Nearest smaller element to the right

These boundaries help us calculate how many subarrays include A[i] as their maximum or minimum.

Contribution Calculation For each element A[i], we calculate:

max_contribution = (i - max_left[i]) × (max_right[i] - i) × A[i]

min_contribution = (i - min_left[i]) × (min_right[i] - i) × A[i]

The final contribution of each element is (max_contribution – min_contribution).

Example Walkthrough

Consider the array A = [4, 7, 3, 8]

Finding Boundaries

max_left  = [-1, -1,  1, -1]  // Index of nearest greater element on left

max_right = [ 1,  3,  3,  4]  // Index of nearest greater element on right

min_left  = [-1,  0, -1,  2]  // Index of nearest smaller element on left

min_right = [ 2,  2,  4,  4]  // Index of nearest smaller element on right

Calculating Element Contributions For A[0] = 4:

Maximum contribution: (0 – (-1)) × (1 – 0) × 4 = 4
Minimum contribution: (0 – (-1)) × (2 – 0) × 4 = 8
Net contribution: 4 – 8 = -4

Similar calculations are performed for each element, and the results are summed modulo 10⁹ + 7.

The final result for this example is 26.

				
					public class Solution {
    
    public int solve(int[] A) {
        int N = A.length;

        Stack<Integer> st = new Stack<>();
        int[] max_left = new int[N];

        for(int i = 0; i<N; i++){
            max_left[i] = -1;
            while(st.size() > 0 && A[st.peek()] <= A[i]){
                st.pop();
            }
            if(st.size() > 0){
                max_left[i] = st.peek();
            }
            st.push(i);
        }

        int[] max_right = new int[N];
         st = new Stack<>();
        for(int i = N-1; i>=0; i--){
            max_right[i] = N;
            while(st.size() > 0 && A[st.peek()] < A[i]){
                st.pop();
            }
            if(st.size() > 0){
                max_right[i] = st.peek();
            }
            st.push(i);
        }


        // min left and right 
        int[] min_left = new int[N];
         st = new Stack<>();
        for(int i = 0; i<N; i++){
            min_left[i] = -1;
            while(st.size() > 0 && A[st.peek()] >= A[i]){
                st.pop();
            }
            if(st.size() > 0){
                min_left[i] = st.peek();
            }
            st.push(i);
        }

        int[] min_right = new int[N];
           st = new Stack<>();
        for(int i = N-1; i>=0; i--){
            min_right[i] = N;
            while(st.size() > 0 && A[st.peek()] > A[i]){
                st.pop();
            }
            if(st.size() > 0){
                min_right[i] = st.peek();
            }
            st.push(i);
        }

        long ans = 0;
        long MOD = 1000000007;


        for(int i = 0; i<N; i++){
            long maxSum = (long)(max_right[i] - i) * (i - max_left[i]) * A[i];
            long minSum = (long)(min_right[i] - i) * (i - min_left[i]) * A[i];

            ans = (ans + ((maxSum - minSum) % MOD + MOD) % MOD) % MOD;
        }


        return (int)ans;
    }
}

Time and Space Complexity

Time Complexity: O(n), where n is the length of array A
Space Complexity: O(n) for storing the boundary arrays

This approach efficiently computes the result without having to generate all possible subarrays explicitly, which would be inefficient for large arrays.

Technical Mickey