Policemen Catch Thieves: Complete Solution and Analysis

1. Introduction and Core Concepts

The policemen catch thieves problem is a classic greedy algorithm challenge that elegantly demonstrates how local optimal choices can lead to a globally optimal solution. The problem statement is deceptively simple: given an array where each element represents either a policeman ('P') or a thief ('T'), and an integer k representing the maximum distance a policeman can travel to catch a thief, determine the maximum number of thieves that can be caught. Each policeman can catch at most one thief, and each thief can be caught by at most one policeman. A catch is only valid if the absolute distance between their indices is less than or equal to k.

At first glance, this might appear to be a complex matching or bipartite graph problem, but its structure allows for a highly efficient greedy solution. The core concept revolves around the principle of earliest possible matching. If we process both policemen and thieves in order of their positions, matching the leftmost available policeman with the leftmost catchable thief ensures we never waste a policeman who could have caught a thief that no one else could reach. This ordering constraint is what makes the greedy approach not just feasible, but provably optimal.

Why does the policemen catch thieves problem matter beyond coding interviews? It serves as a foundational model for a wide class of resource allocation and assignment problems with distance or time constraints. Understanding this problem builds intuition for interval scheduling, bipartite matching with linear ordering, and constrained assignment. It is frequently asked in technical interviews at companies like Amazon, Microsoft, and Goldman Sachs because it tests a candidate's ability to recognize greedy choice properties, prove correctness, and implement a linear-time two-pointer technique without resorting to expensive brute-force or graph algorithms.

The Greedy Choice Property

The greedy choice property in this context states that making the locally optimal match at each step — pairing the earliest unmatched policeman with the earliest unmatched thief within range — never harms the ability to achieve a globally optimal total. If a policeman at index i can catch thieves at indices j1 and j2 where j1 < j2, catching j1 is always at least as good as catching j2, because j2 might still be reachable by a later policeman while j1 might not. This monotonicity is the key insight that separates an O(n) greedy solution from an O(n^2) brute-force search.

Problem Constraints and Assumptions

Typically, the array length n is up to 10^5, and k is a non-negative integer. The array contains only 'P' and 'T' characters. The distance is defined as abs(police_index - thief_index) <= k. It is crucial to note that policemen and thieves are indistinguishable except for position; there is no priority or weight. The objective is strictly to maximize the cardinality of the matching, not to minimize total distance traveled. This unweighted nature is what allows the greedy strategy to succeed without needing dynamic programming or maximum flow.

2. How It Works

The optimal strategy for policemen catch thieves relies on separating and ordering the positions of policemen and thieves. Instead of scanning the original array repeatedly, we first create two auxiliary lists: one storing all indices where arr[i] == 'P' and another storing all indices where arr[i] == 'T'. Both lists are naturally sorted because we traverse the array from left to right. This preprocessing transforms a scattered spatial problem into a clean, ordered matching problem between two sorted sequences.

Once we have these two sorted lists, we apply a two-pointer technique. Let p point to the current policeman and t point to the current thief. We compare police[p] and thief[t]. If abs(police[p] - thief[t]) <= k, we have found a valid catch, so we increment our catch count and advance both pointers. If thief[t] < police[p] - k, the thief is too far to the left to be caught by this or any future policeman (since future policemen are even further right), so we must discard this thief and advance t. Conversely, if police[p] < thief[t] - k, the policeman is too far left to catch this or any future thief, so we advance p.

This mechanism ensures every comparison results in progress — at least one pointer moves forward. The algorithm never backtracks, which is the hallmark of its efficiency. The logic mirrors the merging step of merge sort or the classic "assign mice to holes" problem. The critical invariant is that at any point, all policemen and thieves before the current pointers have already been optimally considered, and no better matching could involve them.

Why Greedy is Optimal: An Intuitive Proof

