1124. Longest Well-Performing Interval Solution

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.

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

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.

Python

def longest_wpi(hours):
    prefix_sum = 0
    longest = 0
    prefix_map = {}
    for i, hour in enumerate(hours):
        prefix_sum += 1 if hour > 8 else -1
        if prefix_sum > 0:
            longest = i + 1
        elif prefix_sum - 1 in prefix_map:
            longest = max(longest, i - prefix_map[prefix_sum - 1])
        if prefix_sum not in prefix_map:
            prefix_map[prefix_sum] = i
    return longest

Java

import java.util.HashMap; 

public class Main {
    public int longestWPI(int[] hours) {
        int prefix_sum = 0, longest = 0;
        HashMap<Integer, Integer> prefix_map = new HashMap<>();
        for (int i = 0; i < hours.length; i++) {
            prefix_sum += (hours[i] > 8) ? 1 : -1;
            if (prefix_sum > 0) {
                longest = i + 1;
            } else if (prefix_map.containsKey(prefix_sum - 1)) {
                longest = Math.max(longest, i - prefix_map.get(prefix_sum - 1));
            }
            prefix_map.putIfAbsent(prefix_sum, i);
        }
        return longest;
    }
    public static void main(String[] args) {
        Main obj = new Main();
        System.out.println(obj.longestWPI(new int[]{9, 9, 6, 0, 6, 6, 9})); // Output: 3
    }
}

C++

#include <vector>
#include <unordered_map>
using namespace std;

int longestWPI(vector<int>& hours) {
    int prefix_sum = 0, longest = 0;
    unordered_map<int, int> prefix_map;
    for (int i = 0; i < hours.size(); ++i) {
        prefix_sum += (hours[i] > 8) ? 1 : -1;
        if (prefix_sum > 0) {
            longest = i + 1;
        } else if (prefix_map.find(prefix_sum - 1) != prefix_map.end()) {
            longest = max(longest, i - prefix_map[prefix_sum - 1]);
        }
        if (prefix_map.find(prefix_sum) == prefix_map.end()) {
            prefix_map[prefix_sum] = i;
        }
    }
    return longest;
}

JavaScript

function longestWPI(hours) {
    let prefix_sum = 0, longest = 0;
    const prefix_map = new Map();
    for (let i = 0; i < hours.length; i++) {
        prefix_sum += (hours[i] > 8) ? 1 : -1;
        if (prefix_sum > 0) {
            longest = i + 1;
        } else if (prefix_map.has(prefix_sum - 1)) {
            longest = Math.max(longest, i - prefix_map.get(prefix_sum - 1));
        }
        if (!prefix_map.has(prefix_sum)) {
            prefix_map.set(prefix_sum, i);
        }
    }
    return longest;
}
console.log(longestWPI([9, 9, 6, 0, 6, 6, 9])); // Output: 3

using System;
using System.Collections.Generic;

class Program {
    public static int LongestWPI(int[] hours) {
        int prefix_sum = 0, longest = 0;
        Dictionary<int, int> prefix_map = new Dictionary<int, int>();
        for (int i = 0; i < hours.Length; i++) {
            prefix_sum += (hours[i] > 8) ? 1 : -1;
            if (prefix_sum > 0) {
                longest = i + 1;
            } else if (prefix_map.ContainsKey(prefix_sum - 1)) {
                longest = Math.Max(longest, i - prefix_map[prefix_sum - 1]);
            }
            if (!prefix_map.ContainsKey(prefix_sum)) {
                prefix_map[prefix_sum] = i;
            }
        }
        return longest;
    }
    static void Main() {
        Console.WriteLine(LongestWPI(new int[] { 9, 9, 6, 0, 6, 6, 9 })); // Output: 3
    }
}

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.

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.

Python

def longest_wpi(hours):
    transformed = [1 if h > 8 else -1 for h in hours]
    accumulated = 0
    longest = 0
    stack = []

    for i in range(len(transformed)):
        accumulated += transformed[i]
        if accumulated > 0:
            longest = max(longest, i + 1)
        for idx in stack:
            if accumulated - (idx if idx < i else 0) > 0:
                longest = max(longest, i - idx)
        if not stack or accumulated < stack[-1]:
            stack.append(i)

    return longest

Java

import java.util.Stack;

