1124. Longest Well-Performing Interval

MediumStackArrayHash TablePrefix SumMonotonic Stack
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What data structure does Breadth-first search typically uses to store intermediate states?

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:

  1. 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.

  2. Iterate over the hours array using enumerate to have both index i and value x for each day.

  3. 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).

  4. 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.

  5. 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.

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

Depth first search is equivalent to which of the tree traversal order?

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:

  1. We initialize our variables: ans to 0, s to 0, and pos as an empty hash map.

  2. 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.

  3. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Recommended Readings

Stack Intro

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

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/Queue Intro

Monotonic Stack Deque Intro If you'd prefer a video iframe width 560 height 315 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 The word monotonic means a list or a

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