0264MediumArrayBinary Search

Solar String Commissioning

Tracked in this browser only

Trains the technique from

LeetCode 1482Minimum Number of Days to Make m Bouquets

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A solar field is built as one long row of panels. readyDay[i] is the day panel i is energised; the panel carries nothing before that day and stays energised from that day onwards.

The field is commissioned in strings. A string is k panels that sit next to each other in the row and are all energised, and a panel may be wired into at most one string.

Return the earliest day on which m strings can be picked out of the row at once. If the row can never supply m strings, return -1. Every readyDay[i] is at least 1, so -1 cannot be confused with a real day.

Examples

Example 1

Input: readyDay = [4, 1, 5, 1, 4, 4], m = 2, k = 2
Output: 4

On day 4 the only panel still dark is panel 2, so panels 0 and 1 make one string and panels 3 and 4 make the other, leaving panel 5 spare.

Example 2

Input: readyDay = [1, 8, 2, 2, 6], m = 1, k = 2
Output: 2

Panels 2 and 3 are both energised on day 2 and sit next to each other, which is the one string the field asks for.

Example 3

Input: readyDay = [2, 3], m = 2, k = 2
Output: -1

Two strings of two panels would take four panels in all and the row holds only two, so no day supplies them.

Constraints

readyDay.length == n
1 <= n <= 10^5
1 <= readyDay[i] <= 10^9
1 <= m <= 10^6
1 <= k <= n

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def earliest_commission_day(readyDay: list[int], m: int, k: int) -> int:

Java

public int earliestCommissionDay(int[] readyDay, int m, int k)

The intended approach

Time O(n log D), where D is the spread between the earliest and latest energising daySpace O(1)

Panels never go dark, so if `m` strings can be picked on some day they can be picked on every later day too; the days therefore split into a failing lower part and a succeeding upper part, and the answer is the first day of the upper part. Testing one day is a single linear walk that grows a run over energised panels and closes a string each time the run reaches `k`, resetting the run to zero so no panel is wired twice. The code binary searches the day range between the earliest and the latest energising day with that test, after settling the hopeless case where `m * k` is larger than the number of panels.

Pythonentry point: earliest_commission_day

def earliest_commission_day(readyDay, m, k):
    n = len(readyDay)
    if m * k > n:
        return -1

    def strings_by(day):
        made = 0
        run = 0
        for value in readyDay:
            if value <= day:
                run += 1
                if run == k:
                    made += 1
                    run = 0
                    if made >= m:
                        return made
            else:
                run = 0
        return made

    low = min(readyDay)
    high = max(readyDay)
    while low < high:
        mid = (low + high) // 2
        if strings_by(mid) >= m:
            high = mid
        else:
            low = mid + 1
    return low

The obvious version

Try every energising day in increasing order and, for each, count strings by adding `run // k` over the maximal blocks of energised panels; return the first day that reaches `m`, or -1 after the last day. O(n^2).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_earliest_commission_day(readyDay, m, k):
    for day in sorted(set(readyDay)):
        made = 0
        run = 0
        for value in readyDay:
            if value <= day:
                run += 1
            else:
                made += run // k
                run = 0
        made += run // k
        if made >= m:
            return day
    return -1

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in