Leetcode 1124: Longest Well-Performing Interval
You are given a list of integers representing the number of hours worked each day. A day is considered tiring if the number of hours worked is strictly greater than 8. A well-performing interval is an interval of days where the number of tiring days is strictly larger than the number of non-tiring days. Your task is to return the length of the longest well-performing interval.
Problem
Approach
Steps
Complexity
Input: You are given a list of integers representing the number of hours worked per day. The length of the list is between 1 and 10,000.
Example: Input: hours = [9,9,6,0,6,6,9]
Constraints:
• The number of elements in hours is between 1 and 10,000.
• Each integer in hours is between 0 and 16.
Output: Return the length of the longest well-performing interval.
Example: Output: 3
Constraints:
• The output should be an integer representing the length of the longest well-performing interval.
Goal: The goal is to find the longest interval where the number of tiring days is greater than the number of non-tiring days.
Steps:
• Traverse the list and calculate a score where tiring days are scored as +1 and non-tiring days as -1.
• Track the cumulative score and use a map to store the earliest index for each score.
• For each score, check if a previous score exists that satisfies the condition of a well-performing interval, and update the result.
Goal: You must ensure that the solution works for a list with up to 10,000 elements efficiently.
Steps:
• The input list will contain between 1 and 10,000 elements.
• Each element in the input list is an integer between 0 and 16.
Assumptions:
• The input list is non-empty.
• The length of the list will be between 1 and 10,000.
• Input: Input: hours = [9,9,6,0,6,6,9]
• Explanation: In this case, the longest well-performing interval is [9,9,6], as there are 2 tiring days (9,9) and 1 non-tiring day (6).
• Input: Input: hours = [6,6,6]
• Explanation: There are no tiring days in this list, so there is no well-performing interval.
Approach: To solve this problem, we will traverse the list and calculate a running score, updating the result whenever we encounter a well-performing interval. We will use a map to track the first occurrence of each cumulative score.
Observations:
• We can track the number of tiring and non-tiring days using a cumulative score.
• By using a map to store the first occurrence of each cumulative score, we can efficiently calculate the length of well-performing intervals.
• We can optimize the solution by processing the list in a single pass and using the map to keep track of the earliest index for each score.
Steps:
• Initialize the score to 0 and the result to 0.
• Loop through the list and update the score based on whether the current day's hours are tiring or not.
• For each score, check if it has been seen before. If it has, update the result by calculating the length of the interval from the first occurrence to the current day.
Empty Inputs:
• If the list is empty, return 0.
Large Inputs:
• Ensure the solution efficiently handles large inputs, up to 10,000 elements.
Special Values:
• If all days are non-tiring, return 0.
Constraints:
• The solution should be able to handle lists with a maximum length of 10,000.
int longestWPI(vector<int>& hours) {
int n = hours.size(), res = 0, score = 0;
map<int, int> mp;
for(int i = 0; i < n; i++) {
score += (hours[i] > 8) ? 1 : -1;
if(score > 0)res = i + 1;
else {
if (!mp.count(score)) mp[score] = i;
if (mp.count(score - 1)) res = max(res, i - mp[score -1]);
}
}
return res;
}
1 : Function Declaration
int longestWPI(vector<int>& hours) {
This function `longestWPI` takes a vector of integers representing working hours for each day and returns the length of the longest well-performing interval (WPI).
2 : Variable Initialization
This line is for initialization and spacing in the code.
3 : Variable Initialization
int n = hours.size(), res = 0, score = 0;
This line initializes the size of the `hours` array (`n`), the result variable `res` to store the length of the longest WPI, and the `score` to track the cumulative score as the loop progresses.
4 : Data Structure
map<int, int> mp;
Declares a map `mp` to store the first occurrence of each score value and its corresponding index.
5 : Loop Start
for(int i = 0; i < n; i++) {
Begins the loop to iterate through each element of the `hours` vector.
6 : Score Update
score += (hours[i] > 8) ? 1 : -1;
This line updates the cumulative `score`. If the working hours for the day are greater than 8, the score is incremented by 1, otherwise, it is decremented by 1.
7 : Result Update (Positive Score)
if(score > 0)res = i + 1;
If the cumulative score is greater than 0, the result `res` is updated to the length of the current interval (`i + 1`).
8 : Else Condition
else {
If the cumulative score is not greater than 0, the code enters the else block to process the map of scores.
9 : Map Update
if (!mp.count(score)) mp[score] = i;
If the map doesn't already contain the current score, the score and its corresponding index are added to the map.
10 : Result Update (Negative Score)
if (mp.count(score - 1)) res = max(res, i - mp[score -1]);
If the map contains the previous score (`score - 1`), the result `res` is updated to the maximum value between the current result and the length of the interval between the current index and the index stored in the map.
11 : Return Statement
return res;
Returns the result, which is the length of the longest well-performing interval (WPI).
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the length of the input list, as we only make a single pass through the list.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage required for the map to track the first occurrence of each cumulative score.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus