Longest Well-Performing Interval

Longest Well-Performing Interval

What is this problem about?

In the Longest Well-Performing Interval problem, you are given an array of integers representing the number of hours an employee worked each day. A day is considered "tiring" if the hours worked are strictly greater than 8. A "well-performing interval" is a contiguous sequence of days where the number of tiring days is strictly greater than the number of non-tiring days. Your goal is to find the maximum length of such an interval.

Why is this asked in interviews?

This problem is a sophisticated array transformation challenge. It is asked to see if a candidate can abstract real-world data into binary mathematics. By transforming the problem into a prefix sum scenario, it rigorously tests Hash Map state tracking. It demonstrates a candidate's ability to optimize what looks like an $O(N^2)$ sliding window into a highly efficient $O(N)$ single pass.

Algorithmic pattern used

This problem leverages the Prefix Sum and Hash Table pattern. First, transform the array: if hours > 8, it's a 1; otherwise, it's a -1. As you iterate, maintain a running score. We want a subarray where the sum is $> 0$ (meaning more 1s than -1s). If the current score > 0, the interval from the beginning of the array is valid. If score <= 0, we look in our Hash Table to see if score - 1 was seen previously. The distance between the current index and the first occurrence of score - 1 is a valid well-performing interval!

Example explanation

Hours: [9, 9, 6, 0, 6, 6, 9] Transformed: [1, 1, -1, -1, -1, -1, 1]

• Index 0 (1): Score = 1. > 0, so max length = 1. Map: {1: 0}.
• Index 1 (1): Score = 2. > 0, so max length = 2. Map: {1: 0, 2: 1}.
• Index 2 (-1): Score = 1. > 0, so max length = 3.
• Index 3 (-1): Score = 0. We need score - 1 which is -1. Not in map. Map: {..., 0: 3}.
• Index 4 (-1): Score = -1. We need -2. Not in map. Map: {..., -1: 4}.
• Index 5 (-1): Score = -2. We need -3. Not in map. Map {..., -2: 5}.
• Index 6 (1): Score = -1. We need -2. Is -2 in the map? Yes, at index 5! The interval from index 5 to 6 is valid. Length = 6 - 5 = 1. The overall max length is 3 (the first three days [9, 9, 6]).

Common mistakes candidates make

A major error is updating the Hash Map with new indices when a score repeats. You must only store the first time a score is seen. Overwriting it with a later index will shrink the calculated interval, causing you to miss the longest possible sequence. Another mistake is using standard sliding window techniques (Two Pointers), which fail here because the score fluctuates up and down unpredictably.

Interview preparation tip

When dealing with the Longest Well-Performing Interval interview pattern or any problem comparing the counts of two categories, always apply the "1 and -1 transformation". If you need category A to be strictly greater than category B, you are simply looking for a subarray whose sum is $\ge 1$. A Hash Map tracking the earliest index of every prefix sum easily achieves this in $O(N)$ time.