This post is completed by 1 user

  • 0
 Add to List
Hard

526. Maximum Surpasser in the given array

The "surpasser" of an element in an array is defined as the number of elements that are to the "right" and bigger than itself. Write an algorithm to Find the maximum surpasser of the array.

Example:

Input array:
[2, 7, 5, 5, 2, 7, 0, 8, 1]
The "surpassers" are
[5, 1, 2, 2, 2, 1, 2, 0, 0]
Maximum Surpasser : 5

Approach: 

Brute Force:

Use nested loops and compare each array with all the elements to the right and check and count the surpassers. Return the maximum surpasser found. 

Time Complexity: O(N^2)

Better Solution: Divide and Conquer. 

Use the merge sort technique. (Please read Merge Sort if required). We will not sort the given array since sorting the given array will modify the given array and as per the problem description, the order of elements should not be changed. So instead we will take an additional array called arrSortedIndex and store the given array indexes and while doing merge sort, we will move the indexes in this array accordingly so that these indexes will represent the sorted order of the original array. For instance, if the given array is [6, 9, 2] then after merge sort the arrSortedIndex will be [2, 0, 1]. 

We will take two more additional arrays, arrSurpass, this array will store the surpasses for elements in the given array, and temp array that will be used for merge sort.

Steps:

  1. Given array is input[].
  2. Initialize arrSortedIndex[] and arrSurpass[] as the same size as input[].
  3. In arrSortedIndex[] fill 0, 1, 2, ,,,,size-1. (indexes)
  4. Divide  - Make recursive calls to the left half and right half of the array.
  5. Conquer - In tail recursion - do the merge
    1. To merge we start with both the arrays (left half and right half) at the beginning, pick the smaller element, take its index from arrSortedIndex[] and it into the temp[] and then compare the next elements and so on.
    2. Once iteration is completed, temp[] will have sorted indexes, copy that into arrSortedIndex[] for next merge iteration.
    3. Now the question is how do we calculate the surpasses. After each comparison We pick the smaller element either from the left half or right half. So when we pick from the left half that means all the remaining elements including the current element in the right half array will be surpasser for the picked element in the left half. So add that number to the respective index in arrSurpass[]. For example, left half is [2, 4, 7] and right half is [3, 5, 6], compare 2 and 3, pick smaller which is 2 so all the remaining elements including the current one [3, 5, 6] are surpasser for element 2. So add 3 in the count of element 2 surpasser.
  6. Once merge is completed, arrSurpass[] will have surpasses for all elements. Iterate the pick the maximum.

Walk Through

Output:

Given Array: [2, 7, 5, 5, 2, 7, 0, 8]
All surpasses: [5, 1, 2, 2, 2, 1, 1, 0]
Maximum Surpass: 5

Reference: https://www.careercup.com/question?id=5716707660267520

Related Problems: