1124. Longest Well-Performing Interval
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 whens - 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 usingenumerate
to have both indexi
and valuex
for each day. -
Update the running sum
s
:- Add 1 to
s
ifx > 8
(tiring day). - Subtract 1 from
s
ifx
is not greater than 8 (non-tiring day).
- Add 1 to
-
After updating the running sum:
- If
s > 0
, it means we've encountered more tiring days than non-tiring days up to dayi
, so updateans
toi + 1
. - If
s <= 0
, we look fors - 1
inpos
. If it's found, it indicates there's an interval starting right after the first occurrence ofs - 1
up to the current dayi
, which is a well-performing interval. Hence, we calculate the length of this interval (i - pos[s - 1]
) and updateans
if it's longer than the currentans
.
- If
-
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.
- If the current running sum
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 EvaluatorExample 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:
hours = [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, andpos
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 becausex > 8
. We add 1 tos
, making it 1. Sinces > 0
, we updateans = i + 1 = 1
. The hash mappos
is updated withpos[1] = 0
because we haven't seen this sum before. - Day 1 (
i=1
,x=9
): Another tiring day. We increments
to 2.ans
is updated toi + 1 = 2
andpos[2] = 1
. - Day 2 (
i=2
,x=6
): A non-tiring day, so we subtract 1 froms
, making it 1 again. Sinces
is still positive, we don't updateans
, but we don't updatepos[1]
either as it already exists. - Day 3 (
i=3
,x=0
): Non-tiring, subtract 1 froms
to 0.ans
remains unchanged, and we addpos[0] = 3
to the hash map. - Day 4 (
i=4
,x=6
): Non-tiring, subtract 1 froms
to -1. Sinces <= 0
, we check fors - 1
which is -2 inpos
, but it's not there. No update toans
and we setpos[-1] = 4
. - Day 5 (
i=5
,x=6
): Non-tiring,s
goes to -2. We check fors - 1
which is -3 inpos
, but it's not found.ans
stays the same andpos[-2] = 5
. - Day 6 (
i=6
,x=9
): Tiring, we add 1 tos
, bringing it up to -1. We check fors - 1
which is -2 inpos
and find it at position 5. We calculate the interval lengthi - pos[-2] = 6 - 5 = 1
. Since this does not exceed our current maximum ofans = 2
, we do not updateans
.
- Day 0 (
-
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.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Monotonic Stack Deque Intro If you'd prefer a video div class responsive iframe iframe src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div The word monotonic means a list or
Want a Structured Path to Master System Design Too? Donāt Miss This!