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.
This approach uses a prefix sum combined with a hashmap to find the longest well-performing interval. Transform the hours array into +1 for tiring days and -1 for non-tiring days. Calculate the prefix sum and use a hashmap to store the first occurrence of each prefix sum value. This helps in quickly determining the length of intervals where tiring days exceed non-tiring days.
We start by initializing a prefix sum to zero and an empty hashmap. We iterate over the hours and update the prefix sum by adding 1 for tiring days or subtracting 1 otherwise. If the prefix sum is positive, it means all days up to the current day form a well-performing interval. If not, we look for previous occurrences of prefix sum - 1 in the hashmap, which, if found, indicates a valid interval ending at the current day. We track the first occurrence of each prefix sum to efficiently find longer intervals.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n) where n is the number of days, since we traverse the list once.
Space Complexity: O(n) due to the hashmap storing prefix sums.
This approach uses a two-pointer technique in tandem with a stack-like simulation (monotonic stack) for efficiently checking conditions. We transform hours into +1/-1 representation and then utilize two pointers to directly seek the longest interval with more tiring days than non-tiring ones.
This Python solution first converts 'hours' into +1/-1. We then use a variable 'accumulated' to keep track of intervals and a stack to store indices where 'accumulated' becomes less optimal.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n^2) for the worst case due to double iteration with the stack.
Space Complexity: O(n) since stack can store up to n-1 indices.
We can use the idea of prefix sum, maintaining a variable s, which represents the difference between the number of "tiring days" and "non-tiring days" from index 0 to the current index. If s is greater than 0, it means that the segment from index 0 to the current index is a "well-performing time period". In addition, we use a hash table pos to record the first occurrence index of each s.
Next, we traverse the hours array, for each index i:
hours[i] > 8, we increment s by 1, otherwise we decrement s by 1.s > 0, it means that the segment from index 0 to the current index i is a "well-performing time period", we update the result ans = i + 1. Otherwise, if s - 1 is in the hash table pos, let j = pos[s - 1], it means that the segment from index j + 1 to the current index i is a "well-performing time period", we update the result ans = max(ans, i - j).s is not in the hash table pos, we record pos[s] = i.After the traversal, return the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the hours array.
| Approach | Complexity |
|---|---|
| Approach 1: Prefix Sum with HashMap | Time Complexity: O(n) where n is the number of days, since we traverse the list once. |
| Approach 2: Two Pointers with Stack Simulation | Time Complexity: O(n^2) for the worst case due to double iteration with the stack. |
| Prefix Sum + Hash Table | — |
| 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. |
LeetCode 1124 | Longest Well Performing Interval | Algorithm Explained (Java + Whiteboard) • Xavier Elon • 5,856 views views
Watch 9 more video solutions →Practice Longest Well-Performing Interval with our built-in code editor and test cases.
Practice on FleetCode