#1124

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Longest Well-Performing Interval

The Longest Well-Performing Interval problem challenges you to find the longest subarray where tiring days exceed non-tiring ones.

array hash table stack monotonic stack prefix sum

Problem Statement

You are given a list of hours worked per day for an employee. A day is considered tiring if the number of hours worked exceeds 8 hours. Your task is to determine the length of the longest subarray where the number of tiring days outnumbers the non-tiring days. The list contains the hours worked each day, and you need to find the longest subarray with a positive sum of tiring days.

A well-performing interval is a subarray where the number of tiring days is strictly greater than the non-tiring days. The key to solving this problem is efficiently identifying and counting such intervals within the given array.

Examples

Example 1

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

Output: 3

The longest well-performing interval is [9,9,6].

Example 2

Input: hours = [6,6,6]

Output: 0

Example details omitted.

Constraints

1 <= hours.length <= 104
0 <= hours[i] <= 16

Solution Approach

Transform hours to +1/-1

Create a new array by converting the hours array into +1 for tiring days (hours > 8) and -1 for non-tiring days. This transformation simplifies the problem into finding the longest subarray with a positive sum.

Track prefix sums with a hash map

Use a hash map to store the first occurrence of each prefix sum while iterating through the array. The key insight is that if the prefix sum at two different indices is the same, the subarray between those indices has a sum of zero, and you can then check for the longest valid subarray.

Efficiently find the longest subarray

Iterate through the transformed array, update the prefix sum, and check if the current sum has been seen before. If it has, calculate the length of the subarray between the current and previous indices. Track the maximum length of these subarrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n), where n is the length of the hours array. The space complexity is O(n) due to the storage of prefix sums in the hash map.

What Interviewers Usually Probe

Can the candidate effectively convert the problem into an array of +1/-1 values?
Does the candidate demonstrate understanding of prefix sum and hash map techniques?
Is the candidate able to optimize the solution by tracking previous sums and finding the longest subarray?

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the conversion to +1/-1 for tiring and non-tiring days.
Overcomplicating the solution without utilizing the prefix sum approach and hash map efficiently.
Missing the fact that the problem requires finding a subarray with a positive sum rather than simply counting tiring days.

Follow-up variants

Handling edge cases where there are no tiring days.
Exploring variations where you are asked to find the shortest subarray with a positive sum.
Solving the problem with a different data structure like a stack to manage sums.

FAQ

What is the key approach for solving Longest Well-Performing Interval?

The solution involves converting hours worked into +1/-1 values and finding the longest subarray with a positive sum using prefix sums and hash lookups.

How does the prefix sum technique apply to this problem?

The prefix sum technique helps efficiently track the cumulative sum as you iterate, allowing you to identify the longest well-performing subarray by comparing prefix sums at different indices.

What are common mistakes when solving the Longest Well-Performing Interval?

Common mistakes include not correctly converting the array into +1/-1 values or failing to utilize the prefix sum approach effectively.

How does hash map improve the performance of the solution?

Hash maps allow you to quickly check for previously seen prefix sums, enabling constant-time lookup and reducing the time complexity to O(n).

What other data structures can be used for this problem?

While hash maps are optimal, a stack-based approach can also be used to track prefix sums and manage subarrays, but it may be less efficient.

terminal

Solution

Solution 1: Prefix Sum + Hash Table

We can use the idea of prefix sum, maintaining a variable $s$, which represents the difference between the number of "tiring days" and "non-tiring days" from index $0$ to the current index. If $s$ is greater than $0$, it means that the segment from index $0$ to the current index is a "well-performing time period". In addition, we use a hash table $pos$ to record the first occurrence index of each $s$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        ans = s = 0
        pos = {}
        for i, x in enumerate(hours):
            s += 1 if x > 8 else -1
            if s > 0:
                ans = i + 1
            elif s - 1 in pos:
                ans = max(ans, i - pos[s - 1])
            if s not in pos:
                pos[s] = i
        return ans

Continue Practicing

#496 next greater element i #1130 minimum cost tree from leaf values #1074 number of submatrices that sum to target