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] <= 16The key idea in #1124 Longest Well-Performing Interval is to convert the problem into a prefix sum question. Treat each day with more than 8 working hours as +1 and all other days as -1. After this transformation, the task becomes finding the longest subarray with a positive sum.
A common strategy is to maintain a prefix sum and store the earliest index where each prefix value appears using a hash table. If the current prefix sum is positive, the interval from the start is already well-performing. Otherwise, checking whether prefixSum - 1 appeared earlier helps identify a longer valid interval.
Another optimized perspective uses a monotonic decreasing stack of prefix indices. By scanning prefix sums from left to right to build the stack and then from right to left to maximize distances, we can efficiently compute the longest valid interval.
Both approaches rely on prefix sum insights and achieve linear time complexity, making them suitable for large inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Sum + Hash Table | O(n) | O(n) |
| Prefix Sum + Monotonic Stack | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Make a new array A of +1/-1s corresponding to if hours[i] is > 8 or not. The goal is to find the longest subarray with positive sum.
Using prefix sums (PrefixSum[i+1] = A[0] + A[1] + ... + A[i]), you need to find for each j, the smallest i < j with PrefixSum[i] + 1 == PrefixSum[j].
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Prefix sums help transform the problem into finding a longest subarray with a positive cumulative score. By tracking earlier prefix values, we can quickly determine whether a longer valid interval exists ending at the current index.
Yes, this type of prefix sum and interval optimization problem is common in FAANG-style interviews. It tests understanding of array transformations, prefix sums, and efficient data structure usage.
The optimal approach converts working hours into +1 and -1 values and uses prefix sums to track cumulative performance. By using a hash map or a monotonic stack, you can efficiently find the longest interval where the prefix sum indicates more tiring days than non-tiring ones.
Common data structures include hash tables and monotonic stacks. A hash table helps store the earliest occurrence of prefix sums, while a monotonic stack can be used to efficiently evaluate valid intervals from prefix sums.