Problem Description

You are given an array hours that represents the number of hours an employee worked each day.

A day is classified as a tiring day if the employee worked strictly more than 8 hours that day.

A well-performing interval is a consecutive sequence of days where the number of tiring days is strictly greater than the number of non-tiring days.

Your task is to find the length of the longest well-performing interval.

For example, if hours = [9, 9, 6, 0, 6, 6, 9]:

• Days with hours > 8 are tiring days: positions 0, 1, and 6 (values 9, 9, 9)
• Days with hours ≤ 8 are non-tiring days: positions 2, 3, 4, 5 (values 6, 0, 6, 6)
• The interval from index 0 to 2 has 2 tiring days and 1 non-tiring day, making it well-performing
• The entire array from index 0 to 6 has 3 tiring days and 4 non-tiring days, which is not well-performing

The goal is to find the maximum length among all possible well-performing intervals.

Intuition

The key insight is to transform this problem into finding the longest subarray with a positive sum. We can map each tiring day (hours > 8) to +1 and each non-tiring day to -1. A well-performing interval then becomes a subarray where the sum is positive (more +1s than -1s).

To find the longest such subarray efficiently, we use prefix sums. Let s be the running sum from the start of the array. If at any point s > 0, the entire array from index 0 to the current position forms a well-performing interval.

But what if s ≤ 0? We need to find an earlier position where removing that prefix would give us a positive sum. If the current prefix sum is s, we want to find the earliest position j where the prefix sum was s - 1. Why s - 1? Because removing a prefix with sum s - 1 from a current sum of s gives us a subarray with sum s - (s - 1) = 1, which is positive.

For example, if at position i we have s = -2, and we previously saw s = -3 at position j, then the subarray from j + 1 to i has sum -2 - (-3) = 1, making it a well-performing interval.

We use a hash table to store the first occurrence of each prefix sum value. This allows us to quickly find the earliest position with sum s - 1 and calculate the maximum interval length. We only store the first occurrence because we want the longest possible interval, which means starting as early as possible.

Learn more about Stack, Prefix Sum and Monotonic Stack patterns.

Solution Approach

We implement the solution using prefix sum and a hash table to track the first occurrence of each prefix sum value.

Step-by-step implementation:

1. Initialize variables:

   • ans = 0: stores the maximum length of well-performing interval
   • s = 0: running prefix sum (difference between tiring and non-tiring days)
   • pos = {}: hash table to store the first occurrence index of each prefix sum

2. Transform and process the array: For each day at index i with hours[i]:

   • If hours[i] > 8, increment s by 1 (tiring day contributes +1)
   • Otherwise, decrement s by 1 (non-tiring day contributes -1)

3. Check for well-performing intervals:

   • Case 1: If s > 0, the entire segment from index 0 to current index i is well-performing. Update ans = i + 1.

   • Case 2: If s ≤ 0, check if s - 1 exists in the hash table pos. If it does:

     • Let j = pos[s - 1] be the index where prefix sum was s - 1
     • The segment from index j + 1 to i has sum = s - (s - 1) = 1 > 0
     • Update ans = max(ans, i - j)

4. Record first occurrence: If the current prefix sum s hasn't been seen before, record it in the hash table: pos[s] = i. We only store the first occurrence to maximize the interval length.

Example walkthrough: For hours = [9, 9, 6, 0, 6, 6, 9]:

• Index 0: s = 1, s > 0, so ans = 1
• Index 1: s = 2, s > 0, so ans = 2
• Index 2: s = 1, s > 0, so ans = 3
• Index 3: s = 0, check s - 1 = -1 (not in pos)
• Index 4: s = -1, check s - 1 = -2 (not in pos)
• Index 5: s = -2, check s - 1 = -3 (not in pos)
• Index 6: s = -1, check s - 1 = -2 (exists at index 5), ans = max(3, 6 - 5) = 3

The algorithm runs in O(n) time with O(n) space for the hash table.

Example Walkthrough

Let's walk through a small example with hours = [6, 9, 9, 0, 9].

Step 1: Transform to +1/-1 array

• 6 ≤ 8 → -1 (non-tiring)
• 9 > 8 → +1 (tiring)
• 9 > 8 → +1 (tiring)
• 0 ≤ 8 → -1 (non-tiring)
• 9 > 8 → +1 (tiring)

Transformed: [-1, +1, +1, -1, +1]

Step 2: Process each element with prefix sum

Initialize: ans = 0, s = 0, pos = {}

Index 0 (hours[0] = 6):

• Update: s = 0 + (-1) = -1
• Check: s = -1 ≤ 0, so look for s - 1 = -2 in pos
• -2 not found in pos
• Record: pos[-1] = 0 (first occurrence of sum -1)
• Current ans = 0

Index 1 (hours[1] = 9):

• Update: s = -1 + 1 = 0
• Check: s = 0 ≤ 0, so look for s - 1 = -1 in pos
• -1 found at index 0! Interval from index 1 to 1 has length 1 - 0 = 1
• Update: ans = max(0, 1) = 1
• Record: pos[0] = 1 (first occurrence of sum 0)

