20. Longest Subarray Length
✅ GFG solution to the Longest Subarray Length problem: find maximum length subarray where all elements are ≤ subarray length using monotonic stack technique. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
You are given an array of integers arr[]. Your task is to 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.
A subarray is a contiguous sequence of elements within an array. The goal is to find the maximum possible length where every element in the subarray satisfies: element ≤ subarray_length.
📘 Examples
Example 1
Input: arr[] = [1, 2, 3]
Output: 3
Explanation: The longest subarray is the entire array itself, which has a length of 3.
All elements in the subarray are less than or equal to 3.Example 2
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.🔒 Constraints
$1 \le \text{arr.size()} \le 10^5$
$1 \le \text{arr}[i] \le 10^9$
✅ My Approach
The optimal approach uses Monotonic Stack technique to efficiently find the boundaries where each element can be the maximum in a valid subarray:
Monotonic Stack Approach
Precompute Boundaries:
For each index
i, find the nearest smaller element on the left (l[i]) and right (r[i]).Use monotonic stack to compute these boundaries in linear time.
Calculate Subarray Length:
For each element at index
i, the maximum subarray wherearr[i]is the largest element has lengthr[i] - l[i] - 1.
Validate Condition:
Check if the subarray length is greater than or equal to
arr[i].If yes, this subarray satisfies our condition.
Track Maximum:
Keep track of the maximum valid subarray length found.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n), where n is the size of the array. Each element is pushed and popped from the stack at most once during the two passes.
Expected Auxiliary Space Complexity: O(n), for storing the left and right boundary arrays and the stack space.
🧑💻 Code (C++)
class Solution {
public:
int longestSubarray(vector<int>& a) {
int n = a.size(), res = 0;
vector<int> l(n, -1), r(n, n);
stack<int> s;
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && a[s.top()] <= a[i]) s.pop();
if (!s.empty()) r[i] = s.top();
s.push(i);
}
while (!s.empty()) s.pop();
for (int i = 0; i < n; i++) {
while (!s.empty() && a[s.top()] <= a[i]) s.pop();
if (!s.empty()) l[i] = s.top();
s.push(i);
int len = r[i] - l[i] - 1;
if (len >= a[i]) res = max(res, len);
}
return res;
}
};☕ Code (Java)
class Solution {
public static int longestSubarray(int[] a) {
int n = a.length, res = 0;
int[] l = new int[n], r = new int[n];
Arrays.fill(l, -1);
Arrays.fill(r, n);
Stack<Integer> s = new Stack<>();
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && a[s.peek()] <= a[i]) s.pop();
if (!s.empty()) r[i] = s.peek();
s.push(i);
}
s.clear();
for (int i = 0; i < n; i++) {
while (!s.empty() && a[s.peek()] <= a[i]) s.pop();
if (!s.empty()) l[i] = s.peek();
s.push(i);
int len = r[i] - l[i] - 1;
if (len >= a[i]) res = Math.max(res, len);
}
return res;
}
}🐍 Code (Python)
class Solution:
def longestSubarray(self, a):
n, res = len(a), 0
l, r, s = [-1] * n, [n] * n, []
for i in range(n - 1, -1, -1):
while s and a[s[-1]] <= a[i]: s.pop()
if s: r[i] = s[-1]
s.append(i)
s.clear()
for i in range(n):
while s and a[s[-1]] <= a[i]: s.pop()
if s: l[i] = s[-1]
s.append(i)
length = r[i] - l[i] - 1
if length >= a[i]: res = max(res, length)
return res🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated