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.

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.

No. 27 - Area of Rectangles

Problem: Please implement a function which gets area of a set of rectangles, whose edges are parallel to X-axis or Y-axis.

Rectangles are defined as the following:

/* === Assumming: left <= right; top <= bottom === */

struct Rect

{

    int left;

    int right;

    int top;

    int bottom;

};

Analysis: The merged shape of overlapping rectangles is no longer a rectangle, and there is no equation to calculate the merged area directly. Therefore, we should split it into a set of rectangles.

A solution to split overlapping rectangles is based on x-values of all left and right edges. For example, there are three rectangles in Figure 1.

Figure 1: Three rectangles

We get all x-values of the three rectangles, which are X1, X2, …, X6 in Figure 2, and then split the merged shape into five rectangles based on x-values.

We should merge y-values of rectangles in ranges of x-value. For instance, both Rect1 and Rect2 fill into the x-value range between X2 and X3. Therefore, we should merge the y-value range of Rect1 and Rect2 to calculate the rectangle piece between X2 and X3.

Figure 2: Split rectangles into pieces based on x-values

Since ranges of x-values and y-values are necessary information to calculate area, we can define a class Range:

struct Range

{

    int less;

    int greater;

    Range(int l, int g)

    {

        less = (l < g) ? l : g;

        greater = (l + g) - less;

    }

    bool IsOverlapping(const Range& other)

    {

        return !(less > other.greater || other.less > greater);

    }

    void Merge(const Range& other)

    {

        if(IsOverlapping(other))

        {

            less = (less < other.less) ? less : other.less;

            greater = (greater > other.greater) ? greater : other.greater;

        }

    }

};

The overall algorithm to calculate the area of overlapping rectangles is: We firstly get all x-values of all rectangles, and then check whether every rectangle fills into each range formed by two neighboring x-values. If there are multiple rectangles fill into an x-value range, we merge their ranges of y-value before we calculate the area of a piece of merged rectangle.

The following function GetArea implements this algorithm. For optimization purpose, we sort all input rectangles according to their x-values of right edges, and sort a vector of all x-values.

int GetArea(vector<Rect>& rects)

{

    // sort rectangles according to x-value of right edges

    sort(rects.begin(), rects.end());

    vector<int> xes;

    GetAllX(rects, xes);

    sort(xes.begin(), xes.end());

    int area = 0;

    vector<int>::iterator iterX1 = xes.begin();

    vector<Rect>::const_iterator iterRect = rects.begin();

    for(; iterX1 != xes.end() && iterX1 != xes.end() - 1; ++ iterX1)

    {

        vector<int>::iterator iterX2 = iterX1 + 1;

        // filter out duplicated X-es

        if(*iterX1 < *iterX2)

        {

            Range rangeX(*iterX1, *iterX2);

            while(iterRect->right < *iterX1)

                ++ iterRect;

            list<Range> rangesOfY;

            GetRangesOfY(rects, iterRect, rangeX, rangesOfY);

            area += GetRectArea(rangeX, rangesOfY);

        }

    }

    return area;

}

bool operator < (const Rect& rect1, const Rect& rect2)

{

    return (rect1.right < rect2.right);

}

The following function GetAllX gets all x-values of all input rectangles.

void GetAllX(const vector<Rect>& rects, vector<int>& xes)

{

    vector<Rect>::const_iterator iter = rects.begin();

    for(; iter != rects.end(); ++ iter)

    {

        xes.push_back(iter->left);

        xes.push_back(iter->right);

    }

}

The function GetRangesOfY gets the ranges of y-values which fill into a range of x-value. It should be noticed that there might be multiple non-overlapping rectangles fill into an x-value range. For example, Rect1 and Rect2 in Figure do not overlap with each other. Therefore, we cannot merge their ranges of y-values. That is why it has a list of ranges of y-values for a range of x-value in the function GetRangesOfY.

Figure 3: Another example of three overlaping rectangles

void GetRangesOfY(const vector<Rect>& rects, vector<Rect>::const_iterator iterRect, const Range& rangeX, list<Range>& rangesOfY)

{

    for(; iterRect != rects.end(); ++ iterRect)

    {

        if(rangeX.less < iterRect->right && rangeX.greater > iterRect->left)

            InsertRangeY(rangesOfY, Range(iterRect->top, iterRect->bottom));

    }

}

The function InsertRangeY inserts a range of y-value into a list. When the range overlaps with another range existing in the list, we should remove the existing range and then insert a new merged range.