Index 2 (hours[2] = 9):

• Update: s = 0 + 1 = 1
• Check: s = 1 > 0, entire array from start is well-performing
• Update: ans = max(1, 2 + 1) = 3
• Record: pos[1] = 2 (first occurrence of sum 1)

Index 3 (hours[3] = 0):

• Update: s = 1 + (-1) = 0
• Check: s = 0 ≤ 0, so look for s - 1 = -1 in pos
• -1 found at index 0! Interval from index 1 to 3 has length 3 - 0 = 3
• Update: ans = max(3, 3) = 3
• pos[0] already exists, don't update

Index 4 (hours[4] = 9):

• Update: s = 0 + 1 = 1
• Check: s = 1 > 0, entire array from start is well-performing
• Update: ans = max(3, 4 + 1) = 5
• pos[1] already exists, don't update

Final Answer: 5

The longest well-performing interval is the entire array [6, 9, 9, 0, 9] with 3 tiring days and 2 non-tiring days.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the hours array exactly once using a single for loop. Within each iteration, all operations are constant time:

• Calculating the cumulative sum s takes O(1)
• Checking if s > 0 takes O(1)
• Dictionary lookup (s - 1 in pos) takes O(1) on average
• Dictionary insertion (pos[s] = i) takes O(1) on average
• The max() comparison takes O(1)

Since we perform n iterations with O(1) operations in each iteration, the overall time complexity is O(n).

Space Complexity: O(n)

The space complexity is determined by the pos dictionary, which stores the first occurrence index of each unique cumulative sum value. In the worst case, every position in the array could produce a different cumulative sum value (for example, when all hours are greater than 8, the cumulative sums would be 1, 2, 3, ..., n). This means the dictionary could store up to n key-value pairs, resulting in O(n) space complexity. The remaining variables (ans, s, i, x) use constant space O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Checking for All Possible Prefix Sum Differences

The Mistake: A common error is trying to check for all prefix sum values less than the current prefix sum, not just prefix_sum - 1. Developers might write:

# INCORRECT approach
for prev_sum in range(prefix_sum - 1, min_prefix_seen - 1, -1):
    if prev_sum in first_occurrence:
        max_length = max(max_length, current_index - first_occurrence[prev_sum])

Why It's Wrong: This unnecessarily increases time complexity and doesn't provide any additional benefit. The key insight is that we only need to check prefix_sum - 1 because:

• We want the minimum previous prefix sum that makes the subarray sum positive
• If prefix_sum[i] - prefix_sum[j] > 0, the smallest valid prefix_sum[j] is prefix_sum[i] - 1
• Checking smaller values would give shorter intervals, not longer ones

The Solution: Stick to checking only prefix_sum - 1 as shown in the correct implementation.

Pitfall 2: Updating First Occurrence Dictionary Incorrectly

The Mistake: Updating the dictionary for every prefix sum value, even if it already exists:

# INCORRECT - overwrites existing values
first_occurrence[prefix_sum] = current_index  # Always updates

Why It's Wrong: This would store the last occurrence instead of the first occurrence of each prefix sum. Since we want the longest possible interval, we need the earliest (first) occurrence of each prefix sum value.

The Solution: Only update when the prefix sum hasn't been seen before:

# CORRECT - preserves first occurrence
if prefix_sum not in first_occurrence:
    first_occurrence[prefix_sum] = current_index

Pitfall 3: Forgetting to Handle the Case When Prefix Sum > 0

The Mistake: Only checking for existing prefix sums in the dictionary without considering the special case:

# INCORRECT - misses the case when entire array from start is well-performing
if prefix_sum - 1 in first_occurrence:
    max_length = max(max_length, current_index - first_occurrence[prefix_sum - 1])

Why It's Wrong: When prefix_sum > 0, the entire interval from index 0 to the current index is well-performing. This is a valid interval that doesn't require looking up previous prefix sums.

The Solution: Always check if prefix_sum > 0 first:

# CORRECT
if prefix_sum > 0:
    max_length = current_index + 1
elif prefix_sum - 1 in first_occurrence:
    max_length = max(max_length, current_index - first_occurrence[prefix_sum - 1])

Pitfall 4: Off-by-One Error in Length Calculation

The Mistake: Incorrectly calculating the interval length:

# INCORRECT - missing the +1
max_length = current_index  # When prefix_sum > 0
# OR
max_length = current_index - first_occurrence[prefix_sum - 1] - 1  # Wrong adjustment

Why It's Wrong:

• When prefix_sum > 0, the interval is from index 0 to current_index inclusive, so length = current_index + 1
• When calculating from a previous occurrence, if the previous sum was at index j, the valid interval starts at j + 1 and ends at current_index, giving length = current_index - j

The Solution: Use the correct formulas:

• When prefix_sum > 0: max_length = current_index + 1
• When using previous occurrence at index j: max_length = current_index - j