Consider any optimal solution that differs from the greedy solution at the first point of divergence. Suppose the greedy algorithm matches policeman P_g with thief T_g, while an optimal solution matches P_g with a later thief T_o where T_g < T_o. Since T_g was the earliest catchable thief for P_g, T_g must be within range of P_g. If T_g is unmatched in the optimal solution, we can swap T_o for T_g without reducing the total count. If T_g is matched to a later policeman P_later in the optimal solution, then P_later can also catch T_o because T_o is to the right of T_g and within range of P_g, implying it is also within range of any policeman to the right that could catch T_g. This exchange argument proves the greedy choice never reduces the optimal count.

Alternative View: Queue-Based Simulation

Another way to conceptualize the process is as a queue. As we scan the array from left to right, we maintain queues of unmatched policemen and thieves that are still within the window k. When we encounter a policeman, we check if there is a waiting thief within distance k; if so, we match them immediately. If not, we enqueue the policeman. The same logic applies when encountering a thief. This view is particularly useful for streaming data where the entire array is not known in advance and matches must be made online.

3. Implementation

Implementing the policemen catch thieves solution in Python is straightforward and can be done in several ways. The most efficient and readable approach uses the two-pointer method on precomputed index lists. Below are multiple implementations showcasing different styles and trade-offs, all adhering to clean, commented Python code.

The first implementation is the canonical, interview-ready solution. It is concise, runs in linear time, and uses linear extra space for the index lists. It handles edge cases such as empty arrays, no policemen, or no thieves gracefully.

def catch_thieves_greedy(arr, k):
    """
    Greedy two-pointer solution for policemen catch thieves.
    arr: list of 'P' and 'T'
    k: maximum catch distance
    Returns: maximum number of thieves caught
    """
    n = len(arr)
    police = []
    thieves = []
    
    # Collect indices of policemen and thieves
    for i in range(n):
        if arr[i] == 'P':
            police.append(i)
        elif arr[i] == 'T':
            thieves.append(i)
    
    p = 0  # pointer for police list
    t = 0  # pointer for thieves list
    caught = 0
    
    # Two-pointer matching
    while p < len(police) and t < len(thieves):
        # Check if current policeman can catch current thief
        if abs(police[p] - thieves[t]) <= k:
            caught += 1
            p += 1
            t += 1
        # Thief is too far left, no policeman can catch him
        elif thieves[t] < police[p]:
            t += 1
        # Policeman is too far left, he cannot catch any future thief
        else:
            p += 1
            
    return caught

# Example usage
arr = ['P', 'T', 'T', 'P', 'T']
k = 1
print(catch_thieves_greedy(arr, k))  # Output: 2

The second implementation demonstrates a brute-force approach for educational purposes. While it correctly computes the answer, it runs in O(n^2) time in the worst case by scanning for each policeman. This version is useful for verifying correctness of the greedy solution on small inputs and for understanding why optimization is necessary.

def catch_thieves_bruteforce(arr, k):
    """
    Brute-force solution to illustrate inefficiency.
    Tries every possible matching for each policeman.
    Time: O(n * k) worst case, Space: O(n)
    """
    n = len(arr)
    caught = [False] * n  # track if thief already caught
    count = 0
    
    for i in range(n):
        if arr[i] == 'P':
            # Search within window [i-k, i+k] for nearest uncaught thief
            # Prefer leftmost thief to be greedy, but brute force checks all
            for j in range(max(0, i - k), min(n, i + k + 1)):
                if arr[j] == 'T' and not caught[j]:
                    # Found a catchable thief
                    caught[j] = True
                    count += 1
                    break  # policeman can catch only one
    return count

# This fails to be optimal if we don't choose earliest thief first
# Example where order matters: ['T', 'P', 'T'], k=1
# Brute force above picks left thief first, which is optimal

The third implementation uses collections.deque to simulate the queue-based online matching. This is particularly elegant when the input is processed as a stream and highlights how the algorithm can be adapted for real-time systems.

from collections import deque

def catch_thieves_queue(arr, k):
    """
    Queue-based simulation using deques.
    Processes array left to right, matching greedily.
    """
    police_q = deque()
    thief_q = deque()
    caught = 0
    
    for idx, ch in enumerate(arr):
        if ch == 'P':
            # Try to match with earliest waiting thief within range
            while thief_q and thief_q[0] < idx - k:
                thief_q.popleft()  # thief too far to be caught now
            if thief_q and abs(thief_q[0] - idx) <= k:
                thief_q.popleft()
                caught += 1
            else:
                police_q.append(idx)
        elif ch == 'T':
            while police_q and police_q[0] < idx - k:
                police_q.popleft()  # policeman too far to catch future thieves
            if police_q and abs(police_q[0] - idx) <= k:
                police_q.popleft()
                caught += 1
            else:
                thief_q.append(idx)
    return caught

arr = ['T', 'P', 'T', 'P', 'T', 'P']
print(catch_thieves_queue(arr, 2))  # Output: 3

The final implementation provides a robust, production-ready class with input validation, support for multiple test cases, and clear error handling. This is the style expected in larger codebases or when the function is part of a library.

class ThiefCatcher:
    def __init__(self, k):
        if k < 0:
            raise ValueError("k must be non-negative")
        self.k = k
    
    def max_catches(self, arr):
        """Return maximum catches with validation and edge case handling."""
        if not arr:
            return 0
        if not all(c in ('P', 'T') for c in arr):
            raise ValueError("Array must contain only 'P' and 'T'")
        
        police = [i for i, c in enumerate(arr) if c == 'P']
        thieves = [i for i, c in enumerate(arr) if c == 'T']
        
        if not police or not thieves:
            return 0
            
        p = t = caught = 0
        while p < len(police) and t < len(thieves):
            dist = abs(police[p] - thieves[t])
            if dist <= self.k:
                caught += 1
                p += 1
                t += 1
            elif police[p] < thieves[t]:
                # policeman left of thief and out of range
                p += 1
            else:
                t += 1
        return caught

# Driver for multiple test cases
def solve_multiple(cases):
    results = []
    for arr, k in cases:
        catcher = ThiefCatcher(k)
        results.append(catcher.max_catches(arr))
    return results

4. Step-by-Step Example

To solidify understanding, let us walk through a concrete example in detail. Consider the array arr = ['P', 'T', 'P', 'T', 'T', 'P'] with k = 2. Our goal is to trace the two-pointer algorithm and see how it achieves the maximum of 3 catches.

First, we extract indices. Policemen are at positions police = [0, 2, 5] and thieves are at thieves = [1, 3, 4]. We initialize pointers p = 0 (police[0]=0) and t = 0 (thieves[0]=1), and caught = 0.

Step 1: Compare police[0]=0 and thieves[0]=1. abs(0-1)=1 <= 2, so this is a valid catch. We match policeman at 0 with thief at 1. Increment caught=1, advance both pointers: p=1 (police[1]=2), t=1 (thieves[1]=3).

Step 2: Compare police[1]=2 and thieves[1]=3. abs(2-3)=1 <= 2, valid catch. Match policeman at 2 with thief at 3. caught=2, p=2 (police[2]=5), t=2 (thieves[2]=4).

Step 3: Compare police[2]=5 and thieves[2]=4. abs(5-4)=1 <= 2, valid catch. Match policeman at 5 with thief at 4. caught=3, p=3 (out of bounds), t=3 (out of bounds). Loop terminates. Total caught = 3, which is optimal.

A More Complex Walkthrough with Discards

Now consider a case where discarding is necessary: arr = ['T', 'T', 'P', 'P', 'T', 'P'], k = 1. Here police = [2, 3, 5], thieves = [0, 1, 4].

Start p=0 (2), t=0 (0). abs(2-0)=2 > 1. Since thieves[t]=0 < police[p]=2, the thief at 0 is too far left; no future policeman (at 3 or 5) can catch it because they are even further right. So we discard thief 0: t=1 (1).

Now p=0 (2), t=1 (1). abs(2-1)=1 <=1 → catch. caught=1, p=1 (3), t=2 (4).

Compare p=1 (3), t=2 (4). abs(3-4)=1 <=1 → catch. caught=2, p=2 (5), t=3 out of bounds. Loop ends. Total 2. Note thief at 1 was caught, thief at 0 was correctly discarded, and policeman at 5 remains unused because no thieves remain.

