We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Well-Performing Interval

Number: 1219

Difficulty: Medium

Paid? No

Companies: Infosys

Problem Description

Given an array of integers representing the number of hours worked each day, a day is considered "tiring" if the hours exceed 8. A "well-performing interval" is a contiguous subarray where the number of tiring days is strictly greater than the number of non‐tiring days. The task is to return the length of the longest well-performing interval.

Key Insights

  • Convert each day's hours into a score: +1 for a tiring day (hours > 8) and -1 otherwise.
  • The problem becomes finding the longest subarray with a positive sum.
  • Use a prefix sum array to compute cumulative scores.
  • Use a monotonic (decreasing) stack to store candidate indices from the prefix sum array to enable efficient lookups.
  • If the current prefix sum is positive, the interval from the beginning is valid.
  • Otherwise, search in the stack for the leftmost index with prefix sum less than the current prefix sum to calculate the length of a valid interval.

Space and Time Complexity

Time Complexity: O(n) - Each element is processed in a constant number of operations. Space Complexity: O(n) - For the prefix sum array and the monotonic stack.

Solution

The approach works by first transforming the input array into a score array where each day contributes either +1 or -1 based on whether it is tiring or not. A prefix sum is then computed over these scores. A positive prefix sum indicates that the interval from the start is well-performing.

For cases where the prefix sum is not positive, we use a monotonic (decreasing) stack to keep track of indices that potentially represent the smallest prefix sums seen so far. As we iterate over the array, for the current prefix sum, we look for the earliest index in the stack that has a prefix sum less than the current, which indicates that the subarray between that index and the current index has a positive sum. We update the maximum interval length accordingly.

The solution uses a single traversal to build the prefix sum and another (reverse) traversal combined with the stack lookup to determine the maximum valid interval, ensuring an O(n) solution.

Code Solutions

# Python solution for Longest Well-Performing Interval

def longestWPI(hours):
    # n represents the number of days 
    n = len(hours)
    # Initialize the prefix sum array with an extra 0 at start.
    prefix = [0] * (n + 1)
    
    # Build the prefix sum where each day contributes +1 if >8, else -1.
    for i in range(n):
        prefix[i + 1] = prefix[i] + (1 if hours[i] > 8 else -1)
    
    # Create a monotonic stack to store indices with decreasing prefix values.
    stack = []
    for i in range(n + 1):
        # If current prefix value is less than the last in stack, add the index.
        if not stack or prefix[i] < prefix[stack[-1]]:
            stack.append(i)
    
    # Initialize the result length.
    maxInterval = 0
    # Traverse from the end of the prefix array.
    for i in range(n, -1, -1):
        # While there are indices and current prefix is greater than the prefix at the stored index,
        # update the maximum interval length.
        while stack and prefix[i] > prefix[stack[-1]]:
            maxInterval = max(maxInterval, i - stack.pop())
    
    return maxInterval

# Example usage:
print(longestWPI([9,9,6,0,6,6,9]))  # Expected output: 3
print(longestWPI([6,6,6]))          # Expected output: 0
← Back to All Questions