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

Question

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?

Answer 1

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

Answer 2

The maximum profit at an arbitrary index b where we must use b as the rightmost element of the pair is arr[b] - arr[a] where a is the index from the subarray before b with the minimum value (i.e. a ranges from 0 to b - 1). Clearly, this minimum value can be maintained while iterating forwards through the array. Then, we can just try all indexes as the rightmost index and take the maximum of all those differences. There is no need to keep track of the maximum array value encountered so far at all.

static int calculateProfit(int[] arr) {
    if (arr == null || arr.length < 2) return 0;
    int min = arr[0], maxProfit = Integer.MIN_VALUE;
    for (int i = 1; i < arr.length; i++) {
        maxProfit = Math.max(maxProfit, arr[i] - min);
        min = Math.min(min, arr[i]);
    }
    return maxProfit;
}

Answer 3

1. Start by finding the first possible solution. This is easy. Scan left-to-right. Track p for the index of the lowest value seen so far. As soon as you see a new non-descending value, set q to that index and goto step 2:

   [8, 5, 2, 2, 4, ...]
   [   D  D  -, I     ] # Look for first increasing value
   [      p     q     ] # arr[p] < arr[q] and p < q
   

2. Now continue looping over the array, looking for an improvement to the solution. The new wrinkle is tracking a u, the index of a value smaller than arr[p] but is unused because it is to the right of q:

   [8, 5, 2, 2, 4, 3, 1, ...]
   [      p     q     u     ]  # arr[u] < arr[p] but u > q
   

For each new value in the loop, update the solution. If the new i/u difference is bigger than the p/q solution, it becomes the new best:

   [8, 5, 2, 2, 4, 3, 1, 2, X, ...]
   [      p     q     u     i, ...]
          \...../                    Previous best solution
                      \-----/        Potential new best