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.

11 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
    Replies
    1. Hi Harry,

      Best thing I have read in a while on this No. 28 - A Pair with the Maximal Difference. There should be a standing ovation button. This is a great piece.

      We want to move to the Cloud for a new Project, and as there is quite a overwhelming choice here we wonder if what we have selected is the right choice or something else might be better.

      The AWS Serverless Application Model (AWS SAM) extends AWS CloudFormation to provide a simplified way of defining the AWS Training Amazon API Gateway APIs, AWS Lambda functions, and Amazon DynamoDB tables needed by your serverless application.


      Very useful post !everyone should learn and use it during their learning path.

      Kind Regards,
      Kevin

      Delete
  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
  6. Hi There,

    I am shocked, shocked, that there is such article exist!! But I really think you did a great job highlighting some of the key No. 28 - A Pair with the Maximal Difference in the entire space.

    We were experimenting with AWS and somehow linked existing accounts . If I click the button to say close account then I get a message stating:

    I look forward to see your next updates.

    Merci,
    Preethi.

    ReplyDelete
  7. Ni Hau,


    Seems like I won the lottery here….This is a treasure box of blogs and your folks are like leprechauns! Phenomenal read on No. 28 - A Pair with the Maximal Difference. AWS Training


    If AWS Certification says that I need to recertify by a specific date, is that date the final day that I can possibly take the recertification (or corresponding professional-level) exam?

    Once again thanks for your tutorial.

    Obrigado,
    Radhey

    ReplyDelete
  8. Merhaba,


    Great post. Well though out. This piece reminds me when I was starting out No. 28 - A Pair with the Maximal Difference
    after graduating from college.


    This is Erin from Amazon Web Services. I took a look at the support case you provided, I see that one of our agents was able to assist and resolve the case. AWS Training USA

    Please let us know if there is anything else we can help with!



    Awesome! Thanks for putting this all in one place. Very useful!


    Kind Regards,
    Irene Hynes

    ReplyDelete
  9. 808 Teens is the first of its kind teen chat room, owned and operated entirely by teens. The Teen Center provides a safe and friendly atmosphere for teenagers to congregate in one location. It’s a secure platform where teenagers from around the Teen Chat world can come together to chat, meet new people, make friends, and discuss a variety of topics.

    ReplyDelete