public class Main {
    public int longestWPI(int[] hours) {
        int[] transformed = new int[hours.length];
        for (int i = 0; i < hours.length; i++)
            transformed[i] = (hours[i] > 8) ? 1 : -1;
        int accumulated = 0, longest = 0;
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < transformed.length; i++) {
            accumulated += transformed[i];
            if (accumulated > 0)
                longest = Math.max(longest, i + 1);
            for (int idx : stack)
                if (accumulated - (idx < i ? idx : 0) > 0)
                    longest = Math.max(longest, i - idx);
            if (stack.isEmpty() || accumulated < stack.peek())
                stack.push(i);
        }
        return longest;
    }
    public static void main(String[] args) {
        Main obj = new Main();
        System.out.println(obj.longestWPI(new int[]{9, 9, 6, 0, 6, 6, 9})); // Output: 3
    }
}

C++

#include <vector>
#include <stack>
using namespace std;

int longestWPI(vector<int>& hours) {
    vector<int> transformed(hours.size());
    for (int i = 0; i < hours.size(); ++i)
        transformed[i] = (hours[i] > 8) ? 1 : -1;
    int accumulated = 0, longest = 0;
    stack<int> s;

    for (int i = 0; i < transformed.size(); ++i) {
        accumulated += transformed[i];
        if (accumulated > 0)
            longest = max(longest, i + 1);
        for (auto idx : s)
            if (accumulated - (idx < i ? idx : 0) > 0)
                longest = max(longest, i - idx);
        if (s.empty() || accumulated < s.top())
            s.push(i);
    }
    return longest;
}

JavaScript

function longestWPI(hours) {
    const transformed = hours.map(h => (h > 8 ? 1 : -1));
    let accumulated = 0;
    let longest = 0;
    const stack = [];

    for (let i = 0; i < transformed.length; i++) {
        accumulated += transformed[i];
        if (accumulated > 0) {
            longest = Math.max(longest, i + 1);
        }
        for (let j = 0; j < stack.length; j++) {
            let idx = stack[j];
            if (accumulated - (idx < i ? idx : 0) > 0) {
                longest = Math.max(longest, i - idx);
            }
        }
        if (!stack.length || accumulated < stack[stack.length - 1]) {
            stack.push(i);
        }
    }
    return longest;
}
console.log(longestWPI([9, 9, 6, 0, 6, 6, 9])); // Output: 3

using System;
using System.Collections.Generic;

class Program {
    public static int LongestWPI(int[] hours) {
        int[] transformed = new int[hours.Length];
        for (int i = 0; i < hours.Length; i++)
            transformed[i] = (hours[i] > 8) ? 1 : -1;
        int accumulated = 0, longest = 0;
        Stack<int> stack = new Stack<int>();

        for (int i = 0; i < transformed.Length; i++) {
            accumulated += transformed[i];
            if (accumulated > 0)
                longest = Math.Max(longest, i + 1);
            foreach (int idx in stack)
                if (accumulated - (idx < i ? idx : 0) > 0)
                    longest = Math.Max(longest, i - idx);
            if (stack.Count == 0 || accumulated < stack.Peek())
                stack.Push(i);
        }
        return longest;
    }
    static void Main() {
        Console.WriteLine(LongestWPI(new int[] {9, 9, 6, 0, 6, 6, 9})); // Output: 3
    }
}

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.

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.

func longestWPI(hours []int) (ans int) {
	s := 0
	pos := map[int]int{}
	for i, x := range hours {
		if x > 8 {
			s++
		} else {
			s--
		}
		if s > 0 {
			ans = i + 1
		} else if j, ok := pos[s-1]; ok {
			ans = max(ans, i-j)
		}
		if _, ok := pos[s]; !ok {
			pos[s] = i
		}
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
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	–

Complexity analysis

Approach	Time	Space	When to Use
Prefix Sum with HashMap	O(n)	O(n)	General case. Most intuitive optimal solution for interviews.
Two Pointers with Monotonic Stack	O(n)	O(n)	When using prefix sums with monotonic structures to find earlier smaller values.

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.

Longest Well-Performing Interval solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Prefix Sum with HashMap

Approach 2: Approach 2: Two Pointers with Stack Simulation

Approach 3: Prefix Sum + Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Longest Well-Performing Interval solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Prefix Sum with HashMap

Approach 2: Approach 2: Two Pointers with Stack Simulation

Approach 3: Prefix Sum + Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems