Longest Equal Subarray with at Most K Increments

Given an array arr[] and an integer k, find the maximum length subarray whose elements can be made equal using at most k increments. An element can be incremented multiple times, but the total number of increments must not exceed k.

Examples:

Input: arr[] = [2, 4, 8, 5, 9, 6], k = 6
Output: 3
Explanation: Subarray [8, 5, 9] can be changed to [9, 9, 9] with 5 increments, which is within the limit k = 6.
Input: arr[] = [2, 2, 4], k = 10
Output: 3
Explanation: Entire array can be made [4, 4, 4] using 4 increments, well within the allowed k = 10.
Input: arr[] = [1, 2, 3, 4], k = 2
Output: 2
Explanation: Subarrays [1, 2], [2, 3], and [3, 4] can each be converted into equal elements using 1 increment.

Table of Content

[Naive Approach] Generate and Check All Subarrays - O(n^3) Time and O(1) Space
[Expected Approach] Sliding Window with Deque - O(n) Time and O(n) Space

[Naive Approach] Generate and Check All Subarrays - O(n^3) Time and O(1) Space

Generate all possible subarrays and make all elements equal by increasing smaller values. For each subarray, find its maximum element as the target and calculate the total increments required. If the required increments do not exceed k, update the maximum length.

Initialize maxLength as 1 to store the answer.
Use two loops to generate all subarrays [i...j].
For each subarray, find its max element as the target.
Compute total increments needed to match this target.
If increments ≤ k, update maxLength.
Return the final max length.

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Calculate increments to make subarray equal to target
int getIncrements(vector<int>& arr, int left, int right, int target) {
    int total = 0;
    for (int i = left; i <= right; i++) {
        if (arr[i] < target) {
            total += target - arr[i];
        }
    }
    return total;
}

// Find maximum element in subarray
int getMax(vector<int>& arr, int left, int right) {
    int maxValue = arr[left];
    for (int i = left + 1; i <= right; i++) {
        maxValue = max(maxValue, arr[i]);
    }
    return maxValue;
}

// Return maximum valid subarray length
int maxEqualSubarrayLength(vector<int>& arr, int k) {
    int n = arr.size();
    int maxLength = 1;

    // Try all possible subarrays
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {

            // Find max element in current subarray manually
            int maxElem = getMax(arr, i, j);
            
            // Calculate how many increments are needed
            int increments = getIncrements(arr, i, j, maxElem);

            // Check if it's within allowed limit
            if (increments <= k) {
                maxLength = max(maxLength, j - i + 1);
            }
        }
    }

    return maxLength;
}

int main() {
    vector<int> arr = {2, 4, 8, 5, 9, 6};
    int k = 6;

    cout << maxEqualSubarrayLength(arr, k) << endl;
    return 0;
}

Java

import java.util.*;

class GfG {

    // Calculate increments to make subarray equal to target
    static int getIncrements(int[] arr, int left, int right, int target) {
        int total = 0;
        for (int i = left; i <= right; i++) {
            if (arr[i] < target) {
                total += target - arr[i];
            }
        }
        return total;
    }

    // Find maximum element in subarray
    static int getMax(int[] arr, int left, int right) {
        int maxValue = arr[left];
        for (int i = left + 1; i <= right; i++) {
            maxValue = Math.max(maxValue, arr[i]);
        }
        return maxValue;
    }

    // Return maximum valid subarray length
    static int maxEqualSubarrayLength(int[] arr, int k) {
        int n = arr.length;
        int maxLength = 1;

        // Try all possible subarrays
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {

                // Find max element in current subarray manually
                int maxElem = getMax(arr, i, j);

                // Calculate how many increments are needed
                int increments = getIncrements(arr, i, j, maxElem);

                // Check if it's within allowed limit
                if (increments <= k) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 8, 5, 9, 6};
        int k = 6;

        System.out.println(maxEqualSubarrayLength(arr, k));
    }
}

Python

# Calculate increments to make subarray equal to target
def getIncrements(arr, left, right, target):
    total = 0
    for i in range(left, right + 1):
        if arr[i] < target:
            total += target - arr[i]
    return total

# Find maximum element in subarray
def getMax(arr, left, right):
    maxValue = arr[left]
    for i in range(left + 1, right + 1):
        maxValue = max(maxValue, arr[i])
    return maxValue

