Given an array arr[], the task is to choose a subarray of size K which contains the maximum number of valley points with respect to adjacent elements.
An element arr[i] is known as a valley point, if both of its adjacent elements are greater than it, i.e. 
and .
Examples:
Input: arr[] = {5, 4, 6, 4, 5, 2, 3, 1}, K = 7 the
Output: 3
Explanation:
In subarray arr[0-6] = {5, 4, 6, 4, 5, 2, 3}
There are 3 Valley points in the subarray, which is maximum.
Input: arr[] = {2, 1, 4, 2, 3, 4, 1, 2}, K = 4
Output: 1
Explanation:
In subarray arr[0-3] = {2, 1, 4, 2}
There is only one valley point in the subarray, which is the maximum.
Approach: The idea is to use the sliding window technique to solve this problem.
Below is an illustration of the steps of the approach:
- Find the total count of valley points in the first sub-array of size K.
- Iterate for all the starting points of the possible subarrays, that is N-K points of the array, and apply the inclusion and exclusion principle to compute the number of valley points in the current window.
- At each step, update the final answer to compute the global maximum of every subarray.
Below is the implementation of the above approach:
C++
// C++ implementation to find the // maximum number of valley elements// in the subarrays of size K#include<bits/stdc++.h>using namespace std;// Function to find the valley elements// in the array which contains // in the subarrays of the size Kvoid minpoint(int arr[],int n, int k){ int min_point = 0; for (int i = 1; i < k-1 ; i++) { // Increment min_point // if element at index i // is smaller than element // at index i + 1 and i-1 if(arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) min_point += 1; } // final_point to maintain maximum // of min points of subarray int final_point = min_point; // Iterate over array // from kth element for(int i = k ; i < n; i++) { // Leftmost element of subarray if(arr[i - ( k - 1 )] < arr[i - ( k - 1 ) + 1]&& arr[i - ( k - 1 )] < arr[i - ( k - 1 ) - 1]) min_point -= 1; // Rightmost element of subarray if(arr[i - 1] < arr[i] && arr[i - 1] < arr[i - 2]) min_point += 1; // if new subarray have greater // number of min points than previous // subarray, then final_point is modified if(min_point > final_point) final_point = min_point; } // Max minimum points in // subarray of size k cout<<(final_point);}// Driver Codeint main(){ int arr[] = {2, 1, 4, 2, 3, 4, 1, 2}; int n = sizeof(arr)/sizeof(arr[0]); int k = 4; minpoint(arr, n, k); return 0; }// This code contributed by chitranayal |
Java
// Java implementation to find the // maximum number of valley elements // in the subarrays of size K class GFG{ // Function to find the valley elements // in the array which contains // in the subarrays of the size K static void minpoint(int arr[], int n, int k) { int min_point = 0; for(int i = 1; i < k - 1; i++) { // Increment min_point // if element at index i // is smaller than element // at index i + 1 and i-1 if(arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) min_point += 1; } // final_point to maintain maximum // of min points of subarray int final_point = min_point; // Iterate over array // from kth element for(int i = k ; i < n; i++) { // Leftmost element of subarray if(arr[i - ( k - 1 )] < arr[i - ( k - 1 ) + 1] && arr[i - ( k - 1 )] < arr[i - ( k - 1 ) - 1]) min_point -= 1; // Rightmost element of subarray if(arr[i - 1] < arr[i] && arr[i - 1] < arr[i - 2]) min_point += 1; // If new subarray have greater // number of min points than previous // subarray, then final_point is modified if(min_point > final_point) final_point = min_point; } // Max minimum points in // subarray of size k System.out.println(final_point); } // Driver Code public static void main (String[] args){ int arr[] = { 2, 1, 4, 2, 3, 4, 1, 2 }; int n = arr.length; int k = 4; minpoint(arr, n, k); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation to find the # maximum number of valley elements# in the subarrays of size K# Function to find the valley elements# in the array which contains # in the subarrays of the size Kdef minpoint(arr, n, k): min_point = 0 for i in range(1, k-1): # Increment min_point # if element at index i # is smaller than element # at index i + 1 and i-1 if(arr[i] < arr[i - 1] and arr[i] < arr[i + 1]): min_point += 1 # final_point to maintain maximum # of min points of subarray final_point = min_point # Iterate over array # from kth element for i in range(k, n): # Leftmost element of subarray if(arr[i - ( k - 1 )] < arr[i - ( k - 1 ) + 1] and\ arr[i - ( k - 1 )] < arr[i - ( k - 1 ) - 1]): min_point -= 1 # Rightmost element of subarray if(arr[i - 1] < arr[i] and arr[i - 1] < arr[i - 2]): min_point += 1 # if new subarray have greater # number of min points than previous # subarray, then final_point is modified if(min_point > final_point): final_point = min_point # Max minimum points in # subarray of size k print(final_point)# Driver Codeif __name__ == "__main__": arr = [2, 1, 4, 2, 3, 4, 1, 2] n = len(arr) k = 4 minpoint(arr, n, k) |
C#
// C# implementation to find the // maximum number of valley elements // in the subarrays of size K using System;class GFG{ // Function to find the valley elements // in the array which contains // in the subarrays of the size K static void minpoint(int []arr, int n, int k) { int min_point = 0; for(int i = 1; i < k - 1; i++) { // Increment min_point // if element at index i // is smaller than element // at index i + 1 and i-1 if(arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) min_point += 1; } // final_point to maintain maximum // of min points of subarray int final_point = min_point; // Iterate over array // from kth element for(int i = k ; i < n; i++) { // Leftmost element of subarray if(arr[i - ( k - 1 )] < arr[i - ( k - 1 ) + 1] && arr[i - ( k - 1 )] < arr[i - ( k - 1 ) - 1]) min_point -= 1; // Rightmost element of subarray if(arr[i - 1] < arr[i] && arr[i - 1] < arr[i - 2]) min_point += 1; // If new subarray have greater // number of min points than previous // subarray, then final_point is modified if(min_point > final_point) final_point = min_point; } // Max minimum points in // subarray of size k Console.WriteLine(final_point); } // Driver Code public static void Main (string[] args){ int []arr = { 2, 1, 4, 2, 3, 4, 1, 2 }; int n = arr.Length; int k = 4; minpoint(arr, n, k); } }// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript implementation to find the// maximum number of valley elements// in the subarrays of size K// Function to find the valley elements// in the array which contains// in the subarrays of the size Kfunction minpoint(arr, n, k) { let min_point = 0; for (let i = 1; i < k - 1; i++) { // Increment min_point // if element at index i // is smaller than element // at index i + 1 and i-1 if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) min_point += 1; } // final_point to maintain maximum // of min points of subarray let final_point = min_point; // Iterate over array // from kth element for (let i = k; i < n; i++) { // Leftmost element of subarray if (arr[i - (k - 1)] < arr[i - (k - 1) + 1] && arr[i - (k - 1)] < arr[i - (k - 1) - 1]) min_point -= 1; // Rightmost element of subarray if (arr[i - 1] < arr[i] && arr[i - 1] < arr[i - 2]) min_point += 1; // if new subarray have greater // number of min points than previous // subarray, then final_point is modified if (min_point > final_point) final_point = min_point; } // Max minimum points in // subarray of size k document.write(final_point);}// Driver Codelet arr = [2, 1, 4, 2, 3, 4, 1, 2];let n = arr.length;let k = 4;minpoint(arr, n, k);// This code contributed by _saurabh_jaiswal</script> |
Output:
1
Time Complexity: O(N)
Space Complexity: 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!
