Longest Well-Performing Interval — Medium Problem & Solution

A day is tiring if more than 8 hours were worked. An interval of days is well-performing when it contains strictly more tiring days than non-tiring days.

Difficulty: Medium
Topics: Arrays, Hash Table, Prefix Sum, Stack
Asked at: Amazon, Google, Uber
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A day is tiring if more than 8 hours were worked. An interval of days is well-performing when it contains strictly more tiring days than non-tiring days.

Given hours, return the length of the longest well-performing interval.

Example 1

Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The first three days have two tiring days and one that is not.

Example 2

Input: hours = [6,6,6]
Output: 0
Explanation: No tiring days at all.

Example 3

Input: hours = [9,6,9]
Output: 3
Explanation: Two tiring against one.

Constraints

1 <= hours.length <= 10000
0 <= hours[i] <= 16

How to solve Longest Well-Performing Interval

Convert to ±1 and look for the widest prefix-sum increase. The scores change by exactly one per step, which is what makes a single hash-map lookup enough instead of a search over all smaller prefix sums.

Approach

Sweep the days, maintaining score — the running sum of +1 for tiring and -1 otherwise.
If score > 0, the whole prefix through i qualifies, giving a candidate of length i + 1.
Otherwise look up the first index where the score was score - 1; the interval after it is well-performing, giving a candidate of i - first[score - 1].
Record the first index at which each score value appears and never overwrite it.

Why it works

For the interval ending at j to be positive you need an earlier prefix strictly smaller than P[j]. Since the prefix sums move in steps of one, the first time a value below P[j] ever appeared it must have been exactly P[j] - 1 — so that single lookup finds the leftmost usable start.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

Overwriting first[score] gives the shortest interval instead of the longest.
Searching every smaller score is O(n²) and unnecessary given the step-of-one property.
hours[i] == 8 is not tiring — the threshold is strict.

Reference solution

Python

from typing import List

def longestWPI(hours: List[int]) -> int:
    first = {}
    score = 0
    best = 0
    for i, h in enumerate(hours):
        score += 1 if h > 8 else -1
        if score > 0:
            best = i + 1
            continue
        if score - 1 in first:
            best = max(best, i - first[score - 1])
        if score not in first:
            first[score] = i
    return best

JavaScript

var longestWPI = function(hours) {
    var first = {};
    var score = 0, best = 0;
    for (var i = 0; i < hours.length; i++) {
        score += hours[i] > 8 ? 1 : -1;
        if (score > 0) { best = i + 1; continue; }
        var key = String(score - 1);
        if (first[key] !== undefined && i - first[key] > best) best = i - first[key];
        var own = String(score);
        if (first[own] === undefined) first[own] = i;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue