Longest Subarray Length

Given an array of integers arr[]. Find the length of the longest subarray such that all the elements of the subarray are smaller than or equal to the length of the subarray.

Example:

Input: arr[] = [1, 2, 3]
Output: 3
Explanation: The longest subarray is the entire array itself [1, 2, 3], which has a length of 3. All elements in the subarray are less than or equal to 3.
Input: arr[] = [6, 4, 2, 5]
Output: 0
Explanation: There is no subarray where all elements are less than or equal to the length of the subarray. The longest subarray is empty, which has a length of 0.

Table of Content

[Naive Approach] By Checking All The Subarray - O(n^2) Time and O(1) Space
[Expected Approach] Using Stack - O(n) Time and O(n) Space

[Naive Approach] By Checking All The Subarray - O(n²) Time and O(1) Space

The idea is to check every possible subarray, compute its maximum element, and verify if the subarray length is greater than or equal to this maximum. If valid, update the answer with the maximum length found.

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestSubarray(vector<int>& arr) {
    int len = 0;
    int n = arr.size();

    // Check every subarray
    for (int i = 0; i < n; i++) {
        int maxi = arr[i];
        for (int j = i; j < n; j++) {
            
            // update max in subarray
            maxi = max(maxi, arr[j]); 
            if (j - i + 1 >= maxi) {
                len = max(len, j - i + 1);
            }
        }
    }
    
    return len;
}

int main() {
    vector<int> arr = {1, 2, 3};
    cout << longestSubarray(arr);
    return 0;
}

Java

public class GFG {
    static int longestSubarray(int[] arr) {
        int len = 0;
        int n = arr.length;

        // Check every subarray
        for (int i = 0; i < n; i++) {
            int maxi = arr[i];
            for (int j = i; j < n; j++) {
                
                // update max in subarray
                maxi = Math.max(maxi, arr[j]); 
                if (j - i + 1 >= maxi) {
                    len = Math.max(len, j - i + 1);
                }
            }
        }
        return len;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        System.out.println(longestSubarray(arr));
    }
}

Python

def longestSubarray(arr):
    lenAns = 0
    n = len(arr)

    # Check every subarray
    for i in range(n):
        maxi = arr[i]
        for j in range(i, n):
            
            # update max in subarray
            maxi = max(maxi, arr[j])  
            if (j - i + 1) >= maxi:
                lenAns = max(lenAns, j - i + 1)

    return lenAns
    
if __name__ == "__main__":
    arr = [1, 2, 3]
    print(longestSubarray(arr))

using System;

class GFG {
    static int longestSubarray(int[] arr) {
        int len = 0;
        int n = arr.Length;

        // Check every subarray
        for (int i = 0; i < n; i++) {
            int maxi = arr[i];
            for (int j = i; j < n; j++) {
                
                 // update max in subarray
                maxi = Math.Max(maxi, arr[j]);
                if (j - i + 1 >= maxi) {
                    len = Math.Max(len, j - i + 1);
                }
            }
        }
        return len;
    }

    static void Main() {
        int[] arr = {1, 2, 3};
        Console.WriteLine(longestSubarray(arr));
    }
}

JavaScript

function longestSubarray(arr) {
    let len = 0;
    let n = arr.length;

    // Check every subarray
    for (let i = 0; i < n; i++) {
        let maxi = arr[i];
        for (let j = i; j < n; j++) {
            
            // update max in subarray
            maxi = Math.max(maxi, arr[j]); 
            if ((j - i + 1) >= maxi) {
                len = Math.max(len, j - i + 1);
            }
        }
    }
    return len;
}

// Driver Code
let arr = [1, 2, 3];
console.log(longestSubarray(arr));

Output

[Expected Approach] Using Stack - O(n) Time and O(n) Space

Intuition

If we are given an array, along with its size and maximum element, we can directly validate whether the array is valid or not (length of array >= maximum element).

What if we treat every element as the maximum element and then try to find the range where that element can actually remain the maximum? So the problem reduces to: For every element arr[i], find the largest window [L..R] where arr[i] is the maximum.

How to find that window?

To find out the window for which an element arr[i] is the maximum:

On the left side, keep moving until you find an element greater than arr[i]. The window cannot extend beyond this point, because then arr[i] would no longer be the maximum.
On the right side, do the same stop as soon as you encounter an element greater than arr[i].

So, the element arr[i] is the maximum in the subarray that starts just after the greater element on the left and ends just before the greater element on the right (windowLength = (NGE[i] - PGE[i] - 1)).

Check validity

If windowLength >= arr[i], then it forms a valid subarray and keep track of the maximum such length.

C++

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int longestSubarray(vector<int>& arr) {
    int n = arr.size();

    vector<int> nextGreater(n, n);
    vector<int> prevGreater(n, -1);

    stack<int> st;

    // Find Next Greater Element to the Right
    for (int i = 0; i < n; i++) {
        while (!st.empty() && arr[st.top()] < arr[i]) {
            nextGreater[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }

    // Clear stack for next pass
    while (!st.empty()) st.pop();

    // Find Next Greater Element to the Left
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && arr[st.top()] < arr[i]) {
            prevGreater[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }

    // Find the maximum valid subarray length
    int maxLength = 0;
    for (int i = 0; i < n; i++) {
        int windowSize = nextGreater[i] - prevGreater[i] - 1;
        if (windowSize >= arr[i]) {
            maxLength = max(maxLength, windowSize);
        }
    }

    return maxLength;
}

int main() {
    vector<int> arr = {1, 2, 3};
    cout << longestSubarray(arr);
    return 0;
}