Given an array arr[], where each element represents either a policeman (P) or a thief (T). Each policeman can catch only one thief and policeman can only catch a thief if the distance between them is at most k units. Find the maximum number of thieves that can be caught.
Examples:
Input: arr[] = ['P', 'T', 'T', 'P', 'T'], k = 1
Output: 2.
Explanation: policeman of 0th index catches thief at index 1 and policeman of 3rd index can catch thief at either 2nd or 4th index.
Input: arr[] = ['T', 'T', 'P'], k = 1
Output: 1
Explanation: Policeman of 2th index catches thief at index 1.
Try it on GfG Practice
Table of Content
[Naive Approach] Using Nested loops - O(n*k) Time and O(n) Space
The idea is that for every policeman, we search for a thief within a range of 2*k + 1 in a sequential manner. If a thief is found, we mark index into the caught array to ensure that the same thief is not caught multiple times.
#include <iostream>
#include<vector>
using namespace std;
int catchThieves(vector<char> &arr, int k) {
int n = arr.size();
// To mark if a thief is caught
vector<bool> caught(n, false);
int count = 0;
for (int i = 0; i < n; ++i) {
if (arr[i] == 'P') {
int start = max(0, i - k);
int end = min(n - 1, i + k);
// Search for an uncaught thief within range
for (int j = start; j <= end; ++j) {
if (arr[j] == 'T' && !caught[j]) {
caught[j] = true;
count++;
break;
}
}
}
}
return count;
}
int main() {
int k = 1;
vector<char> arr = { 'P', 'T', 'T', 'P', 'T' };
cout<< catchThieves(arr, k) << endl;
}
public class GfG {
static int catchThieves(char[] arr, int k) {
int n = arr.length;
// To mark if a thief is caught
boolean[] caught = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 'P') {
int start = Math.max(0, i - k);
int end = Math.min(n - 1, i + k);
// Search for an uncaught thief within range
for (int j = start; j <= end; j++) {
if (arr[j] == 'T' && !caught[j]) {
caught[j] = true;
count++;
break;
}
}
}
}
return count;
}
public static void main(String[] args) {
int k = 1;
char[] arr = { 'P', 'T', 'T', 'P', 'T' };
System.out.println(catchThieves(arr, k));
}
}
def catchThieves(arr, k):
n = len(arr)
# To mark if a thief is caught
caught = [False] * n
count = 0
for i in range(n):
if arr[i] == 'P':
start = max(0, i - k)
end = min(n - 1, i + k)
# Search for an uncaught thief within range
for j in range(start, end + 1):
if arr[j] == 'T' and not caught[j]:
caught[j] = True
count += 1
break
return count
if __name__ == "__main__":
k = 1
arr = ['P', 'T', 'T', 'P', 'T']
print(catchThieves(arr, k))
using System;
class GfG {
static int catchThieves(char[] arr, int k) {
int n = arr.Length;
// To mark if a thief is caught
bool[] caught = new bool[n];
int count = 0;
for (int i = 0; i < n; i++)
{
if (arr[i] == 'P')
{
int start = Math.Max(0, i - k);
int end = Math.Min(n - 1, i + k);
// Search for an uncaught thief within range
for (int j = start; j <= end; j++)
{
if (arr[j] == 'T' && !caught[j])
{
caught[j] = true;
count++;
break;
}
}
}
}
return count;
}
static void Main() {
int k = 1;
char[] arr = { 'P', 'T', 'T', 'P', 'T' };
Console.WriteLine(catchThieves(arr, k));
}
}
function catchThieves(arr, k) {
let n = arr.length;
// To mark if a thief is caught
let caught = new Array(n).fill(false);
let count = 0;
for (let i = 0; i < n; i++) {
if (arr[i] === 'P') {
let start = Math.max(0, i - k);
let end = Math.min(n - 1, i + k);
// Search for an uncaught thief within range
for (let j = start; j <= end; j++) {
if (arr[j] === 'T' && !caught[j]) {
caught[j] = true;
count++;
break;
}
}
}
}
return count;
}
// Driver Code
const k = 1;
const arr = ['P', 'T', 'T', 'P', 'T'];
console.log(catchThieves(arr, k));
Output
2
[Better Approach] Using Queue - O(n) Time and O(n) Space
The idea is to maintain two queues for police and thief indices. Traverse the array, enqueue positions, and match from the front if the distance ≤ k. Dequeue accordingly to count maximum catches.
Working:
Traverse the array and enqueue the index of each police officer or thief into their respective queues. Then, repeatedly compare the front elements of both queues. If the distance between the police and the thief at the front is less than or equal to k, we catch the thief and dequeue both. If the police index is smaller, it means this policeman cannot catch the thief at the front, so we dequeue the police. Otherwise, if the thief is too far left, we dequeue the thief.
#include <iostream>
#include<queue>
using namespace std;
int catchThieves(vector<char> &arr, int k) {
// Keep track of police and thieve
queue<int>police,thieve;
int c=0;
int n=arr.size();
for(int i=0;i<n;i++)
{
if(arr[i]=='P')
police.push(i);
else
thieve.push(i);
// process the thieve and police
while(!police.empty() && !thieve.empty())
{
if(abs(police.front()-thieve.front())<=k)
{
c++;
police.pop();
thieve.pop();
}
else if(police.front()<thieve.front())
police.pop();
else
thieve.pop();
}
}
return c;
}
int main() {
int k = 1;
vector<char> arr = { 'P', 'T', 'T', 'P', 'T' };
cout<< catchThieves(arr, k) << endl;
}
import java.util.LinkedList;
import java.util.Queue;
public class GFG {
public static int catchThieves(char[] arr, int k) {
// Keep track of police and thieve
Queue<Integer> police = new LinkedList<>();
Queue<Integer> thieve = new LinkedList<>();
int c = 0;
int n = arr.length;
for (int i = 0; i < n; i++) {
if (arr[i] == 'P')
police.add(i);
else
thieve.add(i);
// process the thieve and police
while (!police.isEmpty() && !thieve.isEmpty()) {
if (Math.abs(police.peek() - thieve.peek()) <= k) {
c++;
police.poll();
thieve.poll();
} else if (police.peek() < thieve.peek())
police.poll();
else
thieve.poll();
}
}
return c;
}
public static void main(String[] args) {
int k = 1;
char[] arr = { 'P', 'T', 'T', 'P', 'T' };
System.out.println(catchThieves(arr, k));
}
}
from queue import Queue
def catchThieves(arr, k):
# Keep track of police and thieve
police = Queue()
thieve = Queue()
c = 0
n = len(arr)
for i in range(n):
if arr[i] == 'P':
police.put(i)
else:
thieve.put(i)
# process the thieve and police
while not police.empty() and not thieve.empty():
p = police.queue[0]
t = thieve.queue[0]
if abs(p - t) <= k:
c += 1
police.get()
thieve.get()
elif p < t:
police.get()
else:
thieve.get()
return c
if __name__ == '__main__':
k = 1
arr = ['P', 'T', 'T', 'P', 'T']
print(catchThieves(arr, k))
using System;
using System.Collections.Generic;
class GFG
{
static int CatchThieves(char[] arr, int k)
{
// Keep track of police and thieve
Queue<int> police = new Queue<int>();
Queue<int> thieve = new Queue<int>();
int c = 0;
int n = arr.Length;
for (int i = 0; i < n; i++)
{
if (arr[i] == 'P')
police.Enqueue(i);
else
thieve.Enqueue(i);
// process the thieve and police
while (police.Count > 0 && thieve.Count > 0)
{
if (Math.Abs(police.Peek() - thieve.Peek()) <= k)
{
c++;
police.Dequeue();
thieve.Dequeue();
}
else if (police.Peek() < thieve.Peek())
police.Dequeue();
else
thieve.Dequeue();
}
}
return c;
}
static void Main()
{
int k = 1;
char[] arr = { 'P', 'T', 'T', 'P', 'T' };
Console.WriteLine(CatchThieves(arr, k));
}
}
// Queue implementation using front pointer (O(1) enqueue & dequeue)
class Queue {
constructor() {
this.arr = [];
this.front = 0;
}
enqueue(x) {
this.arr.push(x); // O(1)
}
dequeue() {
if (this.isEmpty()) return null;
return this.arr[this.front++]; // O(1)
}
peek() {
return this.isEmpty() ? null : this.arr[this.front];
}
isEmpty() {
return this.front >= this.arr.length;
}
}
// Function to catch thieves
function catchThieves(arr, k) {
// Keep track of police and thieve
let police = new Queue();
let thieve = new Queue();
let c = 0;
let n = arr.length;
for (let i = 0; i < n; i++) {
if (arr[i] === 'P') {
police.enqueue(i);
} else {
thieve.enqueue(i);
}
// process the thieve and police
while (!police.isEmpty() && !thieve.isEmpty()) {
let p = police.peek();
let t = thieve.peek();
if (Math.abs(p - t) <= k) {
c++;
police.dequeue();
thieve.dequeue();
} else if (p < t) {
police.dequeue();
} else {
thieve.dequeue();
}
}
}
return c;
}
// Driver code
let k = 1;
let arr = ['P', 'T', 'T', 'P', 'T'];
console.log(catchThieves(arr, k));
Output
2
[Expected Approach] Using Two Pointers - O(n) Time and O(1) Space
The idea is to use two pointers (both begin from left side): one to keep track of policemen and the other for thieves. We traverse the array while maintaining these pointers. If a policeman and a thief are within the allowed range k, the thief is caught, and both pointers move forward. If the thief is too far left, we move the thief pointer forward otherwise policeman is too far left, we move the policeman pointer forward.
#include <iostream>
#include<vector>
using namespace std;
int catchThieves(vector<char> &arr, int k) {
int n = arr.size();
int i = 0, j = 0;
int count = 0;
while (i < n && j < n) {
// Move i to the next policeman
while (i < n && arr[i] != 'P') i++;
// Move j to the next thief
while (j < n && arr[j] != 'T') j++;
// If both policeman and thief exist and are within range k
if (i < n && j < n && abs(i - j) <= k) {
count++;
i++;
j++;
}
else if (j < n && j < i) {
j++;
}
else if (i < n && i < j) {
i++;
}
}
return count;
}
int main() {
int k = 1;
vector<char> arr = { 'P', 'T', 'T', 'P', 'T' };
cout<< catchThieves(arr, k) << endl;
}
public class GfG {
static int catchThieves(char[] arr, int k) {
int n = arr.length;
int i = 0, j = 0;
int count = 0;
while (i < n && j < n) {
// Move i to the next policeman
while (i < n && arr[i] != 'P') i++;
// Move j to the next thief
while (j < n && arr[j] != 'T') j++;
// If both policeman and thief exist
// and are within range k
if (i < n && j < n && Math.abs(i - j) <= k) {
count++;
i++;
j++;
}
else if (j < n && j < i) {
j++;
}
else if (i < n && i < j) {
i++;
}
}
return count;
}
public static void main(String[] args) {
int k = 1;
char[] arr = { 'P', 'T', 'T', 'P', 'T' };
System.out.println(catchThieves(arr, k));
}
}
def catchThieves(arr, k):
n = len(arr)
i, j = 0, 0
count = 0
while i < n and j < n:
# Move i to the next policeman
while i < n and arr[i] != 'P':
i += 1
# Move j to the next thief
while j < n and arr[j] != 'T':
j += 1
# If both policeman and thief exist
# and are within range k
if i < n and j < n and abs(i - j) <= k:
count += 1
i += 1
j += 1
elif j < n and j < i:
j += 1
elif i < n and i < j:
i += 1
return count
if __name__ == "__main__":
k = 1
arr = ['P', 'T', 'T', 'P', 'T']
print(catchThieves(arr, k))
using System;
class GfG {
static int catchThieves(char[] arr, int k) {
int n = arr.Length;
int i = 0, j = 0;
int count = 0;
while (i < n && j < n) {
// Move i to the next policeman
while (i < n && arr[i] != 'P')
i++;
// Move j to the next thief
while (j < n && arr[j] != 'T')
j++;
// If both policeman and thief exist
// and are within range k
if (i < n && j < n && Math.Abs(i - j) <= k) {
count++;
i++;
j++;
}
else if (j < n && j < i) {
j++;
}
else if (i < n && i < j) {
i++;
}
}
return count;
}
static void Main() {
int k = 1;
char[] arr = { 'P', 'T', 'T', 'P', 'T' };
Console.WriteLine(catchThieves(arr, k));
}
}
function catchThieves(arr, k) {
let n = arr.length;
let i = 0, j = 0;
let count = 0;
while (i < n && j < n) {
// Move i to the next policeman
while (i < n && arr[i] !== 'P') i++;
// Move j to the next thief
while (j < n && arr[j] !== 'T') j++;
// If both policeman and thief exist and are within range k
if (i < n && j < n && Math.abs(i - j) <= k) {
count++;
i++;
j++;
}
else if (j < n && j < i) {
j++;
}
else if (i < n && i < j) {
i++;
}
}
return count;
}
// Driver Code
const k = 1;
const arr = ['P', 'T', 'T', 'P', 'T'];
console.log(catchThieves(arr, k));
Output
2