Longest Well-Performing Interval

medium prefix sum hash map

Problem

Given an array of work hours, a day is tiring if hours > 8. Find the length of the longest interval where tiring days strictly outnumber non-tiring days.

Inputhours = [9, 9, 6, 0, 6, 6, 9]

Output3

Map >8 → +1, else → -1; find longest subarray with sum > 0.

hours (comma-separated)

def longest_wpi(hours):
    first = {}
    s = 0
    best = 0
    for i, h in enumerate(hours):
        s += 1 if h > 8 else -1
        if s > 0:
            best = i + 1
        else:
            if (s - 1) in first:
                best = max(best, i - first[s - 1])
            first.setdefault(s, i)
    return best

function longestWPI(hours) {
  const first = new Map();
  let s = 0, best = 0;
  for (let i = 0; i < hours.length; i++) {
    s += hours[i] > 8 ? 1 : -1;
    if (s > 0) best = i + 1;
    else {
      if (first.has(s - 1)) best = Math.max(best, i - first.get(s - 1));
      if (!first.has(s)) first.set(s, i);
    }
  }
  return best;
}

class Solution {
    public int longestWPI(int[] hours) {
        Map<Integer, Integer> first = new HashMap<>();
        int s = 0, best = 0;
        for (int i = 0; i < hours.length; i++) {
            s += hours[i] > 8 ? 1 : -1;
            if (s > 0) best = i + 1;
            else {
                if (first.containsKey(s - 1)) best = Math.max(best, i - first.get(s - 1));
                first.putIfAbsent(s, i);
            }
        }
        return best;
    }
}

int longestWPI(vector<int>& hours) {
    unordered_map<int, int> first;
    int s = 0, best = 0;
    for (int i = 0; i < (int)hours.size(); i++) {
        s += hours[i] > 8 ? 1 : -1;
        if (s > 0) best = i + 1;
        else {
            if (first.count(s - 1)) best = max(best, i - first[s - 1]);
            if (!first.count(s)) first[s] = i;
        }
    }
    return best;
}

Explanation

The clever first move is to forget the actual hours and just turn each day into +1 (tiring, more than 8 hours) or -1 (not tiring). Now "tiring days outnumber non-tiring days" simply means a stretch whose sum is greater than 0.

We keep a running prefix sum s as we walk left to right. Whenever s > 0, the entire stretch from the start up to here already has more tiring days, so the best length so far is i + 1.

When s is not positive, we use a trick. To make a stretch ending here positive, we want an earlier point whose prefix was s - 1 (one smaller). The first map remembers the earliest index each prefix value appeared, so i - first[s - 1] gives a valid longer-than-zero stretch. We only ever store the first time a value is seen, because earlier means a longer span.

Example: hours = [9, 9, 6, 0, 6, 6, 9] maps to deltas +1, +1, -1, -1, -1, -1, +1. The prefixes dip and rise; the longest stretch with a positive total turns out to have length 3, which is the answer.

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