Visualize LeetCode 644 step by step. Watch binary search narrow the answer on the average, then a sliding window feasibility check verify each candidate.
Instead of searching for a value in the array, binary search on the ANSWER: the maximum achievable average. lo = min(array), hi = max(array). We narrow this range until |hi − lo| < ε.
For each candidate average `mid`, subtract `mid` from every element to get a transformed array. If any subarray of length ≥ k in the transformed array has sum ≥ 0, then avg ≥ mid is achievable.
To check subarrays of length ≥ k efficiently: maintain a sliding window sum and a prefix minimum (min sum of any prefix ending at position i−k). If windowSum − minPrev ≥ 0, a valid subarray exists. O(N) per check.
O(N × log((max−min)/ε)) ≈ O(N × 50) for typical inputs. Each feasibility check is O(N) and we do about log((max−min)/1e-5) ≈ 50 binary search iterations.
R = (max−min)/ε is the precision range. For integers in [1,10000] with ε=1e-5, this is about log2(10^9) ≈ 30 iterations.