Longest Well-Performing Interval: Prefix Sum with Hash Map

You are given a list of hours worked each day. A day is tiring if the number of hours worked is strictly greater than 8. A well-performing interval is a contiguous span of days where the number of tiring days is strictly greater than the number of non-tiring days. Return the length of the longest well-performing interval.

This is LeetCode 1124: Longest Well-Performing Interval, and it is one of the cleanest examples of the prefix sum + hash map pattern applied to subarray problems. The trick is recognizing that you can transform the input into a simpler problem with a well-known solution.

Why this problem matters

Prefix sum combined with a hash map is one of the most versatile patterns in array problems. You have already seen it in "Subarray Sum Equals K" and "Contiguous Array." This problem adds a twist: instead of looking for an exact target sum, you need the longest subarray with a positive sum. Learning to adapt the prefix sum + hash map technique to this variant builds real flexibility with the pattern.

The key insight

Transform each day into a score: +1 if the day is tiring (hours > 8), -1 otherwise. Now "more tiring days than non-tiring days" becomes "subarray with positive sum." The problem reduces to finding the longest subarray whose elements sum to a value greater than zero.

Here is the key observation that makes an O(n) solution possible. Compute prefix sums as you walk through the array. At each index i, the prefix sum tells you the running total of scores from index 0 to i:

• If prefix_sum > 0 at index i, then the entire subarray [0..i] has a positive sum. The answer is at least i + 1.
• If prefix_sum is not positive, look up prefix_sum - 1 in the hash map. If it exists at some earlier index j, then the subarray [j+1..i] has a sum of exactly 1 (which is positive), and its length is i - j.

You only store the first occurrence of each prefix sum. This guarantees the longest possible subarray when you find a match.

The solution

def longest_wpi(hours: list[int]) -> int:
    prefix_sum = 0
    best = 0
    first_occurrence = {}

    for i, h in enumerate(hours):
        prefix_sum += 1 if h > 8 else -1

        if prefix_sum > 0:
            best = i + 1
        else:
            if prefix_sum not in first_occurrence:
                first_occurrence[prefix_sum] = i
            if prefix_sum - 1 in first_occurrence:
                best = max(best, i - first_occurrence[prefix_sum - 1])

    return best

Let's break down what each piece does.

The loop iterates through the hours, converting each day to +1 or -1 and accumulating the prefix sum. This single pass builds the prefix sum incrementally -- no need for a separate array.

When prefix_sum > 0, the entire subarray from the beginning to the current index is well-performing. You cannot do better than starting at index 0, so the answer is i + 1.

When prefix_sum is zero or negative, you need to find the earliest index where the prefix sum was exactly prefix_sum - 1. Why prefix_sum - 1? Because if the prefix sum was prefix_sum - 1 at index j, then the subarray from j + 1 to i has a sum of prefix_sum - (prefix_sum - 1) = 1, which is positive. That is the minimum positive sum, and using the first occurrence of that value gives the maximum length.

The hash map stores only the first time each prefix sum value appears. Later occurrences would produce shorter subarrays, so they are useless.

Visual walkthrough

Let's trace through hours = [9, 9, 6, 0, 6, 6, 9] step by step. Watch how the prefix sum rises during tiring days and falls during non-tiring days, and how the hash map captures first occurrences of each prefix sum value.

The first three days produce prefix sums of 1, 2, and 1 -- all positive. So the answer is at least 3 by the time we reach index 2. The remaining days push the prefix sum negative, but no hash map lookup finds a longer interval. The final answer is 3.

Complexity analysis

Time is O(n) where n is the length of the hours array. You make a single pass through the array. Each step does O(1) work: update the prefix sum, check a condition, and do at most one hash map lookup and one hash map insertion.

Space is O(n) in the worst case. The hash map stores at most one entry per distinct prefix sum value. Since the prefix sum changes by 1 at each step, the range of possible values is bounded by n, so the map holds at most n entries.

The building blocks

1. Binary transformation of input

Converting a complex condition into +1/-1 scores is a pattern you will use repeatedly in subarray problems:

scores = [1 if h > 8 else -1 for h in hours]

This transformation turns "count of X exceeds count of Y" into "subarray with positive sum." The same idea applies in "Contiguous Array" (convert 0s to -1s) and any problem where you need to compare frequencies of two categories within a subarray.

2. First-occurrence prefix sum hash map

Storing only the first time each prefix sum appears, then looking up a target to find the longest matching subarray:

prefix_sum = 0
first_occurrence = {}
for i in range(n):
    prefix_sum += scores[i]
    if prefix_sum not in first_occurrence:
        first_occurrence[prefix_sum] = i

This is the core of the prefix sum + hash map technique. In "Subarray Sum Equals K," you look up prefix_sum - k. Here, you look up prefix_sum - 1. The principle is identical: find the earliest point where the prefix sum had a value that, combined with the current prefix sum, implies the target condition over the subarray between them.

Edge cases

Before submitting, think through these scenarios:

• All tiring days: every score is +1, prefix sum is always positive. The answer is the full array length.
• All non-tiring days: every score is -1, prefix sum is always negative. No well-performing interval exists. Return 0.
• Single element: [10] returns 1 (tiring). [6] returns 0 (not tiring).
• Alternating days: the answer depends on whether tiring days ever outnumber non-tiring days in any prefix.
• Prefix sum reaches 0: this means equal tiring and non-tiring days so far. Not well-performing, but the hash map records this for future lookups.

From understanding to recall

You have seen how the prefix sum + hash map pattern adapts to the "longest subarray with positive sum" variant. The transformation from hours to +1/-1 scores is the creative step. After that, the algorithm is mechanical: accumulate prefix sums, check positivity, and use first-occurrence lookups for prefix_sum - 1.

The details that trip people up under pressure are small but critical. Do you look up prefix_sum - 1 or prefix_sum + 1? Do you store first occurrence or last occurrence? Do you update the hash map before or after the lookup? These are not conceptual gaps -- they are recall gaps. Spaced repetition closes them by having you write the code from memory at increasing intervals until the pattern is automatic.

Related posts

• Subarray Sum Equals K - The foundational prefix sum + hash map problem where you look up an exact target
• Contiguous Array - Another binary transformation problem: convert 0s to -1s and find the longest subarray with sum 0
• Maximum Subarray - Kadane's algorithm for the longest/maximum subarray sum, a different angle on subarray sum problems

CodeBricks breaks Longest Well-Performing Interval into its binary transformation and first-occurrence prefix sum building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a prefix sum problem shows up in your interview, you do not think about it. You just write it.