# Return maximum valid subarray length
def maxEqualSubarrayLength(arr, k):
    n = len(arr)
    maxLength = 1

    # Try all possible subarrays
    for i in range(n):
        for j in range(i, n):

            # Find max element in current subarray manually
            maxElem = getMax(arr, i, j)

            # Calculate how many increments are needed
            increments = getIncrements(arr, i, j, maxElem)

            # Check if it's within allowed limit
            if increments <= k:
                maxLength = max(maxLength, j - i + 1)

    return maxLength

if __name__ == "__main__":
    arr = [2, 4, 8, 5, 9, 6]
    k = 6

    print(maxEqualSubarrayLength(arr, k))

using System;

class GfG {

    // Calculate increments to make subarray equal to target
    static int getIncrements(int[] arr, int left, int right, int target) {
        int total = 0;
        for (int i = left; i <= right; i++) {
            if (arr[i] < target) {
                total += target - arr[i];
            }
        }
        return total;
    }

    // Find maximum element in subarray
    static int getMax(int[] arr, int left, int right) {
        int maxValue = arr[left];
        for (int i = left + 1; i <= right; i++) {
            maxValue = Math.Max(maxValue, arr[i]);
        }
        return maxValue;
    }

    // Return maximum valid subarray length
    static int maxEqualSubarrayLength(int[] arr, int k) {
        int n = arr.Length;
        int maxLength = 1;

        // Try all possible subarrays
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {

                // Find max element in current subarray manually
                int maxElem = getMax(arr, i, j);

                // Calculate how many increments are needed
                int increments = getIncrements(arr, i, j, maxElem);

                // Check if it's within allowed limit
                if (increments <= k) {
                    maxLength = Math.Max(maxLength, j - i + 1);
                }
            }
        }

        return maxLength;
    }

    static void Main() {
        int[] arr = {2, 4, 8, 5, 9, 6};
        int k = 6;

        Console.WriteLine(maxEqualSubarrayLength(arr, k));
    }
}

JavaScript

// Calculate increments to make subarray equal to target
function getIncrements(arr, left, right, target) {
    let total = 0;
    for (let i = left; i <= right; i++) {
        if (arr[i] < target) {
            total += target - arr[i];
        }
    }
    return total;
}

// Find maximum element in subarray
function getMax(arr, left, right) {
    let maxValue = arr[left];
    for (let i = left + 1; i <= right; i++) {
        maxValue = Math.max(maxValue, arr[i]);
    }
    return maxValue;
}

// Return maximum valid subarray length
function maxEqualSubarrayLength(arr, k) {
    let n = arr.length;
    let maxLength = 1;

    // Try all possible subarrays
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {

            // Find max element in current subarray manually
            let maxElem = getMax(arr, i, j);

            // Calculate how many increments are needed
            let increments = getIncrements(arr, i, j, maxElem);

            // Check if it's within allowed limit
            if (increments <= k) {
                maxLength = Math.max(maxLength, j - i + 1);
            }
        }
    }

    return maxLength;
}

// Driver Code
let arr = [2, 4, 8, 5, 9, 6];
let k = 6;

console.log(maxEqualSubarrayLength(arr, k));

Output

[Expected Approach] Sliding Window with Deque - O(n) Time and O(n) Space

The idea is based on the fact that if we maintain sum of elements and max in a window, then we can count the number of increments in O(1) time using maxElement * windowSize - windowSum. So we maintain a sliding window with these parameters. To track the maximum of every window size, we use a monotonic (decreasing order) deque.

Use two pointers (left, right) to maintain a sliding window and keep track of the sum.
Maintain a monotonic decreasing deque to get the maximum element.
Compute cost = maxElement * window_size - sum.
If cost exceeds k, shrink the window from the left and update the deque.
Track and return the maximum valid window length.

C++

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int maxEqualSubarrayLength(vector<int>& arr, int k) {
    int left = 0, maxLength = 0;
    long long sum = 0;

    deque<int> dq;

    for (int right = 0; right < arr.size(); right++) {
        sum += arr[right];

        // Maintain decreasing deque
        while (!dq.empty() && dq.back() < arr[right]) {
            dq.pop_back();
        }
        dq.push_back(arr[right]);

        // Shrink window if cost > k
        while ((long long)dq.front() * (right - left + 1) - sum > k) {
            sum -= arr[left];

            if (arr[left] == dq.front()) {
                dq.pop_front();
            }
            left++;
        }

        maxLength = max(maxLength, right - left + 1);
    }

    return maxLength;
}

int main() {
    vector<int> arr = {2, 4, 8, 5, 9, 6};
    int k = 6;

    cout << maxEqualSubarrayLength(arr, k) << endl;
    return 0;
}