Given an array arr[] of length N, the task is to find the length of the longest subarray with smaller elements on the immediate left for each element in the given array.
Example:
Input: arr[] = { 2, 1, 7, 6, 7 }
Output: 0 0 2 0 1
Explanation:
Index 0 (2): No substring is present to the immediate left having all smaller elements. So, length=0
Index 1 (1): No substring is present to the immediate left having all smaller elements. So, length=0
Index 2 (7): Substring {2, 1} is present to the immediate left having all smaller elements. So, length=2
Index 3 (6): No substring is present to the immediate left having all smaller elements. So, length=0
Index 4 (2): Substring {6} is present to the immediate left having all smaller elements. So, length=1Input: arr[] = { 4, 5, 7, 6, 10 }
Output: 0 1 2 0 4
Approach: For every element travel to its left until the element to the left is greater or the array ends to find the length of the longest subarray with smaller elements on the immediate left. Follow the below steps, to solve this problem:
- Traverse each element in array arr[].
- For each element run another loop in the left direction.
- Count all the elements smaller than the current element until a greater element comes or the array ends.
- Print the answer according to the above observation.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to find the length of the longest// subarray with smaller elements on the immediate// left for each element in the given arrayvoid subarrayLength(int* arr, int n){ for (int i = 0; i < n; i++) { int ans = 0; for (int j = i - 1; j >= 0; j--) { // If a greater element comes if (arr[i] <= arr[j]) { break; } // Else ans++; } cout << ans << " "; }}// Driver Codeint main(){ int n = 5; int arr[n] = { 1, 4, 2, 6, 3 }; subarrayLength(arr, n); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to find the length of the longest// subarray with smaller elements on the immediate// left for each element in the given arraystatic void subarrayLength(int arr[], int n) { for(int i = 0; i < n; i++) { int ans = 0; for(int j = i - 1; j >= 0; j--) { // If a greater element comes if (arr[i] <= arr[j]) { break; } // Else ans++; } System.out.print(ans + " "); }}// Driver Codepublic static void main(String args[]){ int n = 5; int arr[] = { 1, 4, 2, 6, 3 }; subarrayLength(arr, n);}}// This code is contributed by gfgking |
Python3
# Python program for the above approach# Function to find the length of the longest# subarray with smaller elements on the immediate# left for each element in the given arraydef subarrayLength(arr, n): for i in range(0, n): ans = 0 for j in range(i-1, -1, -1): # If a greater element comes if (arr[i] <= arr[j]): break # Else ans += 1 print(ans, end=" ")# Driver Codeif __name__ == "__main__": n = 5 arr = [1, 4, 2, 6, 3] subarrayLength(arr, n)# This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;class GFG{// Function to find the length of the longest// subarray with smaller elements on the immediate// left for each element in the given arraystatic void subarrayLength(int []arr, int n) { for(int i = 0; i < n; i++) { int ans = 0; for(int j = i - 1; j >= 0; j--) { // If a greater element comes if (arr[i] <= arr[j]) { break; } // Else ans++; } Console.Write(ans + " "); }}// Driver Codepublic static void Main(){ int n = 5; int []arr = { 1, 4, 2, 6, 3 }; subarrayLength(arr, n);}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the length of the longest // subarray with smaller elements on the immediate // left for each element in the given array function subarrayLength(arr, n) { for (let i = 0; i < n; i++) { let ans = 0; for (let j = i - 1; j >= 0; j--) { // If a greater element comes if (arr[i] <= arr[j]) { break; } // Else ans++; } document.write(ans + " "); } } // Driver Code let n = 5; let arr = [1, 4, 2, 6, 3]; subarrayLength(arr, n);// This code is contributed by Potta Lokesh </script> |
0 1 0 3 0
Time Complexity: O(N2)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
