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

Finding subarrays that satisfy specific conditions is a common problem in computer science, crucial for optimizing data analysis and processing. In this article, you will learn how to efficiently find the longest subarray within a given array whose average value is greater than or equal to a specified threshold k.

Problem Statement

Given an array of integers nums and an integer k, the challenge is to find the length of the longest subarray [nums[i], nums[i+1], ..., nums[j]] such that the average of its elements is greater than or equal to k. If no such subarray exists, the result is 0. This problem is vital in areas like financial analysis (identifying periods of sustained high performance), sensor data processing (detecting prolonged periods above a critical threshold), and quality control (finding batches meeting average quality standards).

Example

Consider the array nums = {1, 2, 3, 4, 5} and k = 3. The subarray {1, 2, 3, 4, 5} has an average of (1+2+3+4+5)/5 = 3. Since 3 >= 3, this is a valid subarray. Its length is 5. No other subarray can be longer than 5. Therefore, the output is 5.

Background & Knowledge Prerequisites

To effectively understand and implement the solutions, a basic grasp of the following concepts is helpful:

• Arrays and Loops: Fundamental operations for iterating through array elements.
• Arithmetic Operations: Basic calculations including sum and average.
• Prefix Sums: An optimization technique to quickly calculate the sum of any subarray in O(1) time after an O(N) precomputation.
• Binary Search: An efficient algorithm for finding an item in a sorted list by repeatedly dividing the search interval in half.

 

Use Cases or Case Studies

This problem has diverse real-world applications:

• Financial Analysis: Identifying the longest period during which a stock or portfolio maintained an average return above a certain benchmark.
• Sensor Data Monitoring: Determining the longest duration where a sensor's readings (e.g., temperature, pressure, pollutant levels) consistently averaged above a critical safety or operational threshold.
• Sports Analytics: Pinpointing the longest sequence of games where a player's or team's average performance metric (e.g., points per game, shooting percentage) met or exceeded a target.
• Quality Control in Manufacturing: Locating the longest production run where the average quality metric of products (e.g., defect rate, purity concentration) stayed within an acceptable range.
• Network Performance Monitoring: Finding the longest interval during which the average latency or bandwidth usage of a network link remained below a specified maximum.

 

Solution Approaches

We will explore multiple ways to solve this problem, starting with a straightforward brute-force method and moving towards more optimized techniques.

The core of the problem, (sum of subarray) / length >= k, can be rewritten as (sum of subarray) >= k * length. This transformation is key for many solutions.

Approach 1: Brute Force

Summary: This approach checks every possible subarray, calculates its sum and average, and updates the maximum length if the condition is met.

// Longest Subarray Average >= K - Brute Force
#include 

// Function to find the longest subarray with average >= k (Brute Force)
// Time Complexity: O(N^2)
// Space Complexity: O(1)
int findLongestSubarrayBruteForce(int arr[], int n, int k) {
    // Step 1: Initialize maxLength to store the length of the longest valid subarray found
    int maxLength = 0;

    // Step 2: Iterate through all possible starting points 'i' for a subarray
    for (int i = 0; i < n; i++) {
        long long currentSum = 0; // Use long long to prevent potential overflow for sum

        // Step 3: Iterate through all possible ending points 'j' for the subarray starting at 'i'
        for (int j = i; j < n; j++) {
            currentSum += arr[j]; // Add current element to the sum
            int currentLength = j - i + 1; // Calculate the current subarray length

            // Step 4: Check if the average of the current subarray is >= k
            // currentSum / currentLength >= k  is equivalent to  currentSum >= k * currentLength
            // Multiply k by currentLength first to avoid floating point arithmetic and maintain precision
            if (currentSum >= (long long)k * currentLength) {
                // If the condition is met, update maxLength if currentLength is greater
                if (currentLength > maxLength) {
                    maxLength = currentLength;
                }
            }
        }
    }
    return maxLength;
}

int main() {
    // Sample Output for Approach 1

    // Example 1
    int arr1[] = {1, 2, 3, 4, 5};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int k1 = 3;
    printf("Array: {1, 2, 3, 4, 5}, k = 3\\n");
    printf("Longest subarray length (Brute Force): %d\\n", findLongestSubarrayBruteForce(arr1, n1, k1));

    // Example 2
    int arr2[] = {2, 1, 4, 3, 5};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    int k2 = 3;
    printf("\\nArray: {2, 1, 4, 3, 5}, k = 3\\n");
    printf("Longest subarray length (Brute Force): %d\\n", findLongestSubarrayBruteForce(arr2, n2, k2));

    // Example 3
    int arr3[] = {10, 20, 30, 40};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    int k3 = 25;
    printf("\\nArray: {10, 20, 30, 40}, k = 25\\n");
    printf("Longest subarray length (Brute Force): %d\\n", findLongestSubarrayBruteForce(arr3, n3, k3));

    // Example 4: No such subarray
    int arr4[] = {1, 2, 0, 1};
    int n4 = sizeof(arr4) / sizeof(arr4[0]);
    int k4 = 5;
    printf("\\nArray: {1, 2, 0, 1}, k = 5\\n");
    printf("Longest subarray length (Brute Force): %d\\n", findLongestSubarrayBruteForce(arr4, n4, k4));
    
    return 0;
}

Run

Sample Output:

Array: {1, 2, 3, 4, 5}, k = 3
Longest subarray length (Brute Force): 5

Array: {2, 1, 4, 3, 5}, k = 3
Longest subarray length (Brute Force): 3

Array: {10, 20, 30, 40}, k = 25
Longest subarray length (Brute Force): 3

Array: {1, 2, 0, 1}, k = 5
Longest subarray length (Brute Force): 0

 

 

Stepwise Explanation:

1. Initialize maxLength to 0. This variable will store the length of the longest subarray satisfying the condition.
2. Use a nested loop structure:
   • The outer loop (i) iterates from the first element to the last, defining the starting point of a subarray.

• The inner loop (j) iterates from i to the last element, defining the ending point of the current subarray.

1. Inside the inner loop, maintain currentSum for the subarray arr[i...j] and calculate currentLength (j - i + 1).
2. Check if currentSum / currentLength >= k. To avoid floating-point issues and potential precision loss, this condition is transformed to currentSum >= (long long)k * currentLength. The cast to long long for k ensures the multiplication result also uses long long to prevent overflow, especially with large k and currentLength.
3. If the condition is met, update maxLength if currentLength is greater than the current maxLength.
4. After checking all possible subarrays, maxLength holds the result.

 

Approach 2: Binary Search on the Answer

Summary: The length of the longest subarray can range from 0 to N (the total number of elements). We can binary search for this length. For a chosen midlength, a helper function check(midlength) determines if there exists any subarray of that length whose average is >= k. If such a subarray exists, we try for a longer length; otherwise, we try for a shorter one.

// Longest Subarray Average >= K - Binary Search on Answer
#include 
#include  // For bool type
#include   // For INT_MIN/MAX

// Helper function to check if there is any subarray of a given 'length'
// whose average is greater than or equal to k.
// Time Complexity: O(N)
bool check(int arr[], int n, int k, int length) {
    if (length == 0) return true; // An empty subarray technically has an average >= k
                                  // (or is not considered for a positive length problem)
                                  // For finding positive length, this effectively means we found a valid length.
    if (length > n) return false;

    long long currentSum = 0;
    // Step 1: Calculate sum for the first window of 'length'
    for (int i = 0; i < length; i++) {
        currentSum += arr[i];
    }

    // Step 2: Check the first window
    if (currentSum >= (long long)k * length) {
        return true;
    }

    // Step 3: Use a sliding window to check subsequent subarrays of 'length'
    for (int i = length; i < n; i++) {
        currentSum += arr[i] - arr[i - length]; // Slide window: add new element, remove old
        if (currentSum >= (long long)k * length) {
            return true;
        }
    }

    return false; // No subarray of 'length' found with average >= k
}


// Function to find the longest subarray with average >= k using Binary Search on Answer
// Time Complexity: O(N log N) (N for check function, log N for binary search)
// Space Complexity: O(1)
int findLongestSubarrayBinarySearch(int arr[], int n, int k) {
    // Step 1: Define the search space for the length of the subarray
    // The length can be from 0 (if no such subarray, or for edge cases) to n
    int low = 0;
    int high = n;
    int ans = 0; // Stores the maximum valid length found

    // Step 2: Perform binary search on the possible lengths
    while (low <= high) {
        int mid = low + (high - low) / 2; // Calculate the middle length

        // Step 3: Use the helper 'check' function to see if 'mid' length is possible
        if (check(arr, n, k, mid)) {
            // If a subarray of 'mid' length exists with average >= k,
            // then 'mid' is a possible answer. We try to find an even longer one.
            ans = mid;
            low = mid + 1;
        } else {
            // If no subarray of 'mid' length satisfies the condition,
            // then we need to look for shorter lengths.
            high = mid - 1;
        }
    }

    return ans; // 'ans' will hold the longest possible length
}

int main() {
    // Sample Output for Approach 2

    // Example 1
    int arr1[] = {1, 2, 3, 4, 5};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int k1 = 3;
    printf("Array: {1, 2, 3, 4, 5}, k = 3\\n");
    printf("Longest subarray length (Binary Search): %d\\n", findLongestSubarrayBinarySearch(arr1, n1, k1));

    // Example 2
    int arr2[] = {2, 1, 4, 3, 5};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    int k2 = 3;
    printf("\\nArray: {2, 1, 4, 3, 5}, k = 3\\n");
    printf("Longest subarray length (Binary Search): %d\\n", findLongestSubarrayBinarySearch(arr2, n2, k2));

    // Example 3
    int arr3[] = {10, 20, 30, 40};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    int k3 = 25;
    printf("\\nArray: {10, 20, 30, 40}, k = 25\\n");
    printf("Longest subarray length (Binary Search): %d\\n", findLongestSubarrayBinarySearch(arr3, n3, k3));

    // Example 4: No such subarray
    int arr4[] = {1, 2, 0, 1};
    int n4 = sizeof(arr4) / sizeof(arr4[0]);
    int k4 = 5;
    printf("\\nArray: {1, 2, 0, 1}, k = 5\\n");
    printf("Longest subarray length (Binary Search): %d\\n", findLongestSubarrayBinarySearch(arr4, n4, k4));
    
    return 0;
}

Run

Sample Output:

Array: {1, 2, 3, 4, 5}, k = 3
Longest subarray length (Binary Search): 5

Array: {2, 1, 4, 3, 5}, k = 3
Longest subarray length (Binary Search): 3

Array: {10, 20, 30, 40}, k = 25
Longest subarray length (Binary Search): 3

Array: {1, 2, 0, 1}, k = 5
Longest subarray length (Binary Search): 0

 

 

Stepwise Explanation:

1. Define Search Space: The possible lengths of the subarray range from 0 to n. We use low = 0 and high = n to define this range for binary search. ans stores the best valid length found.
2. Binary Search Loop: The while (low <= high) loop iteratively narrows down the search space.
   • mid is calculated as the potential length to check.

• check(arr, n, k, mid) Function: This helper function takes a length and verifies if any subarray of that specific length has an average >= k.
• It uses a sliding window approach:
• First, calculate the sum of the initial length elements.
• If this sum satisfies the average condition, return true.
• Then, slide the window across the array. For each step, subtract the element leaving the window and add the new element entering the window. Check the average condition for each new window.
• This check function runs in O(N) time.

1. Update Search Bounds:
   • If check(arr, n, k, mid) returns true (meaning a subarray of length mid exists), then mid is a possible answer. We store it in ans and try to find an even longer subarray by setting low = mid + 1.

• If check(arr, n, k, mid) returns false, then no subarray of length mid meets the criteria. We must look for shorter subarrays, so high = mid - 1.

1. Return Result: After the binary search loop completes, ans will hold the maximum length for which check returned true, which is the longest valid subarray length.

 

Conclusion

We've explored different strategies to solve the problem of finding the longest subarray with an average greater than or equal to k. The brute-force approach, while easy to understand, is inefficient for large datasets with its O(N^2) time complexity. The binary search on the answer, combined with a sliding window check function, offers a more optimized solution with O(N log N) time complexity, making it suitable for larger inputs.

Understanding how to transform the average condition (sum / length >= k) into a sum condition (sum >= k * length) is a critical insight that simplifies problem-solving and enables more efficient algorithms. For problems demanding even higher performance (O(N)), advanced techniques involving prefix sums and data structures like monotonic queues or segment trees can be adapted, though they introduce additional complexity in implementation.

Summary

• Problem: Find the longest subarray whose average is >= k.
• Key Transformation: sum / length >= k becomes sum >= k * length.
• Approach 1: Brute Force (O(N^2))
• Iterates through all possible start and end points of subarrays.
• Calculates sum and checks average for each subarray.
• Simple to implement but inefficient for large arrays.
• Approach 2: Binary Search on the Answer (O(N log N))
• Binary searches on the possible length of the longest subarray (from 0 to N).
• Uses a check helper function (O(N) with sliding window) to verify if a subarray of a given length meets the average condition.
• More efficient and commonly used for "find longest/shortest X" type problems.

---

Test Your Understanding

1. What would be the output for nums = {10, 1, 2, 3, 4, 5, 6, 7, 8, 9}, k = 5 using any of the methods above?
2. If k is a negative number, how might that affect the interpretation of currentSum >= (long long)k * currentLength? Provide an example.
3. Can you think of a scenario where long long for currentSum would be absolutely essential, even if array elements are small int values?

---

Call to Action

Try implementing the Binary Search on the Answer approach in your preferred programming language and test it with your own custom examples to solidify your understanding!