[Medium] 1124. Longest Well-Performing Interval

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.

Examples

Example 1:

Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The longest well-performing interval is [9,9,6].

Example 2:

Input: hours = [6,6,6]
Output: 0
Explanation: All intervals have more non-tiring days than tiring days.

Constraints

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

Thinking Process

Prefix Sum Transformation: Convert to binary scoring system

Identify the pattern from constraints (sorted? graph? optimal substructure?).
Write brute force first mentally, then optimize the bottleneck.
Verify edge cases: empty input, single element, duplicates.

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Brute force (this problem)	Often O(n^2) or O(2^n)	O(n)	Baseline; clarifies the optimization target
Sort + scan	O(n log n)	O(1)	Pairs, intervals, greedy ordering
Hash map / set	O(n)	O(n)	Frequency, membership, two-sum style
Single-pass linear	O(n)	O(1)	Two pointers, sliding window, Kadane

Solution

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

Use a hash map to track the first occurrence of each prefix sum and find the longest interval where tiring days > non-tiring days.

// import java.util.*;
class Solution {
        public int longestWPI(int[] hours) {
        HashMap<Integer, Integer> seen = new HashMap<Integer, Integer>();
        int score = 0, res = 0;

        for(int i = 0; i < (int)hours.size(); i++) {
            if(hours[i] > 8) score++;
            else score--;

            if(score > 0) res = i + 1;
            else if (seen.contains(score - 1)) res = Math.max(res, i - seen[score - 1]);

            if(!seen.containsKey(score)) seen.put(score, i);
        }

        return res;
    }
}

Solution Explanation

Approach: Brute force (this problem)

Key idea: 1. Prefix Sum Transformation: Convert to binary scoring system

How the code works:

Prefix Sum Transformation: Convert to binary scoring system
- Identify the pattern from constraints (sorted? graph? optimal substructure?).
- Write brute force first mentally, then optimize the bottleneck.
- Verify edge cases: empty input, single element, duplicates.

Walkthrough — input hours = [9,9,6,0,6,6,9], expected output 3:

The longest well-performing interval is [9,9,6].

| Approach | Time Complexity | Space Complexity | |———-|—————-|——————| | Brute Force | O(n²) | O(1) | | Prefix Sum Array | O(n²) | O(n) | | Hash Map (Optimal) | O(n) | O(n) |

Algorithm Breakdown

1. Score Calculation

class Solution {
        public int longestWPI(int[] hours) {
        int n = hours.size();
        int maxLen = 0;

        for(int i = 0; i < n; i++) {
            int tiring = 0, nonTiring = 0;
            for(int j = i; j < n; j++) {
                if(hours[j] > 8) tiring++;
                else nonTiring++;

                if(tiring > nonTiring) {
                    maxLen = Math.max(maxLen, j - i + 1);
                }
            }
        }

        return maxLen;
    }
}

Transformation:

hours[i] > 8 → +1 (tiring day)
hours[i] ≤ 8 → -1 (non-tiring day)

2. Direct Positive Sum Check

class Solution {
        public int longestWPI(int[] hours) {
        int n = hours.size();
        int[] prefix = new int[n + 1];

        for(int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + (hours[i] > 8 ? 1 : -1);
        }

        int maxLen = 0;
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j <= n; j++) {
                if(prefix[j] - prefix[i] > 0) {
                    maxLen = Math.max(maxLen, j - i);
                }
            }
        }

        return maxLen;
    }
}

Why this works:

If score > 0, the entire interval from start to current position is well-performing
Length = i + 1 (0-indexed to 1-indexed conversion)

3. Hash Map Lookup

else if (seen.contains(score - 1)) res = max(res, i - seen[score - 1]);

Mathematical reasoning:

We want prefix[j] - prefix[i] > 0
If current score = k, we look for score - 1 = k - 1
This ensures prefix[j] - prefix[k-1] = k - (k-1) = 1 > 0

4. Hash Map Update

if(!seen.contains(score)) seen[score] = i;

Why only store first occurrence:

We want the longest interval
First occurrence gives us the earliest starting point
Later occurrences would give shorter intervals

Complexity

Common Mistakes

All tiring days: hours = [9,9,9] → 3
All non-tiring days: hours = [6,6,6] → 0
Single element: hours = [9] → 1
Mixed but no valid interval: hours = [6,6,9] → 1
Wrong score calculation: Not handling the binary transformation correctly
Incorrect hash map lookup: Looking for wrong score value
Missing edge case: Not handling score > 0 directly
Wrong interval length: Off-by-one errors in length calculation

Detailed Example Walkthrough

Example: `hours = [9,9,6,0,6,6,9]`

Step 0: i=0, hours[0]=9, score=1, seen={}, res=0
- score > 0 → res = 1
- seen[1] = 0
- seen = {1: 0}

Step 1: i=1, hours[1]=9, score=2, seen={1: 0}, res=1  
- score > 0 → res = 2
- seen[2] = 1
- seen = {1: 0, 2: 1}

Step 2: i=2, hours[2]=6, score=1, seen={1: 0, 2: 1}, res=2
- score > 0 → res = 3
- seen[1] already exists, skip
- seen = {1: 0, 2: 1}

Step 3: i=3, hours[3]=0, score=0, seen={1: 0, 2: 1}, res=3
- score = 0, check seen[0-1] = seen[-1] → not found
- seen[0] = 3
- seen = {1: 0, 2: 1, 0: 3}

Step 4: i=4, hours[4]=6, score=-1, seen={1: 0, 2: 1, 0: 3}, res=3
- score < 0, check seen[-1-1] = seen[-2] → not found
- seen[-1] = 4
- seen = {1: 0, 2: 1, 0: 3, -1: 4}

Step 5: i=5, hours[5]=6, score=-2, seen={1: 0, 2: 1, 0: 3, -1: 4}, res=3
- score < 0, check seen[-2-1] = seen[-3] → not found
- seen[-2] = 5
- seen = {1: 0, 2: 1, 0: 3, -1: 4, -2: 5}

Step 6: i=6, hours[6]=9, score=-1, seen={1: 0, 2: 1, 0: 3, -1: 4, -2: 5}, res=3
- score < 0, check seen[-1-1] = seen[-2] → found at index 5
- res = max(3, 6-5) = max(3, 1) = 3
- seen[-1] already exists, skip
- seen = {1: 0, 2: 1, 0: 3, -1: 4, -2: 5}

Final result: 3

Why This Solution is Optimal

Single Pass: Each element processed exactly once
Hash Map Lookup: O(1) average case for score lookup
Mathematical Insight: Elegant transformation to prefix sum problem
Space Efficient: Only stores necessary prefix sum positions

References

LC 1124: Longest Well-Performing Interval on LeetCode
LeetCode Discuss — LC 1124: Longest Well-Performing Interval
LeetCode Editorial (may require premium)

Key Takeaways

Prefix Sum Transformation: Convert to binary scoring system
Hash Map Optimization: Store first occurrence for longest interval
Mathematical Insight: Look for score - 1 to ensure positive difference
Single Pass: Process each element exactly once

Robina Li

[Medium] 1124. Longest Well-Performing Interval

Examples

Constraints

Thinking Process

Common Approaches

Solution

Solution Explanation

Algorithm Breakdown

1. Score Calculation

2. Direct Positive Sum Check

3. Hash Map Lookup

4. Hash Map Update

Complexity

Common Mistakes

Detailed Example Walkthrough

Example: `hours = [9,9,6,0,6,6,9]`

Why This Solution is Optimal

References

Key Takeaways

Related Posts

Recent Posts

Examples

Constraints

Thinking Process

Common Approaches

Solution

Solution Explanation

Algorithm Breakdown

1. Score Calculation

2. Direct Positive Sum Check

3. Hash Map Lookup

4. Hash Map Update

Complexity

Common Mistakes

Detailed Example Walkthrough

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

Related Problems

Why This Solution is Optimal

References

Key Takeaways

Related Posts

Recent Posts

Example: `hours = [9,9,6,0,6,6,9]`