Given an array A[] consisting of N integers and an integer K, the task is to maximize the length of the subarray having equal elements after performing at most K increments by 1 on array elements.
Note: Same array element can be incremented more than once.
Examples:
Input: A[] = {2, 4, 8, 5, 9, 6}, K = 6
Output: 3
Explanation:
Subarray [8, 5, 9] can be modified to [9, 9, 9].
Total number of increments required is 5 which is less than K(= 6).Input: A[] = {2, 2, 4}, K = 10
Output: 3
Naive Approach: The simplest approach to solve the problem is to generate all possible subarrays and for each subarray, check if all its elements can be made equal in at most K increments. Print the maximum length of such subarrays obtained.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Approach: The above approach can be optimized using the Sliding Window technique. Follow the steps below to solve the problem:
- Keep a track of the maximum element of the window.
- The total operations required for a particular window is obtained by the following equation:
Count of operations = (Length of the window calculated so far + 1) * (Maximum element from the window) – Sum of the window
- Now, check if the above-calculated value exceeds K or not. If so, then slide the starting pointer of the window towards the right, otherwise increment the length of the window calculated so far.
- Repeat the above steps to obtain the longest window satisfying the required condition.
Below is the implementation of the above approach:
C++14
// C++14 program for above approach#include <bits/stdc++.h>using namespace std;#define newl "\n"// Function to find the maximum length// of subarray of equal elements after// performing at most K incrementsint maxSubarray(int a[], int k, int n){ // Stores the size // of required subarray int answer = 0; // Starting point of a window int start = 0; // Stores the sum of window long int s = 0; deque<int> dq; // Iterate over array for(int i = 0; i < n; i++) { // Current element int x = a[i]; // Remove index of minimum elements // from deque which are less than // the current element while (!dq.empty() && a[dq.front()] <= x) dq.pop_front(); // Insert current index in deque dq.push_back(i); // Update current window sum s += x; // Calculate required operation to // make current window elements equal long int cost = (long int)a[dq.front()] * (answer + 1) - s; // If cost is less than k if (cost <= (long int)k) answer++; // Shift window start pointer towards // right and update current window sum else { if (dq.front() == start) dq.pop_front(); s -= a[start++]; } } // Return answer return answer;}// Driver Codeint main(){ int a[] = { 2, 2, 4 }; int k = 10; // Length of array int n = sizeof(a) / sizeof(a[0]); cout << (maxSubarray(a, k, n)); return 0;}// This code is contributed by jojo9911 |
Java
// Java Program for above approachimport java.util.*;class GFG { // Function to find the maximum length // of subarray of equal elements after // performing at most K increments static int maxSubarray(int[] a, int k) { // Length of array int n = a.length; // Stores the size // of required subarray int answer = 0; // Starting point of a window int start = 0; // Stores the sum of window long s = 0; Deque<Integer> dq = new LinkedList<>(); // Iterate over array for (int i = 0; i < n; i++) { // Current element int x = a[i]; // Remove index of minimum elements // from deque which are less than // the current element while (!dq.isEmpty() && a[dq.peek()] <= x) dq.poll(); // Insert current index in deque dq.add(i); // Update current window sum s += x; // Calculate required operation to // make current window elements equal long cost = (long)a[dq.peekFirst()] * (answer + 1) - s; // If cost is less than k if (cost <= (long)k) answer++; // Shift window start pointer towards // right and update current window sum else { if (dq.peekFirst() == start) dq.pollFirst(); s -= a[start++]; } } // Return answer return answer; } // Driver Code public static void main(String[] args) { int[] a = { 2, 2, 4 }; int k = 10; // Function call System.out.println(maxSubarray(a, k)); }} |
Python3
# Python3 program for above approachfrom collections import deque# Function to find the maximum length# of subarray of equal elements after# performing at most K incrementsdef maxSubarray(a, k): # Length of array n = len(a) # Stores the size # of required subarray answer = 0 # Starting po of a window start = 0 # Stores the sum of window s = 0 dq = deque() # Iterate over array for i in range(n): # Current element x = a[i] # Remove index of minimum elements # from deque which are less than # the current element while (len(dq) > 0 and a[dq[-1]] <= x): dq.popleft() # Insert current index in deque dq.append(i) # Update current window sum s += x # Calculate required operation to # make current window elements equal cost = a[dq[0]] * (answer + 1) - s # If cost is less than k if (cost <= k): answer += 1 # Shift window start pointer towards # right and update current window sum else: if (dq[0] == start): dq.popleft() s -= a[start] start += 1 # Return answer return answer# Driver Codeif __name__ == '__main__': a = [ 2, 2, 4 ] k = 10 # Function call print(maxSubarray(a, k))# This code is contributed by mohit kumar 29 |
C#
// C# Program for// the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the maximum length// of subarray of equal elements after// performing at most K incrementsstatic int maxSubarray(int[] a, int k){ // Length of array int n = a.Length; // Stores the size // of required subarray int answer = 0; // Starting point of a window int start = 0; // Stores the sum of window long s = 0; Queue<int> dq = new Queue<int>(); // Iterate over array for (int i = 0; i < n; i++) { // Current element int x = a[i]; // Remove index of minimum // elements from deque // which are less than // the current element while (dq.Count!=0 && a[dq.Peek()] <= x) dq.Dequeue(); // Insert current // index in deque dq.Enqueue(i); // Update current window sum s += x; // Calculate required operation to // make current window elements equal long cost = (long)a[dq.Peek()] * (answer + 1) - s; // If cost is less than k if (cost <= (long)k) answer++; // Shift window start pointer towards // right and update current window sum else { if (dq.Peek() == start) dq.Dequeue(); s -= a[start++]; } } // Return answer return answer;}// Driver Codepublic static void Main(String[] args){ int[] a = {2, 2, 4}; int k = 10; // Function call Console.WriteLine(maxSubarray(a, k));}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program for above approach// Function to find the maximum length// of subarray of equal elements after// performing at most K incrementsfunction maxSubarray(a, k, n){ // Stores the size // of required subarray var answer = 0; // Starting point of a window var start = 0; // Stores the sum of window var s = 0; var dq = []; // Iterate over array for(var i = 0; i < n; i++) { // Current element var x = a[i]; // Remove index of minimum elements // from deque which are less than // the current element while (dq.length!=0 && a[dq[0]] <= x) dq.shift(); // Insert current index in deque dq.push(i); // Update current window sum s += x; // Calculate required operation to // make current window elements equal var cost = a[dq[0]] * (answer + 1) - s; // If cost is less than k if (cost <= k) answer++; // Shift window start pointer towards // right and update current window sum else { if (dq[0] == start) dq.shift(); s -= a[start++]; } } // Return answer return answer;}// Driver Codevar a = [2, 2, 4];var k = 10;// Length of arrayvar n = a.length;document.write(maxSubarray(a, k, n));</script> |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
