# Longest Well-Performing Interval
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-well-performing-interval)
Canonical: https://scaleengineer.com/dsa/problems/longest-well-performing-interval
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table, Stack, Monotonic Stack
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
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 <= 104`
* `0 <= hours[i] <= 16`

# Approaches
## Brute Force Approach
A straightforward approach is to examine every possible contiguous interval of days and check if it's a well-performing one. To do this efficiently, we first transform the input `hours` array. We can represent a tiring day as `+1` and a non-tiring day as `-1`. A well-performing interval is then an interval where the sum of these new values is positive.

We can use two nested loops to generate all possible intervals. The outer loop determines the start of the interval, and the inner loop determines the end. For each interval, we calculate the sum of our `+1`/`-1` scores. If the sum is greater than zero, we compare its length with the maximum length found so far and update it if necessary.
**Time:** O(n^2), where n is the number of days. We have two nested loops to check every possible interval. · **Space:** O(1) extra space, as we only need a few variables to keep track of the current sum and maximum length.
**Pros:** Simple to understand and implement.; It uses constant extra space (if we don't count the score array, which can be avoided).
**Cons:** The time complexity is quadratic, which can be too slow for large inputs (e.g., n=10^4).
### Explanation
This method iterates through every possible subarray (interval) of the given `hours` array. For each subarray, it counts the number of tiring and non-tiring days to check if it's a well-performing interval. To optimize the counting process, we can pre-process the `hours` array into a `score` array where a tiring day is `+1` and a non-tiring day is `-1`. Then, for each subarray, we just need to compute the sum. A positive sum indicates a well-performing interval.

```java
class Solution {
    public int longestWPI(int[] hours) {
        int maxLength = 0;
        int n = hours.length;
        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = i; j < n; j++) {
                // Add 1 for a tiring day, -1 for a non-tiring day
                currentSum += (hours[j] > 8) ? 1 : -1;
                // If the sum is positive, the interval is well-performing
                if (currentSum > 0) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
1. First, we simplify the problem by converting the `hours` array into a binary `score` array. A tiring day (`hours[i] > 8`) is represented by `+1`, and a non-tiring day (`hours[i] <= 8`) is represented by `-1`.
2. The problem now is to find the longest subarray with a sum strictly greater than 0.
3. We can iterate through all possible start and end points of a subarray.
4. Initialize `maxLength = 0`.
5. Use a nested loop. The outer loop fixes the starting index `i` from `0` to `n-1`.
6. The inner loop iterates from the starting index `i` to the end of the array, `j` from `i` to `n-1`.
7. For each subarray `[i, j]`, calculate its sum. We can maintain a running sum in the inner loop to do this in O(1) for each `j`.
8. If the `currentSum` of the subarray `[i, j]` is greater than 0, it represents a well-performing interval. We update `maxLength = max(maxLength, j - i + 1)`.
9. After checking all subarrays, `maxLength` will hold the length of the longest well-performing interval.

## Prefix Sum with HashMap
A more efficient solution uses the concept of prefix sums combined with a HashMap. As before, we convert tiring days to `+1` and non-tiring days to `-1`. We then compute the prefix sum as we iterate through this new `score` array.

The problem is to find indices `i` and `j` (`i <= j`) that maximize `j - i + 1`, such that the sum of scores from `i` to `j` is positive. This sum can be expressed as `prefixSum[j] - prefixSum[i-1] > 0`, or `prefixSum[j] > prefixSum[i-1]`.

We can iterate through the array with index `j`, calculating the `current_sum` (which is `prefixSum[j]`). For each `j`, we need to find the earliest index `i-1` where the prefix sum was smaller than `current_sum`. A HashMap is used to store the first index at which each prefix sum value appeared. This allows us to find the required `i-1` efficiently.
**Time:** O(n), where n is the number of days. We iterate through the array once, and HashMap operations (put, get) take average O(1) time. · **Space:** O(n) in the worst case, as the HashMap could potentially store a distinct prefix sum for each element. The range of possible sums is from `-n` to `n`.
**Pros:** Highly efficient with linear time complexity.; Solves the problem in a single pass through the input array.
**Cons:** The logic can be less intuitive to derive compared to the brute-force approach.; Requires extra space for the HashMap.
### Explanation
We iterate through the array once, maintaining a running `sum`. We use a HashMap to keep track of the first time we encounter each `sum` value. The key is the sum, and the value is the index.

We initialize the map with `{0: -1}` to correctly handle cases where a well-performing interval starts at index 0.

For each day `i`, we update our `sum`. 
- If `sum > 0`, the entire interval from the start `[0, i]` is well-performing. This has length `i+1`, which is the longest possible interval ending at `i`. We update our max length accordingly.
- If `sum <= 0`, a well-performing interval ending at `i` must start at some `k > 0`. We are looking for a previous prefix sum, `prev_sum`, that is less than the current `sum`. To maximize the interval length `i - k`, we need the smallest `k`. The condition `sum - prev_sum > 0` is equivalent to `prev_sum <= sum - 1`. The key insight is that we only need to check for the existence of `sum - 1` in our map. If `map.containsKey(sum - 1)`, we have found an interval with a sum of at least 1, and `map.get(sum - 1)` gives us the end index of the prefix that we subtract. The length of this interval is `i - map.get(sum - 1)`. We update our max length with this value if it's larger.

We only add a sum to the map if it's not already there. This ensures we always have the earliest index for any given sum, which is crucial for finding the longest interval.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestWPI(int[] hours) {
        int maxLength = 0;
        int sum = 0;
        // Map to store the first occurrence of a prefix sum
        Map<Integer, Integer> map = new HashMap<>();
        // Base case for intervals starting at index 0
        map.put(0, -1);

        for (int i = 0; i < hours.length; i++) {
            sum += (hours[i] > 8) ? 1 : -1;

            // If the current sum is positive, the interval from the beginning is well-performing.
            // This is the longest possible interval ending at i.
            if (sum > 0) {
                maxLength = i + 1;
            } else {
                // If sum <= 0, we look for a previous prefix sum `sum - 1`.
                // This guarantees an interval sum of `sum - (sum - 1) = 1 > 0`.
                // We check for `sum - 1` because it gives the longest possible interval
                // for a subarray ending at `i` with a positive sum.
                if (map.containsKey(sum - 1)) {
                    maxLength = Math.max(maxLength, i - map.get(sum - 1));
                }
            }
            
            // Store the first time we see a particular sum.
            // If the sum is already in the map, we don't update it because we want the earliest index.
            map.putIfAbsent(sum, i);
        }

        return maxLength;
    }
}
```
### Algorithm
1. Transform the problem: represent tiring days as `+1` and non-tiring days as `-1`. The goal is to find the longest subarray with a sum `> 0`.
2. This problem can be solved in a single pass using a HashMap and the concept of prefix sums.
3. Initialize `sum = 0`, `maxLength = 0`, and a HashMap `map` to store the first-seen index of each prefix sum. Add a base case `map.put(0, -1)` to handle intervals starting from index 0.
4. Iterate through the `hours` array from `i = 0` to `n-1`:
   a. Update the running `sum`: `sum += (hours[i] > 8) ? 1 : -1`.
   b. If `sum` is not already in the `map`, store its first occurrence: `map.put(sum, i)`.
   c. Check if the current prefix sum `sum` is positive. If `sum > 0`, it means the interval from the beginning `[0, i]` is well-performing. Its length is `i + 1`. Update `maxLength = max(maxLength, i + 1)`.
   d. If `sum <= 0`, we look for a previous prefix sum `prev_sum` such that `sum - prev_sum > 0`, which simplifies to `prev_sum < sum`. To get the longest such interval ending at `i`, we need the earliest (smallest index) `prev_sum`. The best candidate for this is `sum - 1`, as it represents the smallest possible positive difference (1). We check if `map.containsKey(sum - 1)`. If it exists, it means we found an interval `[map.get(sum - 1) + 1, i]` with a sum of 1. We update `maxLength = max(maxLength, i - map.get(sum - 1))`.
5. Return `maxLength`.

# Solutions
### Java

```java
class Solution { public int longestWPI ( int [] hours ) { int ans = 0 , s = 0 ; Map < Integer , Integer > pos = new HashMap <>(); for ( int i = 0 ; i < hours . length ; ++ i ) { s += hours [ i ] > 8 ? 1 : - 1 ; if ( s > 0 ) { ans = i + 1 ; } else if ( pos . containsKey ( s - 1 )) { ans = Math . max ( ans , i - pos . get ( s - 1 )); } pos . putIfAbsent ( s , i ); } return ans ; } }
```

### CPP

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

### Python

```python
class Solution : def longestWPI ( self , hours : List [ int ]) -> int : ans = s = 0 pos = {} for i , x in enumerate ( hours ): s += 1 if x > 8 else - 1 if s > 0 : ans = i + 1 elif s - 1 in pos : ans = max ( ans , i - pos [ s - 1 ]) if s not in pos : pos [ s ] = i return ans
```