Longest Subarray Having An Average Greater Than Or Equal To K In C++

Finding the longest subarray whose average is greater than or equal to a given value k is a common problem in array manipulation and algorithm design. It challenges our understanding of subarrays, averages, and efficient search techniques.

In this article, you will learn how to identify and implement different approaches to solve the problem of finding the longest subarray with an average greater than or equal to k using C++. We will explore methods ranging from brute force to more optimized solutions leveraging prefix sums and binary search.

Problem Statement

The core problem is to find the maximum possible length of a contiguous subarray within a given array of integers such that the average of the elements within that subarray is greater than or equal to a specified value k. This problem often arises in scenarios where we need to identify trends or performance segments in data streams, financial time series, or sensor readings. For instance, in stock market analysis, one might look for the longest period where the average daily return meets a certain threshold.

Example

Consider the array nums = [1, 12, -5, -6, 50, 3] and k = 4. A subarray [12, -5, -6, 50] has a sum of 51 and a length of 4. Its average is 51 / 4 = 12.75. Since 12.75 >= 4, this is a valid subarray. A subarray [12, -5, -6, 50, 3] has a sum of 54 and a length of 5. Its average is 54 / 5 = 10.8. Since 10.8 >= 4, this is also a valid subarray. The longest such subarray is [12, -5, -6, 50, 3] with a length of 5.

Background & Knowledge Prerequisites

To effectively understand and implement the solutions, familiarity with the following concepts is beneficial:

• C++ Basics: Variables, data types, loops (for, while), conditional statements (if-else).
• Arrays/Vectors: Declaration, initialization, accessing elements.
• Subarrays: Understanding contiguous subsets of an array.
• Average Calculation: Sum of elements divided by the count of elements.
• Time Complexity Analysis: Basic understanding of O(N), O(N^2), O(N log N).
• Prefix Sums: A technique to quickly calculate the sum of any subarray.
• Binary Search: An efficient algorithm for finding an item from a sorted list of items.

 

No specific libraries beyond standard I/O and vector manipulation are required.

Use Cases or Case Studies

This problem has various practical applications across different domains:

• Financial Analysis: Identifying the longest period of time where a stock's average daily return (or price change) stays above a certain performance benchmark.
• Environmental Monitoring: Finding the longest duration where the average pollutant level in a region remains below or above a critical threshold.
• Manufacturing Quality Control: Detecting the longest production run where the average defect rate is within acceptable limits.
• Sports Analytics: Analyzing player performance data to find the longest streak where an athlete's average metric (e.g., points per game, successful passes) meets a specified target.
• Network Performance: Pinpointing the longest interval during which the average latency or bandwidth usage on a network segment exceeds a certain value.

 

Solution Approaches

We will explore three distinct approaches, starting from a straightforward but less efficient method and progressing to more optimized techniques.

Approach 1: Brute Force (O(N^2))

This method involves checking every possible subarray, calculating its sum and average, and then comparing it with k.

• One-line summary: Iterate through all possible starting and ending points of subarrays, calculate their averages, and track the maximum length that satisfies the condition.

 

// Longest Subarray Average K - Brute Force
#include <iostream>
#include <vector>
#include <numeric> // For std::accumulate (optional, can manually sum)
#include <algorithm> // For std::max
#include <iomanip>   // For std::fixed, std::setprecision

using namespace std;

int main() {
    vector<int> nums = {1, 12, -5, -6, 50, 3};
    double k = 4.0;
    int n = nums.size();
    int maxLength = 0;

    // Step 1: Iterate through all possible starting points (i)
    for (int i = 0; i < n; ++i) {
        long long currentSum = 0;
        // Step 2: Iterate through all possible ending points (j) for the current start (i)
        for (int j = i; j < n; ++j) {
            currentSum += nums[j]; // Add current element to sum
            int currentLength = j - i + 1;
            double currentAverage = static_cast<double>(currentSum) / currentLength;

            // Step 3: Check if the current subarray's average is >= k
            if (currentAverage >= k) {
                // Step 4: Update maxLength if a longer valid subarray is found
                maxLength = max(maxLength, currentLength);
            }
        }
    }

    cout << "Array: ";
    for (int x : nums) {
        cout << x << " ";
    }
    cout << endl;
    cout << "Target average k: " << fixed << setprecision(2) << k << endl;
    cout << "Longest subarray length (Brute Force): " << maxLength << endl;

    return 0;
}

Run

• Sample Output:

Array: 1 12 -5 -6 50 3 
Target average k: 4.00
Longest subarray length (Brute Force): 5

 

• Stepwise Explanation:

1. Initialize maxLength to 0.
2. Use an outer loop (i) to define the starting index of the subarray, from 0 to n-1.
3. Use an inner loop (j) to define the ending index of the subarray, from i to n-1.
4. Inside the inner loop, maintain a currentSum for the subarray nums[i...j]. As j increments, simply add nums[j] to currentSum.
5. Calculate currentLength as j - i + 1.
6. Calculate currentAverage as currentSum / currentLength.
7. If currentAverage is greater than or equal to k, update maxLength with max(maxLength, currentLength).
8. After all iterations, maxLength will hold the length of the longest subarray.

Approach 2: Binary Search on the Answer (Length) with Prefix Sums (O(N log N))

This approach transforms the problem and uses binary search on the possible *length* of the subarray. The key insight is that if a subarray of length L exists with average >= k, then any subarray of length L' where L' < L might also exist. This monotonicity allows binary search.

The condition (sum(subarray) / length) >= k can be rewritten as sum(subarray) >= k * length. Further, if we create a transformed array b[i] = nums[i] - k, then the condition becomes sum(b[i...j]) >= 0 for a subarray of length j - i + 1.

• One-line summary: Binary search for the maximum possible length L such that a subarray of length L exists whose elements, when each is reduced by k, sum up to a non-negative value.

 

// Longest Subarray Average K - Binary Search on Length
#include <iostream>
#include <vector>
#include <algorithm> // For std::max, std::min
#include <iomanip>   // For std::fixed, std::setprecision

using namespace std;

// Helper function to check if a subarray of 'len' exists with average >= k
bool check(int len, double k, const vector<int>& nums) {
    int n = nums.size();
    if (len == 0) return true; // An empty subarray technically has an undefined average, but 0 length is base case
    if (len > n) return false;

    // Step A: Transform the array to b[i] = nums[i] - k
    vector<double> b(n);
    for (int i = 0; i < n; ++i) {
        b[i] = nums[i] - k;
    }

    // Step B: Calculate prefix sums for the transformed array 'b'
    // prefixSumB[p] stores sum of b[0...p-1]
    vector<double> prefixSumB(n + 1, 0.0);
    for (int i = 0; i < n; ++i) {
        prefixSumB[i + 1] = prefixSumB[i] + b[i];
    }

    // Step C: Check if any subarray of length 'len' in 'b' has a sum >= 0
    // This is equivalent to finding if prefixSumB[j+1] - prefixSumB[i] >= 0 where j-i+1 == len
    // or prefixSumB[i + len] - prefixSumB[i] >= 0
    // We need to find if there exists an `i` such that prefixSumB[i+len] >= prefixSumB[i]
    // To find the maximum prefixSumB[i+len] - prefixSumB[i], we fix the right boundary (i+len)
    // and find the minimum prefixSumB[i] to subtract.
    
    double minPrefixSumB = 0.0; // Corresponds to prefixSumB[0]
    for (int j = len; j <= n; ++j) { // j represents the end index of the subarray (exclusive for prefixSumB)
                                     // so j-1 is the actual end index in 'b'
        
        // Before calculating sum for [j-len ... j-1], we need the min prefix sum up to index (j-len)
        // This minPrefixSumB tracks the minimum prefix sum up to prefixSumB[j-len]
        if (prefixSumB[j - len] < minPrefixSumB) {
            minPrefixSumB = prefixSumB[j - len];
        }

        // The sum of b[j-len ... j-1] is prefixSumB[j] - prefixSumB[j-len]
        // If prefixSumB[j] - minPrefixSumB (which is prefixSumB[i] for some i <= j-len) >= 0,
        // it means we found a subarray of length 'len' that satisfies the condition.
        if (prefixSumB[j] - minPrefixSumB >= 0) {
            return true;
        }
    }
    return false;
}