This walkthrough demonstrates the algorithm's ability to skip impossible matches without missing opportunities. If we had greedily matched policeman at 2 with thief at 0 (even though distance 2 > k, it would be invalid), we would have missed the valid match. The distance check prevents invalid catches, and the pointer advancement logic ensures we never get stuck.

5. Complexity Analysis

Efficiency is a major advantage of the greedy solution for policemen catch thieves. Unlike brute-force or graph-based approaches, the two-pointer method achieves linear time complexity, making it suitable for large inputs up to millions of elements.

The algorithm consists of two phases: building the index lists and the two-pointer matching. Building the lists requires a single pass over the array of size n, which is O(n) time and O(n) space in the worst case where all elements are of one type. The matching phase also runs in O(n) time because each pointer moves monotonically forward and each element is visited at most once. Overall, the time complexity is O(n) and the space complexity is O(n) for storing the indices.

It is worth noting that the space can be optimized to O(1) if we avoid storing separate lists and instead scan the original array with two pointers that find the next 'P' and 'T' on the fly. However, that approach complicates the code and often results in O(n*k) worst-case time if not implemented carefully. For clarity and interview purposes, the O(n) space solution is preferred and easily passes constraints.

In the best case, where k is large enough to match all possible pairs, the matching loop still processes all elements but terminates quickly. In the worst case, where k = 0, only thieves and policemen at the exact same index could match (which never happens since each index holds one character), so the algorithm will discard one pointer at each step, still visiting each element once. The average case remains linear regardless of the distribution of 'P' and 'T'.

Space-Time Tradeoffs

If memory is severely constrained, an in-place variant can be implemented that does not store index lists. Instead, it maintains two indices i and j scanning the original array to find the next policeman and thief. This reduces space to O(1) but requires careful handling to avoid re-scanning. For most practical purposes, the O(n) space overhead is negligible — storing 10^5 integers uses less than 1 MB in Python.

6. Variations and Optimizations

The basic policemen catch thieves problem admits several interesting variations that test deeper understanding of greedy algorithms and data structures. Recognizing these variants is crucial for adapting the solution to interview follow-ups or real-world constraints.

One common variation introduces different catch ranges for each policeman. Instead of a uniform k, each policeman P_i has its own k_i. The simple two-pointer approach no longer works directly because the matching condition is no longer symmetric. However, if policemen are still processed in order and each policeman's range is known, a greedy strategy using a priority queue (min-heap) of available thieves can still be optimal: for each policeman in order, add all thieves within his range that haven't been considered, and match him with the earliest one.

Another variation allows multiple thieves per policeman or requires minimizing total distance traveled rather than maximizing catches. The former becomes a flow problem, while the latter is an assignment problem that may require dynamic programming. A third variation places policemen and thieves on a 2D grid with Manhattan distance, which transforms the problem into a more complex bipartite matching scenario where greedy by linear order fails.

Optimization: Early Termination and Input Compression

For very large arrays with sparse 'P' and 'T' (e.g., mostly empty spaces denoted by ' '), we can compress the input by storing only relevant indices. Additionally, if k is small, we can early-terminate the inner checks. Another optimization is to use Python's bisect module to binary search for the next catchable thief for each policeman, though this yields O(n log n) time and is not better than the linear two-pointer method.

For the case where the array is given as a string and we need to handle multiple queries with different k values, we can precompute police and thief positions once and answer each query in O(P+T) time. If many queries are expected, we could even precompute answers for all possible k using a sweep line.

import bisect

def catch_thieves_bisect(arr, k):
    """
    Variant using binary search for educational comparison.
    Not optimal vs two-pointer but useful when k varies per policeman.
    """
    police = [i for i, c in enumerate(arr) if c == 'P']
    thieves = [i for i, c in enumerate(arr) if c == 'T']
    caught = [False] * len(thieves)
    count = 0
    
    for p_idx in police:
        # Find leftmost thief within [p_idx - k, p_idx + k]
        left = bisect.bisect_left(thieves, p_idx - k)
        # Find first uncaught thief in range
        for t_pos in range(left, len(thieves)):
            if thieves[t_pos] > p_idx + k:
                break
            if not caught[t_pos]:
                caught[t_pos] = True
                count += 1
                break
    return count

