Maximum Difference

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Find maximum difference arr[j] - arr[i] where j > i. Track running minimum from left.

Algorithm

1Scan left to right: maintain minSoFar. maxDiff = max(maxDiff, arr[j] - minSoFar).

Common Pitfalls

•Same as LC 121. O(n) single pass. Answer must be positive (j > i and arr[j] > arr[i]).

Maximum Difference.java

Java

// Approach: For max b-a with b>a and index_b>index_a: track minimum so far; max diff = max(arr[i] - minSoFar).
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    public int findMaxDiff(int[] arr) {
        // code here
        int n = arr.length, maxDiff = 0;
        int leftSmaller[] = new int[n];
        int rightSmaller[] = new int[n];

        Stack<Integer> stk = new Stack<>();
        stk.push(0);
        for (int i = 1; i < n; i++) {
            while (!stk.isEmpty() && arr[stk.peek()] >= arr[i])
                stk.pop();
            leftSmaller[i] = stk.isEmpty() ? 0 : arr[stk.peek()];
            stk.push(i);
        }
        stk.clear();
        stk.push(n - 1);
        for (int i = n - 2; i >= 0; i--) {
            while (!stk.isEmpty() && arr[stk.peek()] >= arr[i])
                stk.pop();
            rightSmaller[i] = stk.isEmpty() ? 0 : arr[stk.peek()];
            stk.push(i);
        }

        for (int i = 0; i < n; i++)
            maxDiff = Math.max(maxDiff, Math.abs(leftSmaller[i] - rightSmaller[i]));

        return maxDiff;
    }
}

Was this solution helpful?