Sunday, October 6, 2019

Interview Questions 1: Maximum Distance to the Larger Element on the Right Side

https://www.geeksforgeeks.org/given-an-array-arr-find-the-maximum-j-i-such-that-arrj-arri/

Given an array arr[], find the maximum j – i such that i < j and arr[j] > arr[i]. If cannot find one valid pair, return -1.


Examples :
  Input: {34, 8, 10, 3, 2, 80, 30, 33, 1}
  Output: 6  (j = 7, i = 1)

  Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
  Output: 8 ( j = 8, i = 0)

  Input:  {1, 2, 3, 4, 5, 6}
  Output: 5  (j = 5, i = 0)

  Input:  {6, 5, 4, 3, 2, 1}
  Output: -1

Notes:

This question is trivial for a O(N^2) solution, so we will focus on the better solutions.

O(NlogN) solution 1:

In general, we need to find the small values on the left side, and large values on the right side. One way is that we can consider to maintain a decreasing array while scanning the original array from left to right. Why decreasing?

The reason is simply: once we meet with a new element which is larger than any of the previous elements on the left, it can be ruled out for the following processing, because there are smaller element which is on a more "left" position which can definitely give a larger distance.

Before we proceed further to the next element, we need to figure out what is the largest j - i at this moment, since arr[j] is larger than at least one of the previous element. As we mentioned earlier, all the previous elements has been sorted in a decreasing order, so we just use binary search to save time. After this, we can just ignore arr[j] (without putting it into the sorted array since it is not necessary), and move on to the next element.

If arr[j] is equal to the back element of the decreasing array, we just move on the the next, since it cannot form a valid pair with any of the previous element.

If arr[j] is smaller than the back element of the decreasing array, we just push it back.

See the code below:

//this functions is used to find the largest j - i with i < j and arr[i] < arr[j]. If cannot find, return -1.
int findLargestDistance(vector<int> nums) {
    int res = -1, len = nums.size();
    if(len<2) return res;
    vector<pair<int, int>> decrArr;
    for(int i=0; i<len; ++i) {
        if(decrArr.empty() || decrArr.back().first > nums[i]) {
     decrArr.push_back({nums[i], i});
 }
 else if(decrArr.back().first < nums[i]) {
     int id = findIndex(decrArr, nums[i]);
     res = max(res, i - id);
 }
    }
    return res;
}

//return the index of of the first elment smaller than target.
//vals is nonempty and sorted decreasingly, and vals.back().first < target.
int findIndex(vector<pair<int, int>>& vals, int target) {
    int left = 0, right = vals.size();
    while(left < right) {
        int mid = left + (right - left) / 2;
 if(vals[mid].first >= target) left = mid + 1;
 else right = mid;
    }
    return vals[left].second;
}

O(NlogN) solution 2:

There is another O(NlogN) solution, which can be found here.

https://www.geeksforgeeks.org/given-an-array-arr-find-the-maximum-j-i-such-that-arrj-arri/

The basic idea is to record the indexes of each element, by using a hash map. If we record this from left to right, we can store the indexes for each element in a monotonically increasing order, or sorted.

Then we can sort the elements, since the original index information has been stored in the has map <int, vector<int>> // <val, <index>>.

Then we can scan the sorted array from left to right. At each position, the most right position, or the largest j is the back element of the map[val] array.

All the smaller elements are on its left side now, and we want to figure out which one give the largest j - i, or we need to find the smallest i.

For each element, the smallest i is the first element of mp[val] array. So we can naturally use one variable to record the smallest index so far.

The most time consuming part is sort the original array, which is O(NlogN).

O(N) solution:

This question can be solved in O(N).

The basic idea is still the same as the above: we want to record the smallest elements from the left, and at the same time, we can also store the largest elements from the right. Since these are the possible candidates which can give the largest j - i.

We will use one array LSmall[i] to record the smallest element from the left to position i, and a second array RLarge[i] to record the largest element from right to position i.

Then we can scan the two arrays from left to right.

If LSmall[i] is larger than RLarge[j], the only choice for us is to increase i. (Why? since the current RLarge[j] is the largest of all the elements on the right side. If it is smaller than LSmall[i], then all the rest elements on the right side are smaller too. So we have to move i to the right, to see whether we can find even smaller RSmall[i].)

Otherwise, we can increase j for even larger j - i.

See the code below:

//this functions is used to find the largest j - i with i < j and arr[i] < arr[j]. If cannot find, return -1.
int findLargestDistance(vector<int> nums) {
    int res = -1, len = nums.size();
    if(len<2) return res;
    vector<int> LSmall(len, INT_MAX), RLarge(len, INT_MIN);
    LSmall[0] = nums[0];
    for(int i=1; i<len; ++i) LSmall[i] = min(nums[i], LSmall[i-1]);
    RLarge[len-1] = nums[len-1];
    for(int i=len-2; i>=0; --i) RLarge[i] = min(nums[i], RLarge[i+1]);
    int i = 0, j = 0;
    while(i<len && j<len) {
        if(LSmall[i] < RLarge[j]) {
            res = max(res, j - i);
            ++j;
        }
 else ++i;
    }
    return res;
}

No comments:

Post a Comment