Interview Question - Find the Max difference of Two elements in the Array in less than O(n^2) - the Lower element should precede the Greater element

During an interview, I've been asked the following Question:

You're given an array of integer numbers.

Find the maximum difference between two elements arr[j] - arr[i] for any sub array in the array, so that j>i.

For example:

array = {20,18,45,78,3,65,55}, max diff is 65 - 3 = 62.

array = {20,8,45,78,3,65,55}, max diff is 78 - 8 = 70.

Here is the solution I come up with:

private static int calculateProfit() {
    int[] arr = {20, 18, 45, 78, 3, 65, 55};
    int maxProfit = 0;
    for (int i = 0; i < arr.length; i++) {
        for (int j = arr.length - 1; j > 0; j--) {
            if (arr[i] < arr[j] && i < j) {
                maxProfit = Math.max(arr[j] - arr[i], maxProfit);
            }
        }
    }
    return maxProfit; // ans: (65 - 3) = 62 
}

The problem is that it runs in O(n^2). How it can be done with a better time complexity?

This problem can be solved in a linear time O(n), with a single run through the given array.

We need to declare only a couple of local variables, no data additional data structures required, space complexity is O(1).

These are the variables we need to track:

• min - the lowest value encountered so far;

• max - the highest encountered value;

• maxProfit - maximal profit that can be achieved at the moment.

While declaring these variables, we can either initialize min to Integer.MAX_VALUE and max to Integer.MIN_VALUE, or initialize both with the value of the first element in the array (this element should be present because the array needs to have at least two elements, otherwise the task has no sense).

And here is a couple of caveats:

• Since max element can not precede the min element, when a new min element is encountered (when the current element is less than min) the max element also needs to be reinitialized (with Integer.MIN_VALUE or with the value of the current element depending on the strategy you've chosen at the beginning).

• maxProfit should be checked against the difference between max and min each time when a new max has been encountered.

That's how it might be implemented:

public static int calculateProfit(int[] arr) {
    
    if (arr.length < 2) return -1; // incorrect input
    
    int max = arr[0];
    int min = arr[0];
    int maxProfit = 0;
    
    for (int i = 1; i < arr.length; i++) {
        int next = arr[i];
        if (next > max) {
            max = next;
            maxProfit = Math.max(max - min, maxProfit);
        } else if (next < min){
            min = next;
            max = next;
        }
    }
    return maxProfit;
}

main()

public static void main(String[] args) {
    System.out.println(calculateProfit(new int[]{1, 2, 3, 4, 10}));
    System.out.println(calculateProfit(new int[]{1, 10, -10, 4, 8}));
    System.out.println(calculateProfit(new int[]{5, 8, 12, 1, 9}));
    System.out.println(calculateProfit(new int[]{20, 18, 45, 78, 3, 65, 55}));
}

Output:

9     // [1, 2, 3, 4, 10]            ->    10 - 1 = 9
18    // [1, 10, -10, 4, 8]          -> 8 - (-10) = 18
8     // [5, 8, 12, 1, 9]            ->     9 - 1 = 8
62    // [20, 18, 45, 78, 3, 65, 55] ->    65 - 3 = 62