Handling Weighted or Prioritized Thieves

If thieves have values (e.g., some are more important to catch), the objective shifts from maximizing count to maximizing total value. The greedy by position fails here; a dynamic programming or weighted bipartite matching solution is required. This variant illustrates the limits of the greedy approach and when to switch to more powerful techniques.

7. Real-World Applications

While the policemen catch thieves narrative is playful, the underlying abstract problem — matching two types of entities with a proximity constraint to maximize matches — appears in numerous real-world systems. Understanding this mapping helps engineers recognize when a simple greedy solution can replace a heavyweight optimization framework.

In web servers and load balancing, consider assigning incoming requests (thieves) to servers (policemen) where each server can handle one request and has a maximum latency window k (network hops or queue time). Matching requests to the nearest available server in order minimizes dropped requests. Similarly, in databases, the problem models assigning queries to connection pool workers where each worker can serve a query only if it arrives within a time window.

In networking, the problem arises in channel allocation for wireless sensors. Sensors (policemen) can intercept signals (thieves) only within a certain signal range. Maximizing interceptions with minimal computation is critical for low-power devices. In operating systems, it mirrors CPU scheduling where tasks must be assigned to cores within deadlines.

Beyond computing, the model applies to logistics and supply chain: delivery trucks (policemen) can serve customers (thieves) only within a fuel or time radius. The greedy algorithm provides a fast heuristic for dispatch planning. In each case, the linear ordering (by time, position, or arrival order) is what enables the greedy optimality; without ordering, the problem would require more expensive matching algorithms.

8. Comparison with Alternatives

To appreciate why the greedy two-pointer method is preferred for policemen catch thieves, it is instructive to compare it with alternative approaches that could also solve the problem, albeit less efficiently. Each alternative has different trade-offs in terms of complexity, implementation effort, and generality.

Brute-force scanning is the most intuitive alternative: for each policeman, scan the window [i-k, i+k] for an uncaught thief. While easy to code, it can degrade to O(n*k) or O(n^2) and may fail to be optimal if the scanning order is not carefully chosen to prioritize the earliest thief. It also requires a visited array to avoid double-counting.

Modeling the problem as a maximum bipartite matching and solving it with DFS augmenting paths (Hungarian or Hopcroft-Karp) is a general and correct approach. It constructs a graph where an edge exists if distance <= k, then finds maximum matching. This works for any distance metric, including 2D, but runs in O(V*E) which can be O(n^3) in dense cases, and is overkill for the 1D ordered case.

Dynamic programming is another alternative, especially if we want to handle weighted thieves. A DP formulation would consider the prefix up to index i and decide to match or skip. While DP can handle more complex objectives, it uses O(n) space and O(n*k) time and is unnecessarily complex for the unweighted version.

The table makes it clear that for the standard policemen catch thieves problem with uniform k and linear ordering, the greedy two-pointer approach dominates in both time and simplicity. It should be the default choice unless the problem statement explicitly introduces weights, non-uniform ranges, or multi-dimensional distances that break the greedy choice property.

9. Common Mistakes and Best Practices

Even though the algorithm is simple, candidates frequently make subtle errors when implementing policemen catch thieves under interview pressure. Awareness of these pitfalls can be the difference between a correct solution and a flawed one.

A common mistake is to match a policeman with the nearest thief rather than the earliest catchable thief. For example, with arr = ['P', 'T', 'T'] and k=1, policeman at 0 can catch thief at 1 (distance 1) but not thief at 2 (distance 2). Choosing the nearest (which is also the earliest here) works, but in ['T', 'P', 'T', 'T'] with k=1, policeman at 1 can catch thieves at 0 and 2. Matching with 2 instead of 0 would leave thief at 0 unmatched forever, reducing total catches. The rule is always prefer the leftmost available thief within range.

