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.

Examples

Example 1

1
2
3

Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The longest well-performing interval is [9,9,6].

Example 2

1
2

Input: hours = [6,6,6]
Output: 0

Constraints

  • 1 <= hours.length <= 10^4
  • 0 <= hours[i] <= 16

Solution

Method 1 – Prefix Sum with Hash Map

Intuition

We can convert the problem into finding the longest subarray with a positive sum by mapping tiring days to +1 and non-tiring days to -1. Using prefix sums and a hash map to record the first occurrence of each prefix sum, we can efficiently find the longest interval.

Approach

  1. Map each day: if hours[i] > 8, use +1; else, use -1.
  2. Compute the prefix sum as we iterate through the array.
  3. Use a hash map to store the first index where each prefix sum occurs.
  4. If the prefix sum is positive at any index, the interval from the start is well-performing.
  5. Otherwise, check if (prefix sum - 1) has been seen before; if so, update the answer with the interval length.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int n = hours.size(), ans = 0, s = 0;
        unordered_map<int, int> first;
        for (int i = 0; i < n; ++i) {
            s += hours[i] > 8 ? 1 : -1;
            if (s > 0) ans = i + 1;
            else {
                if (first.count(s - 1)) ans = max(ans, i - first[s - 1]);
            }
            if (!first.count(s)) first[s] = i;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func longestWPI(hours []int) int {
    n, ans, s := len(hours), 0, 0
    first := map[int]int{}
    for i := 0; i < n; i++ {
        if hours[i] > 8 {
            s++
        } else {
            s--
        }
        if s > 0 {
            ans = i + 1
        } else if v, ok := first[s-1]; ok {
            if i-v > ans {
                ans = i - v
            }
        }
        if _, ok := first[s]; !ok {
            first[s] = i
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int longestWPI(int[] hours) {
        int n = hours.length, ans = 0, s = 0;
        Map<Integer, Integer> first = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            s += hours[i] > 8 ? 1 : -1;
            if (s > 0) ans = i + 1;
            else if (first.containsKey(s - 1)) ans = Math.max(ans, i - first.get(s - 1));
            if (!first.containsKey(s)) first.put(s, i);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun longestWPI(hours: IntArray): Int {
        var ans = 0
        var s = 0
        val first = mutableMapOf<Int, Int>()
        for (i in hours.indices) {
            s += if (hours[i] > 8) 1 else -1
            if (s > 0) ans = i + 1
            else if (first.containsKey(s - 1)) ans = maxOf(ans, i - first[s - 1]!!)
            if (!first.containsKey(s)) first[s] = i
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def longestWPI(self, hours: list[int]) -> int:
        ans = s = 0
        first = {}
        for i, h in enumerate(hours):
            s += 1 if h > 8 else -1
            if s > 0:
                ans = i + 1
            elif (s - 1) in first:
                ans = max(ans, i - first[s - 1])
            if s not in first:
                first[s] = i
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn longest_wpi(hours: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut s = 0;
        let mut first = std::collections::HashMap::new();
        for (i, &h) in hours.iter().enumerate() {
            s += if h > 8 { 1 } else { -1 };
            if s > 0 {
                ans = (i + 1) as i32;
            } else if let Some(&v) = first.get(&(s - 1)) {
                ans = ans.max((i - v) as i32);
            }
            first.entry(s).or_insert(i);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    longestWPI(hours: number[]): number {
        let ans = 0, s = 0;
        const first = new Map<number, number>();
        for (let i = 0; i < hours.length; ++i) {
            s += hours[i] > 8 ? 1 : -1;
            if (s > 0) ans = i + 1;
            else if (first.has(s - 1)) ans = Math.max(ans, i - first.get(s - 1)!);
            if (!first.has(s)) first.set(s, i);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), as we scan the array once.
  • 🧺 Space complexity: O(n), for the hash map storing prefix sums.