Leetcode 1124. Longest Well-Performing Interval

Problem

An employee works for several hours each day and tracks his worked hours per day in an array. He considers any day he worked more than 8 hours as a tiring day. He also identifies certain intervals of days as well-performing if within that interval, the number of tiring days is strictly more than the number of non-tiring days.

The task is to find out the length of the longest well-performing interval and return it.

For instance, consider the following array of hours worked per day:

[9,9,6,0,6,6,9] Here, the longest well-performing interval is [9,9,6] and its length is 3. Therefore, 3 is returned.

Solution

The function longestWPI() will take the hours array as an argument. It will iterate through the hours array, and at each iteration, it will calculate a prefix sum, which increments by 1 if the worked hours > 8, else it is decremented by -1, this is used to distinguish tiring days from non-tiring days.

If prefix > 0, it implies that there are more tiring days than non-tiring days so, it updates ans with the index+1 which represents the length of the well-performing interval.

Otherwise, it checks if prefix already exists in the map (which stores prefix and its index), if not it adds the prefix into the map.

Then, it looks for the (prefix-1) in the map, if found, it checks if the length of the current well-performing interval(i - map[prefix - 1]) is greater than the current ans and updates the ans if it is.

In the end, it will return ans representing the length of the longest well-performing interval.

Python Solution

1
2python
3class Solution:
4    def longestWPI(self, hours: List[int]) -> int:
5        ans = 0
6        prefix = 0
7        map = {}
8
9        for i in range(len(hours)):
10            prefix += 1 if hours[i] > 8 else -1
11            if prefix > 0:
12                ans = i + 1
13            else:
14                if prefix not in map:
15                    map[prefix] = i
16                if prefix - 1 in map:
17                    ans = max(ans, i - map[prefix - 1])
18                
19        return ans

Java Solution

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

Javascript Solution

1
2javascript
3var longestWPI = function(hours) {
4    let ans = 0;
5    let prefix = 0;
6    let map = new Map();
7
8    for (let i = 0; i < hours.length; ++i) {
9        prefix += hours[i] > 8 ? 1 : -1;
10        if (prefix > 0) {
11            ans = i + 1;
12        } else {
13            if (!map.has(prefix))
14                map.set(prefix, i);
15            if (map.has(prefix - 1))
16                ans = Math.max(ans, i - map.get(prefix - 1));
17        }
18    }
19
20    return ans;
21};

C++ Solution

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

C# Solution

1
2csharp
3public class Solution {
4    public int LongestWPI(int[] hours) {
5        int ans = 0, score = 0;
6        Dictionary<int, int> seen = new Dictionary<int, int>();
7        for (int i = 0; i < hours.Length; ++i) {
8            score += hours[i] > 8 ? 1 : -1;
9            if (score > 0) {
10                ans = i + 1;
11            } else {
12                if (!seen.ContainsKey(score))
13                    seen[score] = i;
14                if (seen.ContainsKey(score - 1))
15                    ans = Math.Max(ans, i - seen[score - 1]);
16            }
17        }
18        return ans;
19    }
20}

No matter you are using Python, Java, JavaScript, C++, or C#, this problem can be solved using a map to keep track of the scores and then finding the longest interval which satisfies the conditions. The concept of this solution is pretty straightforward and simple to understand, but it might be a bit tricky to implement especially if you are new to these languages.

Each solution utilizes a data structure to save the score calculated at each day. The score increases by 1 if it's a tiring day and reduces by 1 if it's not. When going through the array of worked hours, if a day would make several more tiring days, it keeps track of the biggest interval that satisfies the condition. If not, it will store the score and its corresponding index in a map. Then, it will check if there is a score reducing 1 in the map. If so, it stands for a period in which there are more tiring days, and will compare to the max interval length got before. After we go through the whole array, the biggest interval length will be returned.

Be aware that implementation in each language has its syntax and API to deal with arrays and maps that might differ from one another. The critical point is to keep track of both the score and the corresponding index at the same time while going through the array. Then, check and compare the intervals that have more tiring days to get the longest one.

Understanding the logic, you should be able to implement the solution in any other similar programming language. This method should be efficient enough for an array with length up to 10^5.