1124. Longest Well-Performing Interval

MediumStackArrayHash TablePrefix SumMonotonic Stack

Problem Description

The problem presents us with an array called hours which represents the number of hours worked by an employee each day. Our goal is to find the length of the longest interval of days where there are more "tiring days" than "non-tiring days". A "tiring day" is defined as any day where the employee works more than 8 hours. We need to understand the interval dynamics where the "well-performing intervals" are those having a greater count of tiring days compared to non-tiring days. The challenge lies in finding the maximum length of such an interval.

Intuition

The solution to this problem uses an interesting approach akin to finding the longest subarray with a positive sum, which can be solved efficiently using a prefix sum and a hash map. The intuition here is to designate tiring days as a positive contribution (+1) and non-tiring days as a negative contribution (-1) to the sum. As we iterate over the array:

We keep a running sum (s), which is increased by 1 for tiring days and decreased by 1 for non-tiring days.
If at any point, the running sum is positive, it means there are more tiring days than non-tiring days so far, so we update the answer to the current length of days (i + 1).
If the running sum is not positive, we look to see if there is a previous running sum (s - 1). If it exists, then the subarray between the day when s - 1 was the running sum and the current day is a "well-performing interval". We then update our answer if this interval is longer than our current longest interval.
To efficiently find these previous running sums, we use a hash map (pos) that records the earliest day that each running sum occurred. This way, we only store the first occurrence of each sum since we want the longest possible interval.

This approach relies on the idea that if we find a running sum that is greater than a past running sum, then there must have been more tiring days than non-tiring days in between those two points. The efficiency of this solution comes from the fact that we traverse the list only once and access/update the hash map in constant time.

Learn more about Stack, Prefix Sum and Monotonic Stack patterns.

Solution Approach

The solution uses a hash map and a running sum to efficiently track well-performing intervals. Here's the detailed breakdown of how the approach is implemented:

Initialize variables:
- ans tracks the length of the longest well-performing interval found so far and initializes to 0.
- s is our running sum, which helps determine if an interval is well-performing.
- pos is a hash map recording the first occurrence of each running sum.
Iterate over the hours array using enumerate to have both index i and value x for each day.
Update the running sum s:
- Add 1 to s if x > 8 (tiring day).
- Subtract 1 from s if x is not greater than 8 (non-tiring day).
After updating the running sum:
- If s > 0, it means we've encountered more tiring days than non-tiring days up to day i, so update ans to i + 1.
- If s <= 0, we look for s - 1 in pos. If it's found, it indicates there's an interval starting right after the first occurrence of s - 1 up to the current day i, which is a well-performing interval. Hence, we calculate the length of this interval (i - pos[s - 1]) and update ans if it's longer than the current ans.
Update the hash map pos:
- If the current running sum s has not been seen before, record its first occurrence (pos[s] = i). We only update the first occurrence because we're interested in the longest interval.

The code uses pos to remember the earliest day an intermediate sum occurs. By checking if s - 1 is in pos, we can infer if a corresponding earlier sum would allow for a well-performing interval to exist between it and the current day.

Using this pattern allows us to efficiently process each day in constant time, resulting in an overall time complexity of O(n), where n is the number of days. The space complexity is also O(n) due to storing the sum indices in the hash map, possibly equal to the number of days if all running sums are unique.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example using the solution approach described above. Suppose we have the following hours array where we need to find the length of the longest well-performing interval:

1hours = [9, 9, 6, 0, 6, 6, 9]

Here's a step-by-step walkthrough using the solution approach:

We initialize our variables: ans to 0, s to 0, and pos as an empty hash map.
We start iterating through hours with the values and their indices:
- Day 0 (i=0, x=9): It's a tiring day because x > 8. We add 1 to s, making it 1. Since s > 0, we update ans = i + 1 = 1. The hash map pos is updated with pos[1] = 0 because we haven't seen this sum before.
- Day 1 (i=1, x=9): Another tiring day. We increment s to 2. ans is updated to i + 1 = 2 and pos[2] = 1.
- Day 2 (i=2, x=6): A non-tiring day, so we subtract 1 from s, making it 1 again. Since s is still positive, we don't update ans, but we don't update pos[1] either as it already exists.
- Day 3 (i=3, x=0): Non-tiring, subtract 1 from s to 0. ans remains unchanged, and we add pos[0] = 3 to the hash map.
- Day 4 (i=4, x=6): Non-tiring, subtract 1 from s to -1. Since s <= 0, we check for s - 1 which is -2 in pos, but it's not there. No update to ans and we set pos[-1] = 4.
- Day 5 (i=5, x=6): Non-tiring, s goes to -2. We check for s - 1 which is -3 in pos, but it's not found. ans stays the same and pos[-2] = 5.
- Day 6 (i=6, x=9): Tiring, we add 1 to s, bringing it up to -1. We check for s - 1 which is -2 in pos and find it at position 5. We calculate the interval length i - pos[-2] = 6 - 5 = 1. Since this does not exceed our current maximum of ans = 2, we do not update ans.
The iteration is now complete. The longest well-performing interval we found has a length of 2, which occurred between days 0 and 1 (inclusive).

Therefore, the answer for this given hours array is 2.

Solution Implementation

1class Solution:
2    def longest_wpi(self, hours) -> int:
3        # Initialize the maximum length of well-performing interval and sum so far
4        max_length = cumulative_sum = 0
5        # Initialize a dictionary to store the earliest index of a particular cumulative sum
6        sum_indices = {}
7      
8        # Iterate through each hour in the list
9        for index, hour in enumerate(hours):
10            # Increment or decrement the cumulative sum based on the hour's value
11            cumulative_sum += 1 if hour > 8 else -1
12          
13            # If the cumulative sum is positive, we found a well-performing interval
14            # from the beginning up to the current index
15            if cumulative_sum > 0:
16                max_length = index + 1
17            else:
18                # If cumulative_sum - 1 is in the sum_indices, it means we previously had a smaller sum
19                # By finding the length from that index to the current index, we ensure a positive hour count
20                if cumulative_sum - 1 in sum_indices:
21                    max_length = max(max_length, index - sum_indices[cumulative_sum - 1])
22              
23                # If this sum has not been seen before, map it to the current index
24                # We only want to record the first occurrence of a cumulative sum to achieve the longest interval
25                if cumulative_sum not in sum_indices:
26                    sum_indices[cumulative_sum] = index
27      
28        # The resulting max_length is the length of the longest well-performing interval
29        return max_length
30

1class Solution {
2    public int longestWPI(int[] hours) {
3        int longestSequence = 0;  // This will hold the final result, length of the longest well-performing interval.
4        int score = 0;  // This tracks the current score indicating the balance of hours (tiring vs. non-tiring).
5        Map<Integer, Integer> scoreToIndexMap = new HashMap<>();  // Mapping from scores to their first occurrence index.
6
7        // Iterate over the input array.
8        for (int i = 0; i < hours.length; ++i) {
9            // If the number of hours worked is more than 8 in a day, increment score, otherwise decrement.
10            score += hours[i] > 8 ? 1 : -1;
11          
12            // If the current score is positive, it means there is a well-performing interval from 0 to i-th day.
13            if (score > 0) {
14                longestSequence = i + 1;  // Update the length of the longest sequence.
15            } else {
16                // If there's a previous score that is one less than the current score...
17                if (scoreToIndexMap.containsKey(score - 1)) {
18                    // ... then there's a well-performing interval from that previous score's index to the current index i.
19                    longestSequence = Math.max(longestSequence, i - scoreToIndexMap.get(score - 1));
20                }
21                // Store the current score's first occurrence index if it's not already stored.
22                // This means for any score, we save the earliest index at which the score occurred.
23                scoreToIndexMap.putIfAbsent(score, i);
24            }
25        }
26        return longestSequence;  // Return the length of the longest well-performing sequence found.
27    }
28}
29

1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7    // Function to find the length of the longest well-performing interval
8    int longestWPI(vector<int>& hours) {
9        int longestInterval = 0;    // Variable to store the length of the longest interval found
10        int score = 0;              // A score to determine well-performing days vs. non-well-performing days
11        unordered_map<int, int> firstOccurrence;  // Map to store the first occurrence of a score
12
13        // Iterate over the hours array
14        for (int i = 0; i < hours.size(); ++i) {
15            // Increase the score for well-performing days (hours > 8), decrease for non-well-performing days
16            score += hours[i] > 8 ? 1 : -1;
17
18            // If the score is positive, we've found a well-performing interval from the start
19            if (score > 0) {
20                longestInterval = i + 1;  // Update the longest interval length
21            } else {
22                // If the score becomes non-positive, try to find a well-performing interval in the middle
23                // Check if there's a previous score that is one less than the current score
24                if (firstOccurrence.count(score - 1)) {
25                    // Update the longest interval found if necessary
26                    longestInterval = max(longestInterval, i - firstOccurrence[score - 1]);
27                }
28            }
29            // Record the first occurrence of a score if it hasn't already been recorded
30            if (!firstOccurrence.count(score)) {
31                firstOccurrence[score] = i;
32            }
33        }
34        return longestInterval;  // Return the length of the longest well-performing interval found
35    }
36};
37

1// Import necessary libraries from JavaScript/TypeScript (no include statement needed in TypeScript)
2// The typing for unordered_map in TypeScript would use a Map or Record
3
4// Define the function to find the longest well-performing interval
5function longestWPI(hours: number[]): number {
6    let longestInterval: number = 0; // Variable to store the length of the longest interval found
7    let score: number = 0; // A score to determine well-performing days vs non-well-performing days
8    let firstOccurrence: Map<number, number> = new Map(); // Map to store the first occurrence of a score
9
10    // Iterate over the hours array
11    for (let i = 0; i < hours.length; ++i) {
12        // Increase score for well-performing days (hours > 8), decrease for non-well-performing days
13        score += hours[i] > 8 ? 1 : -1;
14
15        // If the score is positive, a well-performing interval from the start has been found
16        if (score > 0) {
17            longestInterval = i + 1; // Update the longest interval length
18        } else {
19            // If the score is non-positive, try to find a well-performing interval in the middle
20            // Check if there's a previous score that is one less than the current score
21            if (firstOccurrence.has(score - 1)) {
22                // Update the longest interval found if necessary
23                longestInterval = Math.max(longestInterval, i - (firstOccurrence.get(score - 1) as number));
24            }
25        }
26      
27        // Record the first occurrence of a score if it hasn't already been recorded
28        if (!firstOccurrence.has(score)) {
29            firstOccurrence.set(score, i);
30        }
31    }
32  
33    return longestInterval; // Return the length of the longest well-performing interval found
34}
35

Time and Space Complexity

Time Complexity

The given Python function longestWPI exhibits a time complexity of O(N), where N represents the length of the input list hours. This is due to the fact that the function iterates through the list exactly once. During each iteration, it performs a constant amount of work: updating the sum s, checking conditions, and updating the pos dictionary or ans as needed.

Space Complexity

The space complexity of the function is also O(N). The pos dictionary is the primary consumer of space in this case, which in the worst-case scenario might need to store an entry for every distinct sum s encountered during the iteration through hours. In a worst-case scenario where every value of s is unique, the dictionary's size could grow linearly with respect to N, the number of elements in hours.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which algorithm should you use to find a node that is close to the root of the tree?

DFS

BFS

Binary search

Backtracking

I don’t know