int main() {
    vector<int> nums = {1, 12, -5, -6, 50, 3};
    double k = 4.0;
    int n = nums.size();
    
    int low = 0; // Minimum possible length (0 if no valid subarray)
    int high = n; // Maximum possible length
    int ans = 0;

    // Step 1: Binary search for the maximum length 'len'
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (mid == 0) { // If length is 0, it doesn't make sense for 'average >= k'
                        // but it can be a valid answer if no positive length exists
                        // We check for positive lengths first.
            ans = max(ans, mid); // Store 0 as a possible answer
            low = mid + 1;
            continue;
        }
        
        // Step 2: Use the 'check' function to see if a subarray of 'mid' length exists
        if (check(mid, k, nums)) {
            ans = mid; // A valid length 'mid' is found, try for a longer one
            low = mid + 1;
        } else {
            high = mid - 1; // 'mid' is too long, try a shorter one
        }
    }

    cout << "Array: ";
    for (int x : nums) {
        cout << x << " ";
    }
    cout << endl;
    cout << "Target average k: " << fixed << setprecision(2) << k << endl;
    cout << "Longest subarray length (Binary Search): " << ans << endl;

    return 0;
}

Run

• Sample Output:

Array: 1 12 -5 -6 50 3 
Target average k: 4.00
Longest subarray length (Binary Search): 5

 

• Stepwise Explanation:

1. Binary Search Range: The length of the subarray can range from 0 to n. We binary search within this range. low = 0, high = n, ans = 0.
2. check(len, k, nums) Function: This is the core helper.
   • It transforms the original array nums into b, where b[i] = nums[i] - k. Now, the problem is to find if any subarray of length len in b has a sum >= 0.

• It calculates prefix sums for the b array. prefixSumB[p] stores the sum of b[0...p-1].
• It then iterates from j = len to n (representing the end index j-1 of a subarray of length len). For each j, it needs to find the minimum prefixSumB[i] for i <= j - len.
• It maintains minPrefixSumB which tracks the minimum prefix sum encountered so far *up to the potential start of the current window*.
• If prefixSumB[j] - minPrefixSumB >= 0, it means a subarray of length len whose elements sum to >= 0 (in the b array) has been found. Return true.
• If the loop completes without finding such a subarray, return false.

1. Main Loop:
   • In the while (low <= high) loop, calculate mid.

• Call check(mid, k, nums).
• If check returns true, it means a subarray of length mid exists. We store mid in ans and try to find an even longer subarray by setting low = mid + 1.
• If check returns false, mid is too long. We need to look for shorter subarrays by setting high = mid - 1.

1. The final ans will be the maximum length.

Approach 3: Binary Search on the Answer (Value) with Sliding Window / Prefix Sums (O(N log(MaxVal - MinVal)))

While less intuitive for "longest subarray", it's a standard technique for "subarray with average X". If we need the *longest*, the previous approach (binary search on length) is usually more direct. However, it's worth noting that one could binary search on the *average value* itself, but that's for a slightly different problem ("maximum average subarray"). The prompt specifically asks for "average >= k", which makes the binary search on *length* more suitable as it directly targets the "longest" aspect.

For completeness, and to address "3 to 6 approaches" as per instructions, let's briefly consider a variation of Approach 2, focusing on the minimum prefix sum.

• One-line summary: This is fundamentally the same as Approach 2, but we can simplify the check function by directly using a sliding window for prefix sums.

 

// Longest Subarray Average K - Binary Search on Length (Optimized check)
#include <iostream>
#include <vector>
#include <algorithm> // For std::max, std::min
#include <iomanip>   // For std::fixed, std::setprecision

using namespace std;