Another frequent error is forgetting to mark thieves as caught or allowing a policeman to catch multiple thieves. This happens in brute-force implementations that do not maintain a visited set. Similarly, some implementations incorrectly use < k instead of <= k, off-by-one errors that fail edge cases where distance exactly equals k.

Candidates also sometimes attempt to modify the original array in place (e.g., marking caught thieves as 'C') which can corrupt the input for multiple test cases or violate the requirement not to mutate inputs. It is better to use auxiliary boolean arrays or pointer indices.

Best Practices

• Separate indices first: Always extract police and thief positions into sorted lists. This clarifies the logic and prevents repeated scanning.
• Use two pointers, not nested loops: Ensure each pointer moves forward monotonically. Avoid nested loops that re-scan the array.
• Validate inputs: Check for empty arrays, invalid characters, and negative k. Handle cases with zero policemen or thieves early.
• Prove greedy choice: In interviews, be ready to explain why greedy works with an exchange argument. Interviewers value proof over just code.
• Test edge cases: Test with k=0, all 'P', all 'T', alternating pattern, and large k >= n. For example, ['P','T'] with k=0 should return 0, while with k=1 should return 1.
• Escape HTML properly: When displaying code on the web, ensure < and > are escaped to prevent rendering issues.

Finally, always analyze complexity explicitly. Stating "O(n) time and O(n) space" without justification is insufficient; explain why each phase is linear and how the two-pointer technique guarantees each element is processed once.

10. Interview Questions

Mastering policemen catch thieves prepares you for a variety of interview questions that test greedy thinking, two-pointer technique, and problem adaptation. Below are common questions and how to approach them.

Q1: What is the maximum number of thieves that can be caught? (Standard Problem)

This is the base question. Expected answer is the greedy two-pointer implementation described earlier. Interviewers will check for correct handling of distance <= k, proper pointer advancement, and O(n) complexity. Be prepared to walk through an example and prove optimality. A strong answer includes both the code and the exchange argument for correctness.

Q2: What if each policeman has a different catching range k_i?

This follow-up tests adaptability. The uniform k greedy no longer directly applies. A good approach is to sort policemen by position and use a min-heap of thieves sorted by position. For each policeman in order, add all thieves whose position is within [police_pos - k_i, police_pos + k_i] and that haven't been assigned, then match the policeman with the earliest thief in the heap. This yields O(n log n) time. If k_i is arbitrary, the problem becomes a general bipartite matching, and you should mention Hopcroft-Karp as an alternative.

Q3: Can you solve it in O(1) extra space?

Yes, by scanning the original array without building auxiliary lists. Use two indices i and j that find the next 'P' and 'T' on the fly. While both exist, check distance. If within k, count and advance both; otherwise advance the pointer with the smaller index. This avoids O(n) storage but requires careful loops to find next occurrence. Discuss the trade-off: slightly more complex code for memory savings, but time remains O(n) if implemented without re-scanning from start each time.

Q4: How would you handle thieves with different priorities or values?

This changes the objective to maximizing total value, not count. Greedy by position fails. The correct approach is dynamic programming or weighted bipartite matching. Define DP[i] as maximum value achievable considering first i positions, with transitions for matching or skipping. Alternatively, model as a maximum weight matching problem. Mention that this variant is NP-hard in some generalizations, but for 1D with interval constraints, DP with sorting by position can solve it in O(n log n).

Q5: Prove that the greedy algorithm is optimal.

Provide the exchange argument: Assume an optimal solution differs from greedy at the first mismatch. Show you can transform the optimal solution to match the greedy choice without decreasing its size, by swapping thieves. Conclude by induction that greedy achieves optimal count. This question tests theoretical depth; a clear, step-by-step proof demonstrates strong algorithmic maturity. Mention the key invariant: greedy never leaves a catchable thief unmatched that could have been matched later.

Preparing answers to these questions, along with clean code and complexity analysis, will ensure you can confidently tackle any policemen catch thieves variant in interviews and apply the underlying principles to real-world allocation problems.