Longest Subarray with first element greater than or equal to Last element - Coding

Given an array arr[0..n-1] of n integers, find the maximum length subarray such that its first element is greater than or equal to the last element of the subarray.

Examples:

Input : arr[] = {-5, -1, 7, 5, 1, -2}
Output : 5
Explanation : Subarray {-1, 7, 5, 1, -2} forms maximum 
length subarray with its first element greater than last.

Input : arr[] = {1, 5, 7}
Output : 1

Naive approach is to use two nested loops for every possible starting and ending element of the subarray and if it satisfies the condition then update the answer accordingly.
Time Complexity : O(n^2)

A Better approach is to use Binary search. In this approach for each element in the array we maximise the length of the subarray ending at that element. Then we take the maximum of the all the lengths.

We will take another array which is used as our search space for choosing the starting element of. We will keep adding element in it as we traverse the array if the element is greater than all the previous elements present in the search space.

The key observation here is that we will add an element to our search space only when it is greater than all the element of the search space because if the element is lower any other element then it can never be chosen as the first element of the maximum length subarray since we would have a better choice.

Since the search space is always sorted in increasing order, we just need compare the current element of the array with last element of the search space and if and only if its greater than the last element we add it to the search space otherwise not.

Below is the implementation of the above approach

C++

<?php
// PHP program to find length 
// of the longest array with 
// first element smaller than 
// or equal to last element.
 
 
// Search function for searching 
// the first element of the
// subarray which is greater or 
// equal to the last element(num)
function binarySearch($searchSpace, 
                      $s, $e, $num)
{
    $ans = 0;
    while ($s <= $e) 
    {
        $mid = ($s + $e) / 2;
 
        if ($searchSpace[$mid] >= $num) 
        {
            $ans = $mid;
            $e = $mid - 1;
        }
        else
        {
            $s = $mid + 1;
        }
    }
 
    return $ans;
}
 
// Returns length of the longest 
// array with first element smaller
// than the last element.
function longestSubArr(&$arr, $n)
{
    // Search space for the
    // potential first elements.
 
    // It will store the Indexes 
    // of the elements of search 
    // space in the original array.
     
    // Initially the search
    // space is empty.
    $j = 0;
    $ans = 0;
    for ($i = 0; $i < $n; ++$i) 
    {
 
        // We will add an ith element 
        // in the search space if the 
        // search space is empty or if 
        // the ith element is greater 
        // than the last element of the
        // search space.
        if ($j == 0 or
            $searchSpace[$j - 1] < $arr[$i]) 
        {
            $searchSpace[$j] = $arr[$i];
            $index[$j] = $i;
            $j++;
        }
     
 
        // we will search for the index 
        // first element in the search 
        // space and we will use it find 
        // the index of it in the original
        // array.
        $idx = binarySearch($searchSpace, 0, 
                            $j - 1, $arr[$i]);
 
        // Update the answer if the length 
        // of the subarray is greater than 
        // the previously calculated lengths.
        $ans = max($ans, $i - $index[$idx] + 1);
    }
    return $ans;
}
 
// Driver code
$arr = array(-5, -1, 7, 5, 1, -2);
$n = sizeof($arr);
echo (longestSubArr($arr, $n)) ; 
 
// This code is contributed
// by Shivi_Aggarwal
?>

Javascript

<script>
 
// Javascript program to find length 
// of the longest array with 
// first element smaller than 
// or equal to last element.
 
// Search function for searching 
// the first element of the
// subarray which is greater or 
// equal to the last element(num)
function binarySearch(searchSpace, s, e, num)
{
    let ans = 0;
     
    while (s <= e) 
    {
        let mid = Math.floor((s + e) / 2);
       
        if (searchSpace[mid] >= num) 
        {
            ans = mid;
            e = mid - 1;
        }
        else
            s = mid + 1;
    }
    return ans;
}
 
// Returns length of the longest 
// array with first element smaller
// than the last element.
function longestSubArr(arr, n)
{
     
    // Search space for the 
    // potential first elements.
    let searchSpace = new Array(n);
       
    // It will store the Indexes 
    // of the elements of search
    // space in the original array.
    let index = new Array(n);
       
    // Initially the search
    // space is empty.
    let j = 0;
    let ans = 0;
       
    for(let i = 0; i < n; ++i)
    {
         
        // We will add an ith element 
        // in the search space if the 
        // search space is empty or if 
        // the ith element is greater 
        // than the last element of 
        // the search space.
        if (j == 0 || searchSpace[j - 1] < arr[i]) 
        {
            searchSpace[j] = arr[i];
            index[j] = i;
            j++;
        }
       
        // We will search for the index 
        // first element in the search 
        // space and we will use it find
        // the index of it in the original array.
        let idx = binarySearch(searchSpace, 0,
                               j - 1, arr[i]);
       
        // Update the answer if the 
        // length of the subarray is
        // greater than the previously 
        // calculated lengths.
        ans = Math.max(ans, i - index[idx] + 1);
    }
    return ans;    
}
 
// Driver code
let arr = [ -5, -1, 7, 5, 1, -2 ];
let n = arr.length;
 
document.write(longestSubArr(arr, n));
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Output

Time Complexity : (N * log N)

Binary search function takes Log N time and the it will be called N times.

Reffered: https://www.geeksforgeeks.org

Searching

Related
Largest subarray having sum greater than k
Find the only missing number in a sorted array
Ways to choose three points with distance between the most distant points <= L
Maximum adjacent difference in an array in its sorted form
Check if a string is suffix of another

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	13