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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Well-Performing Interval

Difficulty: Medium

Problem Description

We are given hours, a list of the number of hours worked per day for a given employee. A day is considered to be a tiring day if and only if the number of hours worked is (strictly) greater than 8. A well-performing interval is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days. Return the length of the longest well-performing interval.

Key Insights

  • A tiring day is defined as working more than 8 hours.
  • To find the longest well-performing interval, we need to count tiring and non-tiring days.
  • The difference between tiring and non-tiring days can be represented using a prefix sum approach.
  • Utilizing a hash map can help track the first occurrence of each prefix sum difference, allowing us to compute lengths of intervals efficiently.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we can use a prefix sum approach combined with a hash map. The idea is to transform the hours list into a new representation where each tiring day contributes +1 and each non-tiring day contributes -1. We can then compute the cumulative sum as we iterate through the list. By keeping track of the first occurrence of each cumulative sum in a hash map, we can determine the length of the longest interval whenever we find that the current cumulative sum exceeds the previous one by 1. This allows us to efficiently find all well-performing intervals.

Code Solutions

def longestWPI(hours):
    prefix_sum = 0
    first_occurrence = {0: -1}  # Maps prefix sum to its first index
    max_length = 0

    for i, h in enumerate(hours):
        # Increment or decrement prefix_sum based on whether the day is tiring or not
        if h > 8:
            prefix_sum += 1
        else:
            prefix_sum -= 1

        # If the current prefix_sum has been seen before, check the length of the interval
        if prefix_sum > 0:
            max_length = max(max_length, i + 1)
        elif prefix_sum - 1 in first_occurrence:
            max_length = max(max_length, i - first_occurrence[prefix_sum - 1])
        
        # Store the first occurrence of the prefix_sum
        if prefix_sum not in first_occurrence:
            first_occurrence[prefix_sum] = i

    return max_length
← Back to All Questions