MediumNo. 1124

Longest Well-Performing Interval — LeetCode 1124 Python Solution

Pattern
Prefix Sum
Topics
Stack, Array, Hash Table, Prefix Sum, Monotonic Stack
Reading time
2 min

The problem

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.

Example

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

Python solution

PythonSolution
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

Complexity

Time
O(n)
Space · auxiliary
O(n)

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 1124. Longest Well-Performing Interval is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0496Next Greater Element IEasy
0523Continuous Subarray SumMedium
0525Contiguous ArrayMedium
0560Subarray Sum Equals KMedium
0930Binary Subarrays With SumMedium
0974Subarray Sums Divisible by KMedium

Frequently asked questions

How hard is LeetCode 1124. Longest Well-Performing Interval?

LeetCode 1124. Longest Well-Performing Interval is rated Medium on LeetCode.

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

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1124. Longest Well-Performing Interval?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1124. Longest Well-Performing Interval cover?

LeetCode 1124. Longest Well-Performing Interval is tagged Stack, Array, Hash Table, Prefix Sum and Monotonic Stack on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.