Maximum count number of valley elements in a subarray of size K

0 0 7 minutes read

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. $\text{[math]}$ and $\text{[math]}$ .

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 K
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
    cout<<(final_point);
}
 
// Driver Code
int 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 K
def 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 Code
if __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 K
function 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 Code
 
let 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:

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 zambiatek!