Skip to main content
Talentd

Longest Well-Performing Interval - Solution & Explanation

MediumArrayHash TableStackMonotonic Stack17 min readAsked at: Infosys, NetApp
Practice this problem

Problem Statement

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 <= 104
  • 0 <= hours[i] <= 16

Approach Overview

Problem Overview: You are given an array hours where each value represents hours worked that day. A day is tiring if hours[i] > 8. The goal is to find the length of the longest subarray where tiring days strictly outnumber non‑tiring days.

Approach 1: Prefix Sum with HashMap (Time: O(n), Space: O(n))

Convert the problem into a prefix score problem. Treat a tiring day (> 8) as +1 and a non‑tiring day as -1. Now the task becomes finding the longest subarray with a positive sum. Maintain a running prefixSum while iterating through the array. If prefixSum > 0, the entire range from index 0 to i is valid. Otherwise, check if the value prefixSum - 1 appeared earlier. If it did, the subarray between that earlier index and the current index has a positive total. A HashMap stores the first occurrence of each prefix sum so lookups are constant time. This approach uses the classic prefix sum transformation combined with a hash table for earliest index tracking. The key insight is that if prefixSum[j] - prefixSum[i] > 0, then the interval (i, j] has more tiring days than non‑tiring days.

Approach 2: Two Pointers with Stack Simulation (Time: O(n), Space: O(n))

This method also starts by converting the input into a +1 and -1 sequence and computing prefix sums. Instead of a hash map, build a decreasing stack of prefix indices. While scanning from left to right, push an index onto the stack only if its prefix sum is smaller than the prefix sum at the current stack top. This produces a monotonic structure that records potential starting positions. Then iterate from right to left and try to extend intervals: while the current prefix sum is greater than the prefix sum at the stack's top index, pop it and update the interval length. Each index is pushed and popped at most once, giving linear time complexity. This technique leverages a monotonic stack to efficiently locate earlier smaller prefix sums that produce positive intervals.

Recommended for interviews: The Prefix Sum + HashMap solution is usually expected in interviews. It directly models the condition of "more tiring than non‑tiring days" using numeric transformation and constant‑time lookups. Interviewers often want to see the prefix sum insight first, then the observation that storing the earliest index maximizes interval length. The monotonic stack variant is equally optimal but slightly less obvious, making it useful as an alternative when discussing O(n) prefix‑based range problems.

Approach 1: Approach 1: Prefix Sum with HashMap

This approach uses a prefix sum combined with a hashmap to find the longest well-performing interval. Transform the hours array into +1 for tiring days and -1 for non-tiring days. Calculate the prefix sum and use a hashmap to store the first occurrence of each prefix sum value. This helps in quickly determining the length of intervals where tiring days exceed non-tiring days.

We start by initializing a prefix sum to zero and an empty hashmap. We iterate over the hours and update the prefix sum by adding 1 for tiring days or subtracting 1 otherwise. If the prefix sum is positive, it means all days up to the current day form a well-performing interval. If not, we look for previous occurrences of prefix sum - 1 in the hashmap, which, if found, indicates a valid interval ending at the current day. We track the first occurrence of each prefix sum to efficiently find longer intervals.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the number of days, since we traverse the list once.
Space Complexity: O(n) due to the hashmap storing prefix sums.

Try this approach in the editor →

Approach 2: Approach 2: Two Pointers with Stack Simulation

This approach uses a two-pointer technique in tandem with a stack-like simulation (monotonic stack) for efficiently checking conditions. We transform hours into +1/-1 representation and then utilize two pointers to directly seek the longest interval with more tiring days than non-tiring ones.

This Python solution first converts 'hours' into +1/-1. We then use a variable 'accumulated' to keep track of intervals and a stack to store indices where 'accumulated' becomes less optimal.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(n^2) for the worst case due to double iteration with the stack.
Space Complexity: O(n) since stack can store up to n-1 indices.

Try this approach in the editor →

Approach 3: 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.

Next, we traverse the hours array, for each index i:

  • If hours[i] > 8, we increment s by 1, otherwise we decrement s by 1.
  • If s > 0, it means that the segment from index 0 to the current index i is a "well-performing time period", we update the result ans = i + 1. Otherwise, if s - 1 is in the hash table pos, let j = pos[s - 1], it means that the segment from index j + 1 to the current index i is a "well-performing time period", we update the result ans = max(ans, i - j).
  • Then, if s is not in the hash table pos, we record pos[s] = i.

After the traversal, return the answer.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the hours array.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Prefix Sum with HashMap

Time Complexity: O(n) where n is the number of days, since we traverse the list once.
Space Complexity: O(n) due to the hashmap storing prefix sums.

Approach 2: Two Pointers with Stack Simulation

Time Complexity: O(n^2) for the worst case due to double iteration with the stack.
Space Complexity: O(n) since stack can store up to n-1 indices.

Prefix Sum + Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix Sum with HashMapO(n)O(n)General case. Most intuitive optimal solution for interviews.
Two Pointers with Monotonic StackO(n)O(n)When using prefix sums with monotonic structures to find earlier smaller values.

Video Solution

LeetCode 1124 | Longest Well Performing Interval | Algorithm Explained (Java + Whiteboard) • Xavier Elon • 6,052 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Longest Well-Performing Interval with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays