Watch 10 video solutions for Longest Well-Performing Interval, a medium level problem involving Array, Hash Table, Stack. This walkthrough by Xavier Elon has 5,856 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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
Constraints:
1 <= hours.length <= 1040 <= hours[i] <= 16Problem Overview: You are given an array hours where each value represents hours worked that day. A day is tiring if hours[i] > 8. The goal is to find the length of the longest subarray where tiring days strictly outnumber non‑tiring days.
Approach 1: Prefix Sum with HashMap (Time: O(n), Space: O(n))
Convert the problem into a prefix score problem. Treat a tiring day (> 8) as +1 and a non‑tiring day as -1. Now the task becomes finding the longest subarray with a positive sum. Maintain a running prefixSum while iterating through the array. If prefixSum > 0, the entire range from index 0 to i is valid. Otherwise, check if the value prefixSum - 1 appeared earlier. If it did, the subarray between that earlier index and the current index has a positive total. A HashMap stores the first occurrence of each prefix sum so lookups are constant time. This approach uses the classic prefix sum transformation combined with a hash table for earliest index tracking. The key insight is that if prefixSum[j] - prefixSum[i] > 0, then the interval (i, j] has more tiring days than non‑tiring days.
Approach 2: Two Pointers with Stack Simulation (Time: O(n), Space: O(n))
This method also starts by converting the input into a +1 and -1 sequence and computing prefix sums. Instead of a hash map, build a decreasing stack of prefix indices. While scanning from left to right, push an index onto the stack only if its prefix sum is smaller than the prefix sum at the current stack top. This produces a monotonic structure that records potential starting positions. Then iterate from right to left and try to extend intervals: while the current prefix sum is greater than the prefix sum at the stack's top index, pop it and update the interval length. Each index is pushed and popped at most once, giving linear time complexity. This technique leverages a monotonic stack to efficiently locate earlier smaller prefix sums that produce positive intervals.
Recommended for interviews: The Prefix Sum + HashMap solution is usually expected in interviews. It directly models the condition of "more tiring than non‑tiring days" using numeric transformation and constant‑time lookups. Interviewers often want to see the prefix sum insight first, then the observation that storing the earliest index maximizes interval length. The monotonic stack variant is equally optimal but slightly less obvious, making it useful as an alternative when discussing O(n) prefix‑based range problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum with HashMap | O(n) | O(n) | General case. Most intuitive optimal solution for interviews. |
| Two Pointers with Monotonic Stack | O(n) | O(n) | When using prefix sums with monotonic structures to find earlier smaller values. |