Given an array arr[] of length N, the task is to find the longest subarray for each array element arr[i], which contains arr[i] as the maximum.
Examples:
Input: arr[] = {1, 2, 3, 0, 1}
Output: 1 2 5 1 2
Explanation:
The longest subarray having arr[0] as the largest is {1}
The longest subarray having arr[1] as the largest is {1, 2}
The longest subarray having arr[2] as the largest is {1, 2, 3, 0, 1}
The longest subarray having arr[3] as the largest is {0}
The longest subarray having arr[4 as the largest is {0, 1}Input: arr[] = {3, 3, 3, 1, 6, 2}
Output: 4 4 4 1 6 1
Approach: The idea is to use Two Pointer technique to solve the problem:
- Initialize two pointers, left and right. such that for every element arr[i], the left points to indices [i – 1, 0] to find elements smaller than or equal to arr[i] in a contiguous manner. The moment an element larger than arr[i] is found, the pointer stops.
- Similarly, right points to indices [i + 1, n – 1] to find elements smaller than or equal to arr[i] in a contiguous manner, and stops on finding any element larger than arr[i].
- Therefore, the largest contiguous subarray where arr[i] is largest is of length 1 + right – left.
- Repeat the above steps for every array element.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum length of// Subarrays for each element of the array// having it as the maximumvoid solve(int n, int arr[]){ int i, ans = 0; for (i = 0; i < n; i++) { // Initialize the bounds int left = max(i - 1, 0); int right = min(n - 1, i + 1); // Iterate to find greater // element on the left while (left >= 0) { // If greater element is found if (arr[left] > arr[i]) { left++; break; } // Decrement left pointer left--; } // If boundary is exceeded if (left < 0) left++; // Iterate to find greater // element on the right while (right < n) { // If greater element is found if (arr[right] > arr[i]) { right--; break; } // Increment right pointer right++; } // If boundary is exceeded if (right >= n) right--; // Length of longest subarray where // arr[i] is the largest ans = 1 + right - left; // Print the answer cout << ans << " "; }}// Driver Codeint main(){ int arr[] = { 4, 2, 1 }; int n = sizeof arr / sizeof arr[0]; solve(n, arr); return 0;} |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG{// Function to find the maximum length of// Subarrays for each element of the array// having it as the maximumstatic void solve(int n, int arr[]){ int i, ans = 0; for (i = 0; i < n; i++) { // Initialize the bounds int left = Math.max(i - 1, 0); int right = Math.min(n - 1, i + 1); // Iterate to find greater // element on the left while (left >= 0) { // If greater element is found if (arr[left] > arr[i]) { left++; break; } // Decrement left pointer left--; } // If boundary is exceeded if (left < 0) left++; // Iterate to find greater // element on the right while (right < n) { // If greater element is found if (arr[right] > arr[i]) { right--; break; } // Increment right pointer right++; } // If boundary is exceeded if (right >= n) right--; // Length of longest subarray where // arr[i] is the largest ans = 1 + right - left; // Print the answer System.out.print(ans + " "); }}// Driver Codepublic static void main(String[] args){ int arr[] = { 4, 2, 1 }; int n = arr.length; solve(n, arr);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to implement# the above approach# Function to find the maximum length of# Subarrays for each element of the array# having it as the maximumdef solve(n, arr): ans = 0 for i in range(n): # Initialise the bounds left = max(i - 1, 0) right = min(n - 1, i + 1) # Iterate to find greater # element on the left while left >= 0: # If greater element is found if arr[left] > arr[i]: left += 1 break # Decrement left pointer left -= 1 # If boundary is exceeded if left < 0: left += 1 # Iterate to find greater # element on the right while right < n: # If greater element is found if arr[right] > arr[i]: right -= 1 break # Increment right pointer right += 1 # if boundary is exceeded if right >= n: right -= 1 # Length of longest subarray where # arr[i] is the largest ans = 1 + right - left # Print the answer print(ans, end = " ") # Driver codearr = [ 4, 2, 1 ]n = len(arr)solve(n, arr) # This code is contributed by Stuti Pathak |
C#
// C# Program to implement// the above approachusing System;class GFG{// Function to find the maximum length of// Subarrays for each element of the array// having it as the maximumstatic void solve(int n, int []arr){ int i, ans = 0; for (i = 0; i < n; i++) { // Initialize the bounds int left = Math.Max(i - 1, 0); int right = Math.Min(n - 1, i + 1); // Iterate to find greater // element on the left while (left >= 0) { // If greater element is found if (arr[left] > arr[i]) { left++; break; } // Decrement left pointer left--; } // If boundary is exceeded if (left < 0) left++; // Iterate to find greater // element on the right while (right < n) { // If greater element is found if (arr[right] > arr[i]) { right--; break; } // Increment right pointer right++; } // If boundary is exceeded if (right >= n) right--; // Length of longest subarray where // arr[i] is the largest ans = 1 + right - left; // Print the answer Console.Write(ans + " "); }}// Driver Codepublic static void Main(String[] args){ int []arr = { 4, 2, 1 }; int n = arr.Length; solve(n, arr);}}// This code is contributed by Princi Singh |
Javascript
<script>// JavaScript program to implement// the above approach// Function to find the maximum length of// Subarrays for each element of the array// having it as the maximumfunction solve(n, arr){ let i, ans = 0; for (i = 0; i < n; i++) { // Initialize the bounds let left = Math.max(i - 1, 0); let right = Math.min(n - 1, i + 1); // Iterate to find greater // element on the left while (left >= 0) { // If greater element is found if (arr[left] > arr[i]) { left++; break; } // Decrement left pointer left--; } // If boundary is exceeded if (left < 0) left++; // Iterate to find greater // element on the right while (right < n) { // If greater element is found if (arr[right] > arr[i]) { right--; break; } // Increment right pointer right++; } // If boundary is exceeded if (right >= n) right--; // Length of longest subarray where // arr[i] is the largest ans = 1 + right - left; // Print the answer document.write(ans + " "); }}// Driver Code let arr = [ 4, 2, 1 ]; let n = arr.length; solve(n, arr); </script> |
Output:
3 2 1
Time Complexity: O(N2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
