What is the brute force approach and complexity for Longest Well-Performing Interval?

Fix each start, grow the end with a running ±1 score, check score > 0 with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Longest Well-Performing Interval?

If score > 0 take the whole prefix; else pair with the first index of score − 1 with optimal time complexity O(N) and space complexity O(N).

Longest Well-Performing Interval

Q: How do you identify the pattern for Longest Well-Performing Interval?

Look for key signals in the prompt: "interval of consecutive days" indicates A contiguous range → prefix sums or a window.; "more than 8 hours / strictly more tiring days" indicates Only two kinds of days → +1 / −1 transform. "Strictly more" means sum > 0, not = 0.; "longest" indicates Pair each end with the earliest valid start → store the first index of each score.; "values move by ±1" indicates The prefix cannot skip values, so the earliest smaller prefix is always at score − 1..

Medium·LeetCode #1124 Pro OnlyTricky / Edge Case

LeetCode

Problem Statement

You are given hours, where hours[i] is how many hours someone worked on day i.

A day is tiring if they worked more than 8 hours. An interval of consecutive days is well-performing if it has strictly more tiring days than non-tiring days.

Return the length of the longest well-performing interval (0 if there is none).

Input

An integer array hours.

Output

The length of the longest interval of consecutive days with more tiring days than non-tiring days.

Example 1

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

Output: 3

[9, 9, 6] has 2 tiring days and 1 non-tiring day. No longer interval has more tiring days.

Example 2

Input: hours = [6, 6, 6]

Output: 0

No day is tiring, so no interval can have more tiring days.

Constraints

• 1 ≤ hours.length ≤ 10^4
• 0 ≤ hours[i] ≤ 16

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“interval of consecutive days”

→ A contiguous range → prefix sums or a window.

“more than 8 hours / strictly more tiring days”

→ Only two kinds of days → +1 / −1 transform. "Strictly more" means sum > 0, not = 0.

“longest”

→ Pair each end with the earliest valid start → store the first index of each score.

“values move by ±1”

→ The prefix cannot skip values, so the earliest smaller prefix is always at score − 1.

Approach Complexity Ladder

Brute Force — try every startO(N²)O(1)

Fix each start, grow the end with a running ±1 score, check score > 0

Optimal — prefix score + first index of score − 1O(N)O(N)

If score > 0 take the whole prefix; else pair with the first index of score − 1

Brute Force Intuition

For every start day, walk the end to the right. Keep a running score (+1 for a tiring day, −1 otherwise). Whenever the score is above 0, the interval has more tiring days, so update the best length.

Recognition rule for this sub-pattern:

Turn values into +1/−1 (or bit flags) so "balanced" means "same prefix state seen before". Store the first index of each state.

Remember this · Prefix Sum

Trigger

Range sums, "subarray sum equals K" (especially with negatives), equal counts, divisible by K.

Think

If I knew the total up to every index, would the answer become a difference of two totals?

Key question

Which earlier prefix value am I looking for when I stand at index i?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Prefix Sum translate into production architectures and low-level memory mechanics.

LLD Architecture