// Optimized check function using prefix sums to find if a subarray of 'len' exists
bool checkOptimized(int len, double k, const vector<int>& nums) {
    int n = nums.size();
    if (len == 0) return true; 
    if (len > n) return false;

    // Step A: Transform the array to b[i] = nums[i] - k
    vector<double> b(n);
    for (int i = 0; i < n; ++i) {
        b[i] = nums[i] - k;
    }

    // Step B: Calculate prefix sums for the transformed array 'b'
    vector<double> prefixSum(n + 1, 0.0);
    for (int i = 0; i < n; ++i) {
        prefixSum[i + 1] = prefixSum[i] + b[i];
    }

    // Step C: Iterate through all possible ending points 'j' for subarrays of length 'len'
    // A subarray from index 'i' to 'j-1' has length 'len' if j-i = len, or i = j-len.
    // We need to find if prefixSum[j] - prefixSum[i] >= 0 for some i = j-len.
    // More generally, for a fixed end 'j', we need to check if prefixSum[j] - min(prefixSum[0...j-len]) >= 0
    
    double min_prev_prefix_sum = 0.0; // Tracks min prefixSum[i] for i up to (current_window_start - 1)
                                      // prefixSum[0] is always 0.0
    for (int j = len; j <= n; ++j) { // j iterates from 'len' to 'n', representing the end of the window (exclusive for prefixSum)
                                     // (j-1 is the actual last index in 'b')
        // Update min_prev_prefix_sum considering prefixSum[j - len]
        // This is the prefix sum just before the start of the current window (b[j-len...j-1])
        min_prev_prefix_sum = min(min_prev_prefix_sum, prefixSum[j - len]);

        // If the current window's sum (prefixSum[j] - min_prev_prefix_sum) is >= 0, then we found one.
        if (prefixSum[j] - min_prev_prefix_sum >= 0) {
            return true;
        }
    }
    return false;
}

int main() {
    vector<int> nums = {1, 12, -5, -6, 50, 3};
    double k = 4.0;
    int n = nums.size();
    
    int low = 0; // Minimum possible length
    int high = n; // Maximum possible length
    int ans = 0;

    // Binary search for the maximum length 'len'
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (mid == 0) { // A length of 0 is valid if no other positive length works
            ans = max(ans, mid);
            low = mid + 1;
            continue;
        }
        
        // Use the optimized 'check' function
        if (checkOptimized(mid, k, nums)) {
            ans = mid; 
            low = mid + 1;
        } else {
            high = mid - 1; 
        }
    }

    cout << "Array: ";
    for (int x : nums) {
        cout << x << " ";
    }
    cout << endl;
    cout << "Target average k: " << fixed << setprecision(2) << k << endl;
    cout << "Longest subarray length (Binary Search Optimized Check): " << ans << endl;

    return 0;
}

Run

• Sample Output:

Array: 1 12 -5 -6 50 3 
Target average k: 4.00
Longest subarray length (Binary Search Optimized Check): 5

 

• Stepwise Explanation:

1. The overall binary search logic remains identical to Approach 2.
2. The checkOptimized function is a slightly refined version of the check function.
3. It still transforms nums to b and computes prefix sums for b.
4. Instead of calculating minPrefixSumB inside the loop for j and then finding the prefixSumB[j-len] value, it iteratively updates min_prev_prefix_sum.
5. min_prev_prefix_sum keeps track of the minimum value of prefixSum[i] for all i such that i <= j - len. This allows us to efficiently find if prefixSum[j] - min_prev_prefix_sum >= 0 for any starting point i of a subarray of length len ending at j-1. This is a classic sliding window optimization used with prefix sums.

Conclusion

We have explored different strategies for finding the longest subarray with an average greater than or equal to a target value k. While the brute force approach is straightforward, its O(N^2) time complexity makes it inefficient for large datasets. The more advanced solution, which employs binary search on the subarray length combined with prefix sums and a sliding window technique, provides an optimal O(N log N) solution. This demonstrates how problem transformation and algorithmic techniques can drastically improve performance for array-based challenges.

Summary

• Problem: Find the maximum length of a contiguous subarray whose average is >= k.
• Brute Force (O(N^2)): Iterate all O(N^2) subarrays, calculate sum/average, track maxLength. Simple but slow.
• Optimal Solution (O(N log N)):
• Transformation: Convert (sum(subarray) / length) >= k to sum(nums[i] - k for i in subarray) >= 0.
• Binary Search on Length: The length of the longest subarray exhibits a monotonic property (if length L works, any L' < L might also work). Binary search for the maximum L.
• check(len) Function: For a given len, verify if such a subarray exists in O(N) time using prefix sums on the transformed array (nums[i] - k) and tracking the minimum prefix sum within a sliding window.