LeetCode Problem 1124

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Stack, Monotonic Stack, Prefix Sum

Solution

Edit

LeetCode 1124 - Longest Well-Performing Interval

Problem Understanding

The problem gives us an array hours, where each element represents the number of hours an employee worked on a specific day. A day is classified as tiring if the employee worked strictly more than 8 hours. Otherwise, the day is considered non-tiring.

We are asked to find the longest contiguous interval in which the number of tiring days is strictly greater than the number of non-tiring days. In other words, for any subarray of hours, we want the count of values greater than 8 to exceed the count of values less than or equal to 8.

A useful way to think about this problem is to transform the array into a score system. Every tiring day contributes +1, and every non-tiring day contributes -1. Once we make this transformation, the task becomes finding the longest subarray whose total sum is strictly positive.

For example:

hours = [9,9,6,0,6,6,9]

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

The interval [9,9,6] becomes:

+1 +1 -1 = +1

Since the sum is positive, this interval is well-performing.

The constraints tell us that:

• 1 <= hours.length <= 10^4
• 0 <= hours[i] <= 16

The input size is moderate. An O(n²) solution may be too slow in the worst case because 10^4² = 10^8 operations, which is generally too expensive for LeetCode time limits. This strongly suggests that we should aim for an O(n) or O(n log n) solution.

Several edge cases are important to recognize upfront. If all days are non-tiring, the answer should be 0 because no interval can have more tiring days than non-tiring days. If all days are tiring, the entire array is valid. Arrays of length 1 also require careful handling because a single day may or may not qualify as a well-performing interval.

Approaches

Brute Force Approach

The most direct solution is to examine every possible subarray and determine whether it forms a well-performing interval.

We first transform the array so that tiring days become +1 and non-tiring days become -1. Then, for every possible starting index, we iterate through every ending index and compute the subarray sum. If the sum is positive, we update the maximum interval length.

A naive implementation would recompute the sum for every subarray, resulting in O(n³) time complexity. We can improve this slightly using prefix sums, allowing subarray sums to be computed in constant time. This reduces the complexity to O(n²).

Although correct, this approach is still too slow for n = 10^4.

Optimal Approach, Prefix Sum + Earliest Occurrence Hash Map

The key insight comes from observing the transformed array.

After converting each day:

• hours[i] > 8 → +1
• hours[i] <= 8 → -1

We want the longest subarray whose sum is positive.

Let prefixSum[i] represent the cumulative score up to index i.

If at some index the prefix sum is already positive, then the interval from the beginning of the array to the current index is automatically valid.

If the prefix sum is not positive, we need to find an earlier prefix sum that is smaller by exactly 1.

Why prefix - 1?

Suppose the current prefix sum is curr.

We want:

curr - previousPrefix > 0

This means:

previousPrefix < curr

Since prefix sums change only by ±1, the earliest valid candidate becomes curr - 1.

To efficiently find this, we store the first occurrence of each prefix sum in a hash map. Keeping the earliest occurrence is important because it maximizes interval length.

This gives us a linear-time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Uses prefix sums to evaluate every subarray
Optimal	O(n)	O(n)	Prefix sum with earliest occurrence hash map

Algorithm Walkthrough

1. Initialize a running prefix sum score = 0, a variable maxLength = 0, and a hash map firstSeen.
2. Traverse the array from left to right.
3. For each day:

• If hours[i] > 8, add 1 to the score.
• Otherwise, subtract 1.

4. If the score becomes positive, then the entire interval from index 0 to i is valid. Update:

maxLength = i + 1

5. If this score has never been seen before, store its first occurrence in the hash map. We only store the earliest occurrence because earlier indices produce longer intervals.
6. If the score is not positive, check whether score - 1 exists in the hash map.

If it does, this means there is an earlier prefix sum that allows the interval sum to become positive.

Compute:

intervalLength = i - firstSeen[score - 1]

Update the maximum answer. 7. Continue until all elements are processed. 8. Return maxLength.

Why it works

The algorithm relies on prefix sums. A subarray sum between indices l and r equals:

prefix[r] - prefix[l - 1]

We need this difference to be strictly positive. Therefore, we search for the earliest previous prefix sum smaller than the current one. Because prefix sums change only by ±1, checking score - 1 is sufficient. By storing the earliest occurrence of each prefix sum, we guarantee the longest possible interval for every endpoint.

Python Solution

from typing import List

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        first_seen = {}
        score = 0
        max_length = 0

        for index, hour in enumerate(hours):
            if hour > 8:
                score += 1
            else:
                score -= 1

            if score > 0:
                max_length = index + 1
            else:
                if score - 1 in first_seen:
                    max_length = max(
                        max_length,
                        index - first_seen[score - 1]
                    )

            if score not in first_seen:
                first_seen[score] = index

        return max_length

The implementation begins by initializing a hash map called first_seen, which stores the earliest index where each prefix score appears.

As we iterate through the array, each day contributes either +1 or -1 to the running score depending on whether it is tiring.

If the score becomes positive, the interval from the beginning of the array to the current position is immediately valid, so we update the maximum length.

When the score is non-positive, we check whether score - 1 has appeared before. If it has, the interval between that earliest occurrence and the current index must have a positive sum. We update the answer accordingly.

Finally, we store the score only if it has not been seen before. Keeping the earliest occurrence ensures maximum interval length.

Go Solution

func longestWPI(hours []int) int {
	firstSeen := make(map[int]int)
	score := 0
	maxLength := 0

	for index, hour := range hours {
		if hour > 8 {
			score++
		} else {
			score--
		}

		if score > 0 {
			maxLength = index + 1
		} else {
			if firstIndex, exists := firstSeen[score-1]; exists {
				length := index - firstIndex
				if length > maxLength {
					maxLength = length
				}
			}
		}

		if _, exists := firstSeen[score]; !exists {
			firstSeen[score] = index
		}
	}

	return maxLength
}

The Go implementation follows the exact same logic as the Python solution. A map[int]int is used to store the earliest occurrence of each prefix score.

Go slices naturally handle dynamic arrays, so there is no difference in iteration logic. Integer overflow is not a concern here because the score can range only between -n and n, where n <= 10^4.

Unlike Python dictionaries, Go maps require an explicit existence check using the two-value assignment pattern:

value, exists := map[key]

This is used both when checking for score - 1 and when storing the earliest occurrence of a prefix sum.

Worked Examples

Example 1

hours = [9,9,6,0,6,6,9]

Transformed values:

[+1,+1,-1,-1,-1,-1,+1]

Index	Hours	Change	Score	score > 0?	score - 1 exists?	firstSeen	maxLength
0	9	+1	1	Yes	No	{}	1
1	9	+1	2	Yes	No	{1:0}	2
2	6	-1	1	Yes	No	{1:0,2:1}	3
3	0	-1	0	No	Yes (-1) No	{1:0,2:1}	3
4	6	-1	-1	No	Yes (-2) No	{1:0,2:1,0:3}	3
5	6	-1	-2	No	Yes (-3) No	{1:0,2:1,0:3,-1:4}	3
6	9	+1	-1	No	Yes (-2) Yes	{1:0,2:1,0:3,-1:4,-2:5}	3

Final answer:

3

The longest valid interval is [9,9,6].

Example 2

hours = [6,6,6]

Transformed:

[-1,-1,-1]

Index	Hours	Change	Score	score > 0?	maxLength
0	6	-1	-1	No	0
1	6	-1	-2	No	0
2	6	-1	-3	No	0

No interval has a positive score.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(n)	Hash map stores prefix sums

The algorithm scans the array one time, and every hash map operation takes constant average time. Since each prefix score is inserted at most once, the total time complexity is linear.

The space complexity is O(n) because, in the worst case, every prefix sum may be unique and stored in the hash map.

Test Cases

solution = Solution()

assert solution.longestWPI([9, 9, 6, 0, 6, 6, 9]) == 3  # Example 1
assert solution.longestWPI([6, 6, 6]) == 0  # Example 2

assert solution.longestWPI([9]) == 1  # Single tiring day
assert solution.longestWPI([6]) == 0  # Single non-tiring day

assert solution.longestWPI([9, 9, 9]) == 3  # All tiring days
assert solution.longestWPI([6, 6, 6, 6]) == 0  # All non-tiring days

assert solution.longestWPI([9, 6]) == 1  # Small mixed input
assert solution.longestWPI([6, 9]) == 1  # Valid interval at end

assert solution.longestWPI([9, 6, 9]) == 3  # Entire array valid
assert solution.longestWPI([6, 9, 6, 9, 6]) == 3  # Alternating values

assert solution.longestWPI([8, 9, 8, 9, 8, 9]) == 5  # Hours equal to 8 are non-tiring
assert solution.longestWPI([16, 0, 16, 0, 16]) == 5  # Entire array positive

assert solution.longestWPI([6, 6, 9, 9, 9]) == 5  # Recovery from negative prefix

Test	Why
[9,9,6,0,6,6,9]	Verifies the provided example
[6,6,6]	Confirms no valid interval exists
[9]	Smallest valid input
[6]	Smallest invalid input
[9,9,9]	Entire array valid
[6,6,6,6]	Entire array invalid
[9,6]	Short mixed interval
[6,9]	Valid interval appears late
[9,6,9]	Whole array remains positive
[6,9,6,9,6]	Alternating tiring and non-tiring days
[8,9,8,9,8,9]	Confirms 8 counts as non-tiring
[16,0,16,0,16]	Large values near constraints
[6,6,9,9,9]	Prefix recovery scenario

Edge Cases

All Days Are Non-Tiring

An input like:

[6,6,6,6]

contains no tiring days. Every transformed value becomes -1, meaning every prefix sum is negative. A naive implementation might accidentally count intervals with equal tiring and non-tiring days, but the problem requires strictly more tiring days. The implementation correctly returns 0 because no positive interval exists.

All Days Are Tiring

For input:

[9,9,9]

every transformed value becomes +1. Since the running score remains positive throughout, the algorithm continually updates maxLength, ultimately returning the entire array length.

Hours Equal to 8

A subtle edge case is:

[8,9,8]

The condition is strictly greater than 8, meaning 8 is not tiring. A common mistake is treating 8 as tiring by using >= 8. The implementation explicitly checks:

hour > 8

which guarantees correct classification.

Prefix Sum Starts Negative Then Recovers

Consider:

[6,6,9,9,9]

The prefix sum becomes negative initially, then eventually positive. A naive greedy approach might fail because the best interval begins after early negative days. By storing the earliest occurrence of prefix sums, the algorithm correctly finds the longest valid interval even when recovery happens later.