Discussing Coding Interview Questions from Google

No. 28 - A Pair with the Maximal Difference

Problem: A pair contains two numbers, and its second number is on the right side of the first one in an array. The difference of a pair is the minus result while subtracting the second number from the first one. Please implement a function which gets the maximal difference of all pairs in an array. For example, the maximal difference in the array {2, 4, 1, 16, 7, 5, 11, 9} is 11, which is the minus result of pair (16, 5).

Analysis: A naïve solution with brute force is quite straightforward: We can get the result for each number minus every number on its right side, and then get the maximal difference after comparisons. Since O(n) minus operations are required for each number in an array with n numbers, the overall time complexity is O(n²). Brutal force solution usually is not the best solution. Let us try to reduce the times of minus operations.

Solution 1: via divide and conquer

We divide an array into two sub-arrays with same size. The maximal difference of all pairs occurs in one of the three following situations: (1) two numbers of a pair are both in the first sub-array; (2) two numbers of a pair are both in the second sub-array; (3) the minuend is in the greatest number in the first sub-array, and the subtrahend is the least number in the second sub-array.  

It is not a difficult to get the maximal number in the first sub-array and the minimal number in the second sub-array. How about to get the maximal difference of all pairs in two sub-arrays? They are actually sub-problems of the original problem, and we can solve them via recursion. The following are the sample code of this solution:

int MaxDiff_Solution1(int numbers[], unsigned length)

{

    if(numbers == NULL || length < 2)

        return 0;

    int max, min;

    return MaxDiffCore(numbers, numbers + length - 1, &max, &min);

}

int MaxDiffCore(int* start, int* end, int* max, int* min)

{

    if(end == start)

    {

        *max = *min = *start;

        return 0x80000000;

    }

    int* middle = start + (end - start) / 2;

    int maxLeft, minLeft;

    int leftDiff = MaxDiffCore(start, middle, &maxLeft, &minLeft);

    int maxRight, minRight;

    int rightDiff = MaxDiffCore(middle + 1, end, &maxRight, &minRight);

    int crossDiff = maxLeft - minRight;

    *max = (maxLeft > maxRight) ? maxLeft : maxRight;

    *min = (minLeft < minRight) ? minLeft : minRight;

    int maxDiff = (leftDiff > rightDiff) ? leftDiff : rightDiff;

    maxDiff = (maxDiff > crossDiff) ? maxDiff : crossDiff;

    return maxDiff;

}

In the function MaxDiffCore, we get the maximal difference of pairs in the first sub-array (leftDiff), and then get the maximal difference of pairs in the second sub-array (rightDiff). We continue to calculate the difference between the maximum in the first sub-array and the minimal number in the second sub-array (crossDiff). The greatest value of the three differences is the maximal difference of the whole array.

We can get the minimal and maximal numbers, as well as their difference in O(1) time, based on the result of two sub-arrays, so the time complexity of the recursive solution is T(n)=2(n/2)+O(1). We can demonstrate its time complexity is O(n).

Solution 2: get the maximum numbers while scanning

Let us define diff[i] for the difference of a pair whose subtrahend is the i^th number in an array. The minuend corresponding to the maximal diff[i] should be the maximum of all numbers on the left side of i^th number in an array. We can get the maximal numbers on the left side of each i^th number in an array while scanning the array once, and subtract the i^th number for them. The following code is based on this solution:

int MaxDiff_Solution3(int numbers[], unsigned length)

{

    if(numbers == NULL || length < 2)

        return 0;

    int max = numbers[0];

    int maxDiff =  max - numbers[1];

    for(int i = 2; i < length; ++i)

    {

        if(numbers[i - 1] > max)

            max = numbers[i - 1];

        int currentDiff = max - numbers[i];

        if(currentDiff > maxDiff)

            maxDiff = currentDiff;

    }

    return maxDiff;

}

It is obviously that its time complexity is O(n) since it is only necessary to scan an array with length n once. It is more efficient than the first solution on memory requirement, which requires O(logn) memory for call stack for the recursion.