Problem statement

It is Diwali, and a row of diyas lines the balcony. brightness[i] is how brightly the i-th diya burns.

Your camera frame fits exactly k consecutive diyas. Return the largest total brightness any one photo can capture.

Example 1

Input: brightness = [3,1,4,1,5,9,2], k = 3
Output: 16
Explanation: Sliding the frame along gives 8, 6, 10, 15 and finally 16, over `[5,9,2]`: no other three neighbours burn brighter together.

Example 2

Input: brightness = [7,7,7], k = 3
Output: 21
Explanation: The frame holds the whole row.

Example 3

Input: brightness = [0,8,0,0,6], k = 1
Output: 8
Explanation: With room for one diya, pick the brightest.

Constraints

• 1 <= k <= brightness.length <= 10^5
• 0 <= brightness[i] <= 10^4

Hints for Brightest String of Diyas

1. Hint 1

   Adding up every frame from scratch costs k steps a frame. What changes when the frame moves one diya to the right?

2. Hint 2

   Exactly one diya enters on the right and one leaves on the left — every diya in between is shared by both frames.

3. Hint 3

   Keep the frame's running total: add the new diya, subtract the one that left, and remember the best total seen.

How to solve Brightest String of Diyas

Neighbouring frames share all but two diyas, so slide one window of size k across the row and update its sum in O(1) per step instead of re-adding k numbers.

Approach

1. Sum the first k diyas; that is the first frame and the best so far.
2. For each i from k to the end: add brightness[i], subtract brightness[i - k].
3. After each step, keep the larger of the best and the current sum.

Why it works

Every frame of k consecutive diyas starts at some index 0 … n - k, and the loop visits each start exactly once; the running sum equals that frame's total because it adds the one diya entering and removes the one leaving.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Start best at the first frame's sum, not at 0 — that is only safe here because brightness is never negative.
• Subtract brightness[i - k], not brightness[i - k + 1]: the diya leaving is the one k places back.

Reference solution

Python

from typing import List

def brightestStretch(brightness: List[int], k: int) -> int:
    total = sum(brightness[:k])
    best = total
    for i in range(k, len(brightness)):
        total += brightness[i] - brightness[i - k]
        best = max(best, total)
    return best

Java

public static int brightestStretch(int[] brightness, int k) {
    int total = 0;
    for (int i = 0; i < k; i++) total += brightness[i];
    int best = total;
    for (int i = k; i < brightness.length; i++) {
        total += brightness[i] - brightness[i - k];
        if (total > best) best = total;
    }
    return best;
}

C++

int brightestStretch(vector<int>& brightness, int k) {
    int total = 0;
    for (int i = 0; i < k; i++) total += brightness[i];
    int best = total;
    for (int i = k; i < (int) brightness.size(); i++) {
        total += brightness[i] - brightness[i - k];
        if (total > best) best = total;
    }
    return best;
}

JavaScript

var brightestStretch = function(brightness, k) {
    var total = 0;
    for (var i = 0; i < k; i++) total += brightness[i];
    var best = total;
    for (var j = k; j < brightness.length; j++) {
        total += brightness[j] - brightness[j - k];
        if (total > best) best = total;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy
• Convert Sorted Array to Binary Search Tree Easy