Longest well performing interval

Array Hash Table Stack Monotonic Stack Prefix Sum

37.0% acceptance

Feb 25, 2026

1529

122

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn longest_wpi(hours: Vec<i32>) -> i32 {
    let mut prefix = 0i32;
    let mut first_seen: HashMap<i32, usize> = HashMap::new();
    let mut result = 0;
    for (i, &h) in hours.iter().enumerate() {
      prefix += if h > 8 { 1 } else { -1 };
      if prefix > 0 {
        result = i + 1;
      } else {
        if let Some(&j) = first_seen.get(&(prefix - 1)) {
          result = result.max(i - j);
        }
      }
      first_seen.entry(prefix).or_insert(i);
    }
    result as i32
  }
}