Solution Explanation: Longest Well-Performing Interval

The problem asks to find the length of the longest well-performing interval in an array of hours worked. A well-performing interval is defined as a continuous subarray where the number of tiring days (hours > 8) strictly exceeds the number of non-tiring days.

Approach: Prefix Sum and Hash Table

The most efficient approach uses prefix sums and a hash table. The core idea is to track the cumulative difference between tiring and non-tiring days as we iterate through the hours array.

1. Prefix Sum: We maintain a variable s representing the cumulative difference. If hours[i] > 8, we increment s; otherwise, we decrement it. This s essentially represents the "balance" of tiring vs. non-tiring days up to index i.

2. Hash Table (Dictionary): We use a hash table (dictionary in Python) pos to store the first index where each cumulative sum s is encountered. This is crucial for efficiently finding well-performing intervals.

3. Iteration and Update: We iterate through the hours array. For each element:

   • If s > 0, it means the current prefix is already a well-performing interval, so we update the maximum length ans.
   • If s <= 0, we check if s - 1 exists in pos. If it does, it implies that the subarray from pos[s-1] + 1 to i is a well-performing interval (because the difference between tiring and non-tiring days increases by 1 from pos[s-1] to i). We update ans accordingly.
   • We update pos with the current index i for the current cumulative sum s only if it's not already present (to ensure we store the first occurrence).

4. Result: After iterating through the entire array, ans will hold the length of the longest well-performing interval.

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the hours array. We iterate through the array once. Hash table lookups and insertions are on average O(1).
• Space Complexity: O(n) in the worst case. The hash table pos could potentially store up to n distinct cumulative sums.

Code Implementation (Python)

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        ans = s = 0
        pos = {}  # Dictionary to store the first index of each cumulative sum
        for i, x in enumerate(hours):
            s += 1 if x > 8 else -1  # Update cumulative sum
            if s > 0:
                ans = i + 1  # Current prefix is well-performing
            elif s - 1 in pos:
                ans = max(ans, i - pos[s - 1])  # Subarray is well-performing
            if s not in pos:
                pos[s] = i  # Store the first occurrence of this cumulative sum
        return ans

The implementations in Java, C++, and Go follow the same logic, using their respective hash table implementations (HashMap, unordered_map, and map). The core algorithm remains consistent across all languages.