Is Longest Well-Performing Interval easy or hard?

Longest Well-Performing Interval is classified as a Medium difficulty problem. The challenge comes from recognizing the prefix sum transformation that converts the problem into finding a longest subarray with positive cumulative score.

Longest Well-Performing Interval Python/Java solution

Python, Java, C++, C#, and JavaScript implementations typically follow the Prefix Sum + HashMap strategy. Convert the hours array into +1/-1 values, compute prefix sums while iterating, and use a map to track the earliest occurrence of each prefix sum to update the maximum interval length.

How to solve Longest Well-Performing Interval in O(n)?

Transform the array so days with hours > 8 become +1 and others become -1. Maintain a running prefix sum while iterating. If the prefix sum is positive, the interval from the start is valid; otherwise check if prefixSum - 1 occurred earlier using a hash map to maximize interval length.

What is the best approach for Longest Well-Performing Interval?

The most common solution uses Prefix Sum with a HashMap in O(n) time and O(n) space. Convert each day to +1 if hours > 8 and -1 otherwise, then maintain a running prefix sum. If the prefix sum is positive, the entire range is valid. Otherwise check if prefixSum - 1 appeared earlier to form a valid interval.

Is Longest Well-Performing Interval asked at Google/Amazon/Meta?

This problem represents a common interview pattern involving prefix sums and subarray scoring. Variations of the problem appear in interviews at companies like Amazon, Google, and Meta because it tests understanding of prefix transformations, hash maps, and range queries.

What data structure is used in Longest Well-Performing Interval?

The optimal solution uses a HashMap to store the earliest index of each prefix sum value. Another efficient variant uses a monotonic stack built from prefix sums to locate earlier smaller values that produce positive intervals.

What is the time complexity of Longest Well-Performing Interval?

The optimal solutions run in O(n) time where n is the number of days. Both the Prefix Sum + HashMap method and the Monotonic Stack approach scan the array once and perform constant-time operations per element. Space complexity is O(n) due to storing prefix indices.

Description Hints 2 Solution Video 8:09

1124. Longest Well-Performing Interval

Medium38.5% acceptance2 companies

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

Asked at 2 companies

Infosys NetApp

Topics

Hints open one at a time

Hint 1

Make a new array A of +1/-1s corresponding to if hours[i] is > 8 or not. The goal is to find the longest subarray with positive sum.

Hint 2

Using prefix sums (PrefixSum[i+1] = A[0] + A[1] + ... + A[i]), you need to find for each j, the smallest i < j with PrefixSum[i] + 1 == PrefixSum[j].

8:09

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def longestWPI(self, hours: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[9,9,6,0,6,6,9]

Input

[6,6,6]

Your code is saved on this device.Solution