Length of maximum subarray such that 1st element is greater than last element

Question

I have been given an array. I need to find the length of maximum subarray in which the first element is greater than the last element. For example 5 4 3 2 1. Length of max subarray is 5 since first element 5 is greater than last element 1. Another example, 5 10 4 7 9 8. Length is again 5 and array starts from 10 and goes till last element. I know the naive approach ie O(n²) but need a better approach.

Answer 1

Here is linear algorithm O(n):

Description of Algorithm

First collect all indices i for which the following is true:

       For any j > i : a_i < a_j

So they are sort of minima, in the sense that there are no lesser-or-equal values at the right of them.

Keep a reference to the left most of these, call that index j. That variable will serve as the end index (inclusive) of a range.

Now start from the left with index i, and as soon as a_i > a_j, go to the next "minimum" (so j increases) while this condition keeps holding (a_i > a_j). For the last j where this holds: this could be a solution: verify if this is the longest range so far found.

Whenever j < i, also take the next "mimimum"

Whenever there are no more minima, stop the algorithm.

Visual Representation

The idea is represented here in a graph-representation of the array values, where the red markers are the minima, and the green markers are possible candidates for where a solution sub array could start:

Code

Here is an implementation of that algorithm in JavaScript: you can enter array values, and the largest sub-array will be displayed as you type:

function longestSubArray(a) {
    // Preprocessing: collect all i, for which holds: 
    //     if j > i, then a[i] < a[j]
    var minima = [-1] // Add a special value first (see later)
    var last = Infinity;
    for (var i = a.length - 1; i >= 0; i--) {
        if (a[i] < last) {
            last = a[i];
            minima.push(i);
            // Optimisation: It is of no use to find more minima if 
            // this value is less than the first value in the aay
            if (last < a[0]) break; 
        }
    }
    // Get first value from minima. This will be the rightmost
    // value that is less than a[0], or if such does not exist,
    // the minimum value in the aay.
    var j = minima.pop();
    var maxSize = 1;
    var maxStart = 0;
    // Look for ranges that start at i:
    for (i = 0; i < a.length; i++) {
        // Check if range (i, j) fulfills the requirement
        while (j !== -1 && (a[i] > a[j] || j <= i) ) {
            // Check if range (i, j) is the largest so far
            if (j - i + 1 > maxSize) {
                maxSize = j - i + 1;
                maxStart = i;
            }
            // Take an end index that is more to the right,
            // but which will represent a higher value also:
            j = minima.pop(); // could be -1: which means "all done"
        }
        if (j == -1) break;
    }
    if (maxSize == 1) return []; // no solution
    return a.slice(maxStart, maxStart+maxSize);
}

// I/0 handling -- not relevant to the algorithm:
var input = document.querySelector('input');
var output = document.querySelector('span');

input.oninput = function () {
    // Translate text input to aay of integers
    var a = input.value.match(/-?\d+/g).map(Number);
    // Apply function
    var sub = longestSubArray(a);
    // Output result
    output.textContent = sub.join(' ');
}

Enter array: <input size="60"><br>
Longest sub-array: <span></span>

Proof of Linear Time Complexity

The algorithm has a linear time complexity:

• The loop for collecting the minima iterates at most n times
• The loop on i iterates at most n times
• The inner loop will in total iterate at most n times, even though it could iterate more than once per i, the array minima is being shortened on every iteration.

So: O(n).

Answer 2

You can try applying a caterpillar method which would be O(n):

The idea is to use two indices, one for the head and another for the tail as well as a maximum length variable. Then, you try to advance the head as long as the condition is valid: The minimum value in the subsequence from the head to the end of your array is less than the value of the tail.

If you can't advance the head, because the condition doesn't fulfill, then you advance the tail. Thus the resemblance to a caterpillar which advances his head and then its tail as it moves.

That minimum can be pre-calculated in a previous iteration over the array.

This is a possible implementation in python:

def subSeqLen(arr):
    head = 0
    tail = 0
    maxLength = 0
    minFromLast = [arr[-1]]*len(arr)
    for i in xrange(len(arr)-2, -1, -1):
        minFromLast[i] = min(minFromLast[i+1], arr[i])
    while head >= tail and head < len(arr):
        if arr[tail]>arr[head] and head-tail+1 > maxLength:
            maxLength = head-tail+1
        if head < len(arr)-1 and minFromLast[head+1]<=arr[tail]:
            head += 1
        else:
            tail += 1
            head = max(head, tail)
    return maxLength

Answer 3

Create another array of pairs such that the first element is same as your array and the second is indices of the element, so for array :

5 4 3 2 1

The new array will be like this

5,1 4,2 3,3 2,4 1,5

Now sort the array of pairs, so it will look like this :

1,5 2,4 3,3 4,2 5,1

Now build a Segment tree using indices of the sorted array of pairs.

Now iterate over the array and for each element find it's equivalent in the sorted array ( this can be done in O(1)), let suppose it's indices is j, know perform range query in the segment [1,i] ( since all elements in the segment [1,i] are lower then the current element because the array of pairs is sorted) to find the maximum indices value in log(n), and finally the answer is the maximum value among all segments lengths.

Complexity is O(nlog(n)).