21. Police and Thieves
✅ GFG solution to the Police and Thieves problem: find maximum number of thieves that can be caught using optimal two-pointer greedy approach. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
Given an array arr[]
, where each element contains either a 'P' for policeman or a 'T' for thief. Find the maximum number of thieves that can be caught by the police.
Keep in mind the following conditions:
Each policeman can catch only one thief
A policeman cannot catch a thief who is more than k units away from him
📘 Examples
Example 1
Input: arr[] = ['P', 'T', 'T', 'P', 'T'], k = 1
Output: 2
Explanation: Maximum 2 thieves can be caught.
First policeman catches first thief and second policeman
can catch either second or third thief.
Example 2
Input: arr[] = ['T', 'T', 'P', 'P', 'T', 'P'], k = 2
Output: 3
Explanation: Maximum 3 thieves can be caught.
🔒 Constraints
$1 \le \text{arr.size()} \le 10^5$
$1 \le k \le 1000$
$\text{arr}[i] = \text{'P'} \text{ or } \text{'T'}$
✅ My Approach
The optimal approach uses a Greedy Two-Pointer technique to maximize the number of catches:
Two-Pointer Greedy Algorithm
Initialize Two Pointers:
i = 0
(searching for policemen)j = 0
(searching for thieves)count = 0
(number of successful catches)
Find Next Valid Pair:
Move pointer
i
to find the next policeman ('P')Move pointer
j
to find the next thief ('T')
Check Distance Constraint:
If
|i - j| ≤ k
, both can be paired successfullyIncrement both pointers and increase count
Otherwise, move the pointer that points to the earlier position
Greedy Strategy:
Always try to pair the earliest available policeman with the earliest reachable thief
This ensures optimal utilization of resources
Why This Approach Works:
Greedy Choice: Pairing the leftmost available policeman with the leftmost reachable thief is always optimal
No Backtracking Needed: Once a pair is formed, we don't need to reconsider previous positions
Linear Scan: Each element is visited at most twice (once by each pointer)
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n), where n is the size of the array. Each element is processed at most twice by the two pointers, resulting in linear time complexity.
Expected Auxiliary Space Complexity: O(1), as we only use a constant amount of additional space for the two pointers and counter variables.
🧑💻 Code (C++)
class Solution {
public:
int catchThieves(vector<char> &arr, int k) {
int n = arr.size(), i = 0, j = 0, c = 0;
while (i < n && j < n) {
while (i < n && arr[i] != 'P') i++;
while (j < n && arr[j] != 'T') j++;
if (i < n && j < n && abs(i - j) <= k) i++, j++, c++;
else if (j < i) j++;
else i++;
}
return c;
}
};
🧑💻 Code (Java)
class Solution {
public int catchThieves(char[] arr, int k) {
int i = 0, j = 0, n = arr.length, c = 0;
while (i < n && j < n) {
while (i < n && arr[i] != 'P') i++;
while (j < n && arr[j] != 'T') j++;
if (i < n && j < n && Math.abs(i - j) <= k) {
i++; j++; c++;
} else if (j < i) j++;
else i++;
}
return c;
}
}
🐍 Code (Python)
class Solution:
def catchThieves(self, arr, k):
i = j = c = 0
n = len(arr)
while i < n and j < n:
while i < n and arr[i] != 'P':
i += 1
while j < n and arr[j] != 'T':
j += 1
if i < n and j < n and abs(i - j) <= k:
i += 1
j += 1
c += 1
elif j < i:
j += 1
else:
i += 1
return c
🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated