Maximum Brightness Window

mediumFREESliding WindowSliding Window, DequeCV - DSA

Problem Statement

In image analysis, we often need to find the brightest region of a fixed size. Given a 1D array of pixel intensities and a window size k, find the maximum value in each sliding window position.

This is equivalent to applying a max filter (dilation in morphological operations).

Applications

Feature detection (finding local maxima)
Morphological dilation
Finding brightest regions for exposure adjustment

Constraints

$1 \leq len(pixels) \leq 10000$
$1 \leq k \leq len(pixels)$
$0 \leq pixels[i] \leq 255$

Example

Input

pixels = [1, 3, 2, 5, 4, 1, 3], k = 3

Output

[3, 5, 5, 5, 4]

Reasoning

Input: pixels is a row of 7 intensities $p_0,\dots,p_6 = 1, 3, 2, 5, 4, 1, 3$ (each in $0$ to $255$ ), and k $= 3$ is the width of the window that slides one pixel at a time.
How many windows: a window of width $k$ fits in $n - k + 1 = 7 - 3 + 1 = 5$ positions, so the output has 5 numbers. Window $j$ covers pixels $p_j, p_{j+1}, p_{j+2}$ .
Math: each output is $m_j = \max(p_j, p_{j+1}, p_{j+2})$ $m_{j} = max (p_{j}, p_{j + 1}, p_{j + 2})$ :
- $j=0$ : $\max(1,3,2) = 3$
- $j=1$ : $\max(3,2,5) = 5$
- $j=2$ : $\max(2,5,4) = 5$
- $j=3$ : $\max(5,4,1) = 5$
- $j=4$ : $\max(4,1,3) = 4$
Output: [3, 5, 5, 5, 4], the max-filtered (dilated) signal. Notice the bright pixel $5$ at index 3 wins every window that contains it (three of them), so one bright spot spreads across $k$ outputs, exactly what dilation does. Once it leaves, the answer drops to $4$ , not to the newly entered $3$ .

Learn this in

Patterns & MiscellaneousDSA Study Plan Two Pointers & Sliding WindowDSA Study Plan

More from CV - DSA

Concept primer

1. Background Knowledge

The Maximum Brightness Window problem involves computing the maximum value in every contiguous subarray (window) of size k in a 1D array of pixel intensities. This is a 1D max filter or sliding window maximum, fundamental in image processing for tasks like morphological dilation, local feature detection, and identifying brightest regions for exposure correction.

Key prerequisites:

Sliding window concept: For array pixels of length n, output an array of length n-k+1 where result[i] = max(pixels[i..i+k-1]).
Mathematical notation: Given $pixels = [p_0, p_1, \dots, p_{n-1}]$ , compute $result[i] = \max_{j=i}^{i+k-1} p_j$ for $i = 0$ to $n-k$ .
Relevance to ML/AI: Used in preprocessing for feature extraction (e.g., edge detection) and CNN input normalization.

2. Algorithm Approach

Common techniques range from naive to optimized:

Approach	Description	Time Complexity
Naive	For each window, scan all k elements	O(nk) – Fine for small k, but O(n²) worst-case
Deque (Sliding Window Maximum)	Maintain deque of indices with decreasing values; front always holds max. Amortized O(1) per window	O(n) – Optimal and standard
Sparse Table	Precompute log-spaced max queries	O(n log n) preprocess, O(1) query
Segment Tree	Build tree for range max queries	O(n) build, O(log n) query

Recommended: Deque method – Efficient for constraints ( $n \leq 10^4$ ), space-optimal.

3. Step-by-Step Strategy

Initialize deque to store indices (not values) in decreasing order of pixels[index].
For first k-1 elements:

While deque back < current pixels[i], pop back.
Push current index i.

For remaining windows i = k-1 to n-1:

Result: Deque front is max for window ending at i.
Remove elements out of current window (if deque.front() <= i-k).
Clean deque back: Pop while pixels[deque.back()] < pixels[i].
Push i.

Return result array of length n-k+1.

Python Example (Deque):

from collections import deque

def max_brightness_window(pixels: list[int], k: int) -> list[int]:
 if not pixels or k > len(pixels):
 return []
 dq = deque()
 result = []

 # First window
 for i in range(k):
 while dq and pixels[dq[-1]] <= pixels[i]:
 dq.pop()
 dq.append(i)

 result.append(pixels[dq])

 # Sliding windows
 for i in range(k, len(pixels)):
 # Remove out-of-window
 if dq and dq == i - k:
 dq.popleft()

 # Maintain decreasing order
 while dq and pixels[dq[-1]] <= pixels[i]:
 dq.pop()
 dq.append(i)

 result.append(pixels[dq])

 return result

Verification Example:

pixels = [1,3,-1,-3,5,3,6,7], k=3
→ [3,3,5,5,6,7]

4. Common Pitfalls

Off-by-one errors: Ensure deque front is always valid (i - k + 1 <= front <= i); handle edge cases (k=1, k=n).
Strict inequality in deque: Use <= to handle duplicates, preventing stale indices.
Empty input/k > n: Return empty list.
Mutable deque misuse: Always use indices, not values, for window tracking.
Naive O(nk) timeout: Fails for n=10^4, k=5000; always prefer deque.

5. Time & Space Complexity

Optimal Deque: $O(n)$ time (each index pushed/popped at most once), $O(k)$ space (deque size ≤ k).
Why optimal? Cannot do better than O(n) as must read all elements; matches constraints perfectly.
Trade-offs:

Method	Time	Space	Best For
Deque	O(n)	O(k)	Online streaming
Sparse Table	O(n log n)	O(n log n)	Static queries

This approach scales to real-time image processing pipelines.

solution.py

Python 3.13

Test results