Monday, December 19, 2011

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(n2). 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 ith number in an array. The minuend corresponding to the maximal diff[i] should be the maximum of all numbers on the left side of ith number in an array. We can get the maximal numbers on the left side of each ith number in an array while scanning the array once, and subtract the ith 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.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 
The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.

6 comments:

  1. if Max is left to the Min, get max of the following three sections
    1. Max - min(right to Max),
    2. MaxDiff of Max+1 to Min-1
    3. max(left to Min)- Min

    ReplyDelete
  2. Can this problem be solved using dynamic programming ?
    for each index i, find the largest number that lies before it. and it can be done by the following formula.
    f(i) = the largest number that lies before i
    f(i) = f(i-1) if a[i-1] < f(i-1)
    else f(i) = a[i-1] if a[i-1] >= f(i-1)

    Kindly reply.

    --
    Sandeep Singh

    ReplyDelete
  3. I write below program. Check it and give your feedback .

    public Pair findMaxPair(int inputArray[])
    {
    int index = 0 ,len =inputArray.length,firstElm=-1, secondElm=-1;
    int curElement=0, first=-1,second=-1;

    for(;index first)
    {
    first =curElement;
    }else if(curElement (firstElm-secondElm))
    {
    firstElm=first;
    secondElm = second;
    }
    }

    }

    return new Pair(firstElm,secondElm);
    }

    }

    class Pair
    {
    int first;
    int second;

    public Pair(int first, int second) {
    // TODO Auto-generated constructor stub
    this.first=first;
    this.second=second;
    }

    int difference ()
    {
    return first-second;
    }

    public String toString()
    {
    return "( "+first+", "+ second+"):diff:"+(first-second);
    }
    }

    ReplyDelete
  4. Time complexity is O(n). I am traversing array just once. Here i created Pair Class to return.

    ReplyDelete
  5. to Harry He
    May be I don't understand question but:
    1. If we talk about that the maximum difference must be negative, i.e. second number must be greater than first number. Then for input {2, 4, 3} MaxDiff_Solution3 output will be {4, 3} = 1 (if we do not take into account the sign), and it's ok, but then for input { 2, 4, 5 } it must output 0 (max negative difference not found), but its output is {4, 5} = -1.
    2. If we talk about that the maximum difference (does not matter positive or negative), then MaxDiff_Solution3 for input {2, 4, 3} and for { 2, 4, 5 }, must output {2, 4} = 2.
    I will be grateful for the answer.

    ReplyDelete