Policemen Catch Thieves

Policemen Catch Thieves is a clean greedy problem that doubles as a two-pointer warm-up. You scan a row of police and thieves once and match them up locally — the trick is proving that a greedy nearest-match is always optimal.

The slow way first

The brute-force instinct is to try every assignment of police to nearby thieves and keep the best — a combinatorial search that blows up fast. Even a more careful matching (bipartite graph + max-flow) is overkill here.

The question to ask: if I walk the row left to right, who should catch whom? It turns out the leftmost free policeman should always grab the nearest unclaimed thief within reach. Once you believe that, a single pass with two pointers solves it.

The idea: greedy nearest match with two pointers

Keep two pointers walking forward: p finds the next policeman, t finds the next thief. Compare their positions. If they are within k, match them and advance both. If not, advance whichever pointer is behind — that element can never improve by waiting, so we move past it.

Why greedy is safe: pairing the earliest policeman with the closest reachable thief never blocks a better future match. Any thief that policeman could skip is still available to a later, equally-close policeman.

Walk through it

Step through the animation. Pointer p (green) lands on each policeman; pointer t (blue) lands on each thief. When |p - t| <= k, both cells turn green and caught ticks up. With k = 1 every police/thief pair here is exactly one cell apart, so all three matches land.

Pseudocode

caught = 0
p = t = 0
while both pointers are inside the row:
    move p forward until it sits on a 'P'
    move t forward until it sits on a 'T'
    if both are still in range:
        if |p - t| <= k:
            caught += 1
            advance both p and t
        else:
            advance whichever pointer is behind
return caught

The Python solution

def catch_thieves(row, k):
    caught = 0
    p = t = 0
    n = len(row)
    while p < n and t < n:
        while p < n and row[p] != 'P': p += 1
        while t < n and row[t] != 'T': t += 1
        if p < n and t < n:
            if abs(p - t) <= k:
                caught += 1
                p += 1; t += 1
            elif p < t: p += 1
            else:       t += 1
    return caught

• p and t are independent scan pointers; they never move backward.
• The two inner while loops fast-forward each pointer to the next relevant character.
• abs(p - t) <= k is the reach test — the heart of the greedy match.
• On a match we advance both pointers so neither element is reused.
• On a miss we advance only the trailing pointer, since the leading one might still pair with someone closer ahead.

Complexity

Both pointers only ever move forward across n cells, so the total work is linear and we use just a couple of integer variables.

When this pattern shows up

Practice