Maximum Brightness Window

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:

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

3. Step-by-Step Strategy

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

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

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

4. 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:

This approach scales to real-time image processing pipelines.