0557MediumArrayHash TableStringSorting

Flagged Expense Claims

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.

An audit tool receives a day's expense claims as a list of strings. Each entry of transactions has the form "{staff},{minute},{amount},{site}", giving the person who filed it, the minute of the day it was filed, the sum claimed, and the office site it was filed from.

A claim is flagged when either of these holds:

the amount claimed is more than 1200, or
some other claim in the list carries the same staff name, was filed from a different site, and its minute is within 60 of this claim's minute (a gap of exactly 60 counts as within).

Return the flagged claims as the original strings, in any order. Two entries may be byte-for-byte identical; each is judged separately, so each flagged copy appears in the result.

Examples

Example 1

Input: transactions = ["dana,120,300,leeds", "dana,180,300,york", "elias,400,1300,leeds"]
Output: ["dana,120,300,leeds", "dana,180,300,york", "elias,400,1300,leeds"]

Dana's two claims are 60 minutes apart from different sites, which is within the window, so both are flagged. Elias claims 1300, which is above 1200.

Example 2

Input: transactions = ["kai,10,200,perth", "kai,20,200,perth"]
Output: []

Both claims come from the same site, so the second rule does not apply, and neither amount is above 1200.

Example 3

Input: transactions = ["mira,300,1500,derby", "mira,300,1500,derby"]
Output: ["mira,300,1500,derby", "mira,300,1500,derby"]

The two entries are identical and each claims 1500, so each one is flagged on the amount rule and both copies are reported.

Constraints

1 <= transactions.length <= 1000
Each transactions[i] has the form "{staff},{minute},{amount},{site}"
staff and site consist of lowercase English letters and have length between 1 and 10.
minute is an integer written in digits, between 0 and 1000.
amount is an integer written in digits, between 0 and 2000.
The result may be returned in any order.

The values you return may be in any order.

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 invalid_transactions(transactions: list[str]) -> list[str]:

Java

public List<String> invalidTransactions(String[] transactions)

The intended approach

Time O(n log n) for sorting the buckets; each sweep is linear in the bucket size.Space O(n) for the parsed rows, the buckets and the flag array.

Parse every claim once and bucket the claim indices by staff name in a hash map, because the second rule can only ever pair claims inside one bucket. Sort a bucket by minute and sweep it twice, once forward and once backward, keeping a window of the claims whose minute is within 60 of the current one and a tally of how many claims of each site sit in that window; the current claim is flagged when the window holds at least one claim from a site other than its own. Two sweeps are needed because the pairing is symmetric and one sweep only ever sees the claims on one side. The amount rule is a separate single pass, and the result is emitted in input order.

Pythonentry point: invalid_transactions

def invalid_transactions(transactions):
    # O(n log n) time, O(n) space: bucket the claims by staff name, sort each
    # bucket by minute, then sweep it twice with a 60-minute window that keeps a
    # tally of the sites currently inside the window.
    n = len(transactions)
    rows = []
    for line in transactions:
        staff, minute, amount, site = line.split(",")
        rows.append((staff, int(minute), int(amount), site))
    flagged = [False] * n
    buckets = {}
    for i, row in enumerate(rows):
        buckets.setdefault(row[0], []).append(i)
    for i, row in enumerate(rows):
        if row[2] > 1200:
            flagged[i] = True
    for group in buckets.values():
        order = sorted(group, key=lambda i: rows[i][1])
        k = len(order)
        for direction in (1, -1):
            seq = order if direction == 1 else order[::-1]
            counts = {}
            total = 0
            lo = 0
            for j in range(k):
                idx = seq[j]
                t = rows[idx][1]
                while lo < j and abs(t - rows[seq[lo]][1]) > 60:
                    s = rows[seq[lo]][3]
                    counts[s] -= 1
                    total -= 1
                    lo += 1
                if total - counts.get(rows[idx][3], 0) > 0:
                    flagged[idx] = True
                counts[rows[idx][3]] = counts.get(rows[idx][3], 0) + 1
                total += 1
    return [transactions[i] for i in range(n) if flagged[i]]

The obvious version

For each claim, walk the entire list once more and test both rules directly against every other claim, with no grouping and no sorting.

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_invalid_transactions(transactions):
    rows = []
    for line in transactions:
        staff, minute, amount, site = line.split(",")
        rows.append((staff, int(minute), int(amount), site))
    out = []
    for i in range(len(rows)):
        staff, minute, amount, site = rows[i]
        bad = amount > 1200
        if not bad:
            for j in range(len(rows)):
                if j == i:
                    continue
                other = rows[j]
                if other[0] != staff:
                    continue
                if other[3] == site:
                    continue
                gap = minute - other[1]
                if gap < 0:
                    gap = -gap
                if gap <= 60:
                    bad = True
                    break
        if bad:
            out.append(transactions[i])
    return out

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