void InsertRangeY(list<Range>& rangesOfY, Range& rangeY)

{

    list<Range>::iterator iter = rangesOfY.begin();

    while(iter != rangesOfY.end())

    {

        if(rangeY.IsOverlapping(*iter))

        {

            rangeY.Merge(*iter);

            list<Range>::iterator iterCopy = iter;

            ++ iter;

            rangesOfY.erase(iterCopy);

        }

        else

            ++ iter;

    }

    rangesOfY.push_back(rangeY);

}

The function GetRectArea below gets the total area of all rectangle pieces in a range of x-value.

int GetRectArea(const Range& rangeX, const list<Range>& rangesOfY)

{

    int width = rangeX.greater - rangeX.less;

   

    list<Range>::const_iterator iter = rangesOfY.begin();

    int area = 0;

    for(; iter != rangesOfY.end(); ++ iter)

    {

        int height = iter->greater - iter->less;

        area += width * height;

    }

    return area;

}

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 printed books, please contact me (zhedahht@gmail.com) . Thanks.

No. 26 - Minimal Number of Coins for Change

Problem: Please implement a function which gets the minimal number of coins, whose value is v₁, v₂, …, v_n, to make change for an amount of money with value t. Any coin with value v_i may duplicate for any times to make change.

For example, the minimal number of coins to make change for 15 out of a set of coins with value 1, 3, 9, 10 is 3. We can choose two coins with value 3 and a coin with value 9. The number of coins for other choices should be greater than 3.

Analysis: Firstly let us define a function f(t) which is the minimal number of coins to make change for total value t. If there are n different coins, we have n choices to make change for value t: we can add a coin with value v₁ into a set of coins whose total value is t-v₁. The minimal number of coins to get value t-v₁ is f(t-v₁). Similarly, we can add a coin with value v₂ into a set of coins whose total value is t-v₂. The minimal number of coins to get value t-v₂ is f(t-v₂)…

Therefore, we divide a problem to calculate f(t) into n sub-problems: f(t-v₁), f(t-v₂), …, f(t-v_n). We can get a formal equation for f(t) as the following accordingly:

 

This equation can be implemented with recursion easily. However, the recursive solution will cause serious performance issues since there are overlaps when we divide this problem into n sub-problems. A better solution is to utilize iteration, and store the result of sub-problems into a table (as the Table 1).

In the Table 1, each column except the first one is to denote the number of coins to make change for a specific value. We can calculate the numbers in the Table 1 from left to right, to simulate the iterative process to get the result of f(15).

For instance, there are two numbers 4 and 2 under the column title “6”. We have two alternatives to make change for 6: the first one is to add a coin with value 1 to a set of coins whose total value is 5. Since the minimal number of coins to get value 5 is 3 (highlighted number under the column tile “5”), the number in the first cell under column title “6” is 4 (4=3+1). The second choice is to add a coin with value 3 to a set of coins whose total value is 3. Since the minimal number of coins to get value 3 is 1 (highlighted number under the column tile “3”), the number in the second cell under column title “6” is 2 (2=1+1). We highlight the number 2 in the column under tile 6 because 2 is less than 4.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	0	1	2	3	2	3	4	3	4	5	2	2	3	3	4	5
3	0	-	-	1	2	3	2	3	4	3	4	5	2	2	3	3
9	0	-	-	-	-	-	-	-	-	1	2	3	2	3	4	3
10	0	-	-	-	-	-	-	-	-	-	1	2	3	2	3	4

Table 1: The iterative process to calculate the minimal number of coins to make changes for 15.

Even though we have a 2-D matrix to show the iterative process, it only requires a 1-D array for coding, because it is only necessary to store the minimal number of coins to make change for each total value. The sample code is shown below:

int GetMinCount(int total, int* coins, int length)

{

    int* counts = new int[total + 1];

    counts[0] = 0;

   

    const int MAX = 0x7FFFFFFF;

    for(int i = 1; i <= total; ++ i)

    {

        int count = MAX;

        for(int j = 0; j < length; ++ j)

        {

            if(i - coins[j] >= 0 && count > counts[i - coins[j]])

                count = counts[i - coins[j]];

        }

        if(count < MAX)

            counts[i] = count + 1;

        else

            counts[i] = MAX;

    }

    int minCount = counts[total];

    delete[] counts;

    return minCount;

}

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.