Problem Description

The Longest Well-Performing Interval problem is as follows:
Given an integer array hours where each hours[i] represents the number of hours an employee worked on the i-th day, return the length of the longest subarray (interval) where the number of "tiring days" is strictly greater than the number of "non-tiring days".

A "tiring day" is a day where hours[i] > 8. A "non-tiring day" is a day where hours[i] <= 8.

Constraints:

• 1 <= hours.length <= 10⁴
• 0 <= hours[i] <= 16
• There is no requirement to use each element only once; intervals can overlap as long as they are contiguous subarrays.

Thought Process

To solve this problem, we first need to recognize the challenge: For any interval (subarray), we must count the number of tiring and non-tiring days and check if tiring days outnumber non-tiring days.

A brute-force solution would check every possible subarray, count the tiring and non-tiring days, and keep track of the maximum interval length where the tiring days are more. However, this approach is inefficient for large arrays.

To optimize, we can transform the array: Replace each hours[i] with 1 if it's a tiring day and -1 if not. Now, the problem reduces to finding the longest subarray with a positive sum, because a positive sum means more tiring days than non-tiring days.

This insight allows us to use prefix sums and hash maps to efficiently track and find the required intervals.

Solution Approach

Let's break down the optimized solution step by step:

1. Transform the Input:
   • For each day, convert hours[i] to 1 if it's a tiring day (hours[i] > 8), otherwise -1.
2. Prefix Sum Calculation:
   • Compute a running sum (prefix sum) as you iterate through the array. This sum tells you the net difference between tiring and non-tiring days up to the current index.
3. Hash Map for Earliest Occurrence:
   • Use a hash map to record the earliest index where each prefix sum value occurs. This allows us to efficiently find the longest interval with a positive sum.
4. Finding the Longest Interval:
   • If at any point the prefix sum is positive, the interval from the start to the current index is well-performing.
   • If not, check if there is an earlier prefix sum of current prefix sum - 1. If so, the interval between that earlier index and the current index forms a well-performing interval.
5. Track the Maximum Length:
   • Keep updating the maximum length found during the iteration.

We use a hash map because lookups and insertions are O(1), making the solution efficient.

Example Walkthrough

Sample Input: hours = [9, 9, 6, 0, 6, 6, 9]
Step 1: Transform to +1/-1:
hours > 8 becomes 1, otherwise -1:
[1, 1, -1, -1, -1, -1, 1]

Step 2: Prefix Sums:

• Index 0: 1
• Index 1: 2
• Index 2: 1
• Index 3: 0
• Index 4: -1
• Index 5: -2
• Index 6: -1

• At index 1, prefix sum is 2 (positive), so interval [0,1] is well-performing (length 2).
• At index 6, prefix sum is -1. Check if prefix sum 0 exists earlier (it does at index 3). Interval [4,6] is length 3, but sum is -1, so not valid.
• At index 2, prefix sum is 1 (positive), interval [0,2], length 3.
• At index 3, prefix sum is 0 (not positive), but prefix sum -1 exists at index 4, not before.
• At index 6, prefix sum is -1, prefix sum 0 exists at index 3, so interval [4,6], length 3.
• Max length found is 3.

Time and Space Complexity

Brute-Force Approach:

• Time Complexity: O(N²) — Checking all possible subarrays.
• Space Complexity: O(1) — No extra data structures needed.

• Time Complexity: O(N) — Single pass through the array, O(1) hash map operations.
• Space Complexity: O(N) — For storing prefix sum indices in the hash map.

The optimized approach is much faster and suitable for large input sizes.

Summary

In summary, the key insight is to transform the problem into finding the longest subarray with a positive sum by mapping tiring and non-tiring days to +1 and -1. Using prefix sums and a hash map allows us to efficiently find the longest well-performing interval in linear time. This approach leverages simple transformations and data structures to achieve an elegant and efficient solution.

Code Implementation

class Solution:
    def longestWPI(self, hours):
        n = len(hours)
        score = 0
        seen = {}
        max_len = 0
        for i, h in enumerate(hours):
            score += 1 if h > 8 else -1
            if score > 0:
                max_len = i + 1
            else:
                if (score - 1) in seen:
                    max_len = max(max_len, i - seen[score - 1])
            if score not in seen:
                seen[score] = i
        return max_len
      

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        unordered_map<int, int> seen;
        int score = 0, max_len = 0;
        for (int i = 0; i < hours.size(); ++i) {
            score += (hours[i] > 8) ? 1 : -1;
            if (score > 0) {
                max_len = i + 1;
            } else if (seen.count(score - 1)) {
                max_len = max(max_len, i - seen[score - 1]);
            }
            if (!seen.count(score)) {
                seen[score] = i;
            }
        }
        return max_len;
    }
};
      

class Solution {
    public int longestWPI(int[] hours) {
        Map<Integer, Integer> seen = new HashMap<>();
        int score = 0, maxLen = 0;
        for (int i = 0; i < hours.length; ++i) {
            score += (hours[i] > 8) ? 1 : -1;
            if (score > 0) {
                maxLen = i + 1;
            } else if (seen.containsKey(score - 1)) {
                maxLen = Math.max(maxLen, i - seen.get(score - 1));
            }
            if (!seen.containsKey(score)) {
                seen.put(score, i);
            }
        }
        return maxLen;
    }
}
      

var longestWPI = function(hours) {
    let seen = new Map();
    let score = 0, maxLen = 0;
    for (let i = 0; i < hours.length; ++i) {
        score += (hours[i] > 8) ? 1 : -1;
        if (score > 0) {
            maxLen = i + 1;
        } else if (seen.has(score - 1)) {
            maxLen = Math.max(maxLen, i - seen.get(score - 1));
        }
        if (!seen.has(score)) {
            seen.set(score, i);
        }
    }
    return maxLen;
};