Longest Well-Performing Interval

Medium
671.

Longest Well-Performing Interval

Longest Well-Performing Interval is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon, Google and Uber interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} hours
 * @return {number}
 */
var longestWPI = function(hours) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Well-Performing Interval — Problem & Solution

Longest Well-Performing Interval solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Longest Well-Performing Interval is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon, Google and Uber interviews.

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

Hints for Longest Well-Performing Interval

  1. Hint 1

    Score each day +1 when tiring and -1 otherwise. The question becomes: what is the longest subarray with a positive sum?

  2. Hint 2

    With prefix sums P, you want the widest i < j with P[j] > P[i].

  3. Hint 3

    Because consecutive prefix sums differ by exactly 1, you only ever need to look for P[j] - 1 — and only at its first occurrence.

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

  1. Sweep the days, maintaining score — the running sum of +1 for tiring and -1 otherwise.
  2. If score > 0, the whole prefix through i qualifies, giving a candidate of length i + 1.
  3. 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].
  4. 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

Java

public static int longestWPI(int[] hours) {
    Map<Integer, Integer> first = new HashMap<>();
    int score = 0, best = 0;
    for (int i = 0; i < hours.length; i++) {
        score += hours[i] > 8 ? 1 : -1;
        if (score > 0) { best = i + 1; continue; }
        Integer at = first.get(score - 1);
        if (at != null && i - at > best) best = i - at;
        if (!first.containsKey(score)) first.put(score, i);
    }
    return best;
}

C++

int longestWPI(vector<int>& hours) {
    unordered_map<int, int> first;
    int score = 0, best = 0;
    for (int i = 0; i < (int) hours.size(); i++) {
        score += hours[i] > 8 ? 1 : -1;
        if (score > 0) { best = i + 1; continue; }
        auto it = first.find(score - 1);
        if (it != first.end() && i - it->second > best) best = i - it->second;
        if (!first.count(score)) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets