0652MediumArrayHash TablePrefix Sum

Best Matched Block of Ledger Entries

Tracked in this browser only

Trains the technique from

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 ledger holds the signed amounts of a day's entries in the list entries; a credit is positive and a debit is negative.

An auditor works on matched blocks. A matched block is a run of consecutive entries in which the amount of the first entry and the amount of the last entry differ by exactly gap, in either direction. Because gap is at least 1, a matched block always holds at least two entries.

Return the largest total a matched block can have. Return 0 when the ledger has no matched block at all; note that a matched block whose entries happen to total exactly 0 produces the same return value, so the two situations cannot be told apart from the answer alone.

Examples

Example 1

Input: entries = [3, 9, 3, 9], gap = 6
Output: 24

The whole ledger is a matched block: it starts at 3, ends at 9, and those differ by 6. Its total is 24.

Example 2

Input: entries = [4, -100, 6, -100, 4], gap = 2
Output: -90

Entries 1 to 3 form a matched block, running 4, -100, 6, since 4 and 6 differ by 2, and it totals -90. Entries 3 to 5 also form one and also total -90.

Example 3

Input: entries = [7, 3], gap = 5
Output: 0

The only run of two or more entries starts at 7 and ends at 3, which differ by 4 rather than 5, so there is no matched block and the answer is 0.

Constraints

2 <= entries.length <= 10^5
-10^9 <= entries[i] <= 10^9
1 <= gap <= 10^9
Every block total the ledger can produce is between -10^14 and 10^14.

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 best_matched_block(entries: list[int], gap: int) -> int:

Java

public long bestMatchedBlock(int[] entries, int gap)

The intended approach

Time O(n): one pass with two constant-time map lookups per entry.Space O(n) for the map, which holds one running total per distinct amount.

The total of a block is the running total up to its last entry minus the running total taken just before its first entry, so for a fixed last entry the best block is the one whose first entry has the smallest running total in front of it. Keep a map from an amount to the smallest running total ever seen immediately before an entry of that amount. Walk the ledger once: record the current entry in the map, extend the running total, then look up the two amounts that are `gap` away from the current one and take the best difference. A separate flag distinguishes never having found a block from finding one that totals zero.

Pythonentry point: best_matched_block

def best_matched_block(entries, gap):
    # Running total up to and including the current entry, minus the smallest
    # running total seen just before an entry of the partner value, is the largest
    # block that can end here. O(n) time, O(n) space.
    floor_before = {}
    running = 0
    answer = None
    for v in entries:
        if v not in floor_before or running < floor_before[v]:
            floor_before[v] = running
        running += v
        for want in (v - gap, v + gap):
            if want in floor_before:
                cand = running - floor_before[want]
                if answer is None or cand > answer:
                    answer = cand
    return 0 if answer is None else answer

The obvious version

Try every pair of positions as the two ends of a block, accumulating the total as the right end moves, and keep the largest total among the pairs whose amounts differ by exactly the gap.

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_best_matched_block(entries, gap):
    n = len(entries)
    answer = None
    for i in range(n):
        acc = entries[i]
        for j in range(i + 1, n):
            acc += entries[j]
            diff = entries[i] - entries[j]
            if diff < 0:
                diff = -diff
            if diff == gap:
                if answer is None or acc > answer:
                    answer = acc
    return 0 if answer is None else answer

How this problem was checked

Reference solution executed against 12 test cases — 12 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