Jobs

Interviews

Discussions

Longest Well-Performing Interval

Medium

Asked by:

22 views

Topics:

ArraysDynamic Programming

We are given hours, a list of the number of hours worked per day for a given employee.

A day is considered to be a tiring day if and only if the number of hours worked is (strictly) greater than 8.

A well-performing interval is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.

Return the length of the longest well-performing interval.

Example 1:

Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The longest well-performing interval is [9,9,6].

Example 2:

Input: hours = [6,6,6]
Output: 0

Constraints:

1 <= hours.length <= 10⁴
0 <= hours[i] <= 16

Try coding it in LeetCode

Longest Well-Performing Interval

Medium

Asked by:

22 views

Topics:

ArraysDynamic Programming

We are given hours, a list of the number of hours worked per day for a given employee.

A day is considered to be a tiring day if and only if the number of hours worked is (strictly) greater than 8.

A well-performing interval is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.

Return the length of the longest well-performing interval.

Example 1:

Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The longest well-performing interval is [9,9,6].

Example 2:

Input: hours = [6,6,6]
Output: 0

Constraints:

1 <= hours.length <= 10⁴
0 <= hours[i] <= 16

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values in the `hours` array? Can the values be negative?
If there are multiple well-performing intervals of the same longest length, should I return any one of them?
What should I return if there is no well-performing interval (i.e., no sub-array with more values greater than 8 than values less than or equal to 8)?
Can the input array `hours` be empty or null?
By 'well-performing interval', do you mean a *contiguous* subarray of days where the number of days working more than 8 hours is strictly greater than the number of days working 8 hours or less?

Brute Force Solution

Approach

We want to find the longest period where there were more good days than bad days. The simplest way to do this is to just check every possible period and see if it meets the criteria.

Here's how the algorithm would work step-by-step:

Start by looking at the first day, and then check if just that day was a 'good' period.
Then, look at the first two days together, and see if that period was 'good'.
Keep doing this, looking at the first three days, then the first four, and so on, until you've checked the period from the first day to the last day.
Next, start at the second day, and repeat the process. Check the period from the second day to the second day, then the second day to the third day, all the way up to the last day.
Keep shifting the starting day forward, one day at a time, and repeat the process of checking all periods until you reach the last day.
Each time you check a period, count how many good days and bad days it contains.
If the period has more good days than bad days, then it's a 'good' period. Note down the length of this 'good' period.
Once you've checked every possible period, look back at all the 'good' periods you noted down, and find the longest one. That's your answer.

Code Implementation

def longest_well_performing_interval_brute_force(hours):
    max_length = 0
    number_of_days = len(hours)

    for start_index in range(number_of_days):

        for end_index in range(start_index, number_of_days):
            # Iterate through all possible intervals

            good_days_count = 0
            bad_days_count = 0

            for day_index in range(start_index, end_index + 1):
                if hours[day_index] > 8:
                    good_days_count += 1
                else:
                    bad_days_count += 1

            # We need to check if this is a 'good' interval
            if good_days_count > bad_days_count:
                interval_length = end_index - start_index + 1
                max_length = max(max_length, interval_length)

    return max_length

Big(O) Analysis

Time Complexity

O(n²) – The provided algorithm iterates through all possible subarrays of the input array of size n. The outer loop determines the starting index of the subarray, which ranges from 0 to n-1. The inner loop determines the ending index of the subarray, ranging from the starting index to n-1. For each subarray, it counts the number of good and bad days. In the worst case, we examine all possible subarrays, resulting in approximately n * (n+1) / 2 comparisons. This simplifies to a time complexity of O(n²).

Space Complexity

O(1) – The described solution iterates through all possible subarrays of the input array. It primarily uses variables to keep track of the current subarray's start and end indices, good/bad day counts, and the maximum length found so far. These variables consume a constant amount of memory regardless of the input array's size (N). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

We're looking for the longest stretch of days where there are more tiring days than non-tiring days. The trick is to transform the problem and use a running total to keep track of whether we're ahead in tiring days.

Here's how the algorithm would work step-by-step:

First, turn the problem into counting positive and negative numbers. Treat tiring days as +1 and non-tiring days as -1.
Now, go through the days and keep a running total. This running total tells us the difference between the number of tiring and non-tiring days so far.
Record the first time each running total appears. If the same total shows up later, it means we've gone in a circle and haven't made progress on the tiring days winning.
For each day, check if the current running total is bigger than any previous total. If it is, we've found a better well-performing interval.
To find the longest interval, look back to where that lower running total first appeared. The difference between that position and the current one is the length of a possible well-performing interval.
Keep track of the longest well-performing interval you've found so far. As you go through each day, update this longest length if you find a better one.
At the end, you'll have the length of the longest stretch where tiring days outnumbered non-tiring days.

Code Implementation

def longest_well_performing_interval(days):
    running_total = 0
    first_seen_total = {0: -1}
    max_interval_length = 0

    for day_index, day in enumerate(days):
        if day > 8:
            running_total += 1
        else:
            running_total -= 1

        #Record the first occurrence of each running total.
        if running_total not in first_seen_total:
            first_seen_total[running_total] = day_index

        #If we find a smaller running total,
        #it means we've found a potentially longer interval.
        for previous_total in sorted(first_seen_total.keys()):
            if running_total > previous_total:

                interval_length = day_index - first_seen_total[previous_total]
                max_interval_length = max(max_interval_length, interval_length)
                break

    return max_interval_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once to calculate the running total. It uses a hash map (or array) to store the first occurrence of each running total, which takes O(1) on average for insertion and lookup. The key step of finding the longest interval involves looking up the previous occurrences of running totals, also taking O(1) on average. Therefore, the overall time complexity is dominated by the single iteration through the input array, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm uses a hash map (or dictionary) to store the first occurrence of each running total. In the worst-case scenario, where the running total is unique for each day, the hash map could store up to N key-value pairs, where N is the number of days. The additional space used by this hash map grows linearly with the input size N. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 since there is no interval to evaluate.
Input array of length 1	Return 0, as a single element cannot form a well-performing interval.
Array with all elements representing days with more tiring hours (all values > 0)	The entire array is a well-performing interval, so return the array's length.
Array with all elements representing days with fewer tiring hours (all values <= 0)	Return 0, as no well-performing interval exists.
Array with alternating tiring and non-tiring days	Prefix sum approach should correctly calculate the longest well-performing interval even with alternating patterns.
Large input array causing potential integer overflow in prefix sum	Use `long` type for prefix sums if the number of days is large, preventing integer overflow.
Input array with very large length, nearing maximum input size.	Verify that memory usage remains acceptable and doesn't exceed reasonable limits (e.g., check the size of auxiliary data structures).
Multiple intervals with the same maximum length.	The algorithm should find the length of one of the longest intervals, not all of them.

Empty or null input array

How to Handle:

Return 0 since there is no interval to evaluate.

Input array of length 1

How to Handle:

Return 0, as a single element cannot form a well-performing interval.

Array with all elements representing days with more tiring hours (all values > 0)

How to Handle:

The entire array is a well-performing interval, so return the array's length.

Array with all elements representing days with fewer tiring hours (all values <= 0)

How to Handle:

Return 0, as no well-performing interval exists.

Array with alternating tiring and non-tiring days

How to Handle:

Prefix sum approach should correctly calculate the longest well-performing interval even with alternating patterns.

Large input array causing potential integer overflow in prefix sum

How to Handle:

Use `long` type for prefix sums if the number of days is large, preventing integer overflow.

Input array with very large length, nearing maximum input size.

How to Handle:

Verify that memory usage remains acceptable and doesn't exceed reasonable limits (e.g., check the size of auxiliary data structures).

Multiple intervals with the same maximum length.

How to Handle:

The algorithm should find the length of *one* of the longest intervals, not all of them.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values in the `hours` array? Can the values be negative?
If there are multiple well-performing intervals of the same longest length, should I return any one of them?
What should I return if there is no well-performing interval (i.e., no sub-array with more values greater than 8 than values less than or equal to 8)?
Can the input array `hours` be empty or null?
By 'well-performing interval', do you mean a *contiguous* subarray of days where the number of days working more than 8 hours is strictly greater than the number of days working 8 hours or less?

Brute Force Solution

Approach

We want to find the longest period where there were more good days than bad days. The simplest way to do this is to just check every possible period and see if it meets the criteria.

Here's how the algorithm would work step-by-step:

Start by looking at the first day, and then check if just that day was a 'good' period.
Then, look at the first two days together, and see if that period was 'good'.
Keep doing this, looking at the first three days, then the first four, and so on, until you've checked the period from the first day to the last day.
Next, start at the second day, and repeat the process. Check the period from the second day to the second day, then the second day to the third day, all the way up to the last day.
Keep shifting the starting day forward, one day at a time, and repeat the process of checking all periods until you reach the last day.
Each time you check a period, count how many good days and bad days it contains.
If the period has more good days than bad days, then it's a 'good' period. Note down the length of this 'good' period.
Once you've checked every possible period, look back at all the 'good' periods you noted down, and find the longest one. That's your answer.

Code Implementation

def longest_well_performing_interval_brute_force(hours):
    max_length = 0
    number_of_days = len(hours)

    for start_index in range(number_of_days):

        for end_index in range(start_index, number_of_days):
            # Iterate through all possible intervals

            good_days_count = 0
            bad_days_count = 0

            for day_index in range(start_index, end_index + 1):
                if hours[day_index] > 8:
                    good_days_count += 1
                else:
                    bad_days_count += 1

            # We need to check if this is a 'good' interval
            if good_days_count > bad_days_count:
                interval_length = end_index - start_index + 1
                max_length = max(max_length, interval_length)

    return max_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, turn the problem into counting positive and negative numbers. Treat tiring days as +1 and non-tiring days as -1.
Now, go through the days and keep a running total. This running total tells us the difference between the number of tiring and non-tiring days so far.
Record the first time each running total appears. If the same total shows up later, it means we've gone in a circle and haven't made progress on the tiring days winning.
For each day, check if the current running total is bigger than any previous total. If it is, we've found a better well-performing interval.
To find the longest interval, look back to where that lower running total first appeared. The difference between that position and the current one is the length of a possible well-performing interval.
Keep track of the longest well-performing interval you've found so far. As you go through each day, update this longest length if you find a better one.
At the end, you'll have the length of the longest stretch where tiring days outnumbered non-tiring days.

Code Implementation

def longest_well_performing_interval(days):
    running_total = 0
    first_seen_total = {0: -1}
    max_interval_length = 0

    for day_index, day in enumerate(days):
        if day > 8:
            running_total += 1
        else:
            running_total -= 1

        #Record the first occurrence of each running total.
        if running_total not in first_seen_total:
            first_seen_total[running_total] = day_index

        #If we find a smaller running total,
        #it means we've found a potentially longer interval.
        for previous_total in sorted(first_seen_total.keys()):
            if running_total > previous_total:

                interval_length = day_index - first_seen_total[previous_total]
                max_interval_length = max(max_interval_length, interval_length)
                break

    return max_interval_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 since there is no interval to evaluate.
Input array of length 1	Return 0, as a single element cannot form a well-performing interval.
Array with all elements representing days with more tiring hours (all values > 0)	The entire array is a well-performing interval, so return the array's length.
Array with all elements representing days with fewer tiring hours (all values <= 0)	Return 0, as no well-performing interval exists.
Array with alternating tiring and non-tiring days	Prefix sum approach should correctly calculate the longest well-performing interval even with alternating patterns.
Large input array causing potential integer overflow in prefix sum	Use `long` type for prefix sums if the number of days is large, preventing integer overflow.
Input array with very large length, nearing maximum input size.	Verify that memory usage remains acceptable and doesn't exceed reasonable limits (e.g., check the size of auxiliary data structures).
Multiple intervals with the same maximum length.	The algorithm should find the length of one of the longest intervals, not all of them.

Empty or null input array

How to Handle:

Return 0 since there is no interval to evaluate.

Input array of length 1

How to Handle:

Return 0, as a single element cannot form a well-performing interval.

Array with all elements representing days with more tiring hours (all values > 0)

How to Handle:

The entire array is a well-performing interval, so return the array's length.

Array with all elements representing days with fewer tiring hours (all values <= 0)

How to Handle:

Return 0, as no well-performing interval exists.

Array with alternating tiring and non-tiring days

How to Handle:

Prefix sum approach should correctly calculate the longest well-performing interval even with alternating patterns.

Large input array causing potential integer overflow in prefix sum

How to Handle:

Use `long` type for prefix sums if the number of days is large, preventing integer overflow.

Input array with very large length, nearing maximum input size.

How to Handle:

Verify that memory usage remains acceptable and doesn't exceed reasonable limits (e.g., check the size of auxiliary data structures).

Multiple intervals with the same maximum length.

How to Handle:

The algorithm should find the length of *one* of the longest intervals, not all of them.