title: Hackerearth policeman and theives problem
body: <p>I am trying to solve the Policeman and Theives problem in Hackeearth website. I am able to reduce the time complexity but three test cases are failing. There seems to be a bug in the solution which causes a small mismatch. I am struggling to find the error for weeks. Below are the problem statement and my code,</p>
  
  <p><strong>Policeman and Thieves Problem statement:</strong></p>
  
  <p>You are given a grid of size  that has the following specifications:</p>
  
  <ul>
  <li>Each cell in the grid contains either a policeman or a thief.</li>
  <li>A policeman can only catch a thief if both of them are in the same row.</li>
  <li>Each policeman can only catch one thief.</li>
  <li>A policeman cannot catch a thief who is more than K units away from the policeman.
  Write a program to find the maximum number of thieves that can be caught in the grid.</li>
  </ul>
  
  <p><strong>Input format</strong></p>
  
  <ul>
  <li><p>First line: T (number of test cases)</p>
  
  <p>For each test case, </p>
  
  <ul>
  <li>First-line contains Two space-separated integers N and K</li>
  <li>Next N lines contain N space-separated characters (denoting each cell in the grid)</li>
  </ul></li>
  </ul>
  
  <p><strong>Output format</strong></p>
  
  <p>For each test case, print the maximum number of thieves that can be caught in the grid.</p>
  
  <p><strong>My code:</strong></p>
  
  <pre><code>import java.io.*;
  import java.util.*;
  
  public class TestClass {
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          PrintWriter wr = new PrintWriter(System.out);
          int T = Integer.parseInt(br.readLine().trim());
          for(int t_i=0; t_i&lt;T; t_i++)
          {
              String[] line = br.readLine().split(" ");
              int N = Integer.parseInt(line[0]);
              int K = Integer.parseInt(line[1]);
              char[][] A = new char[N][N];
              for(int i_A=0; i_A&lt;N; i_A++)
              {
                  String[] arr_A = br.readLine().split(" ");
                  for(int j_A=0; j_A&lt;arr_A.length; j_A++)
                  {
                      A[i_A][j_A] = arr_A[j_A].charAt(0);
                  }
              }
  
              int out_ = solution(A, K);
              System.out.println(out_);
              System.out.println("");
          }
  
          wr.close();
          br.close();
      }
      static int solution(char[][] A, int K){
          int count = 0;
          for(int i=0;i&lt;A.length;i++){
              for(int j=0;j&lt;A[i].length;j++){
                  if(A[i][j]=='P'){
                      boolean thiefCaptured = false;
                      int x;
                      if(j-K &gt;0){
                          x = j-K;
                      }else {
                          x = 0;
                      }
                      for(;x&lt;j;x++) {
                          if (A[i][x] == 'T') {
                              A[i][x] = 'X';
                              A[i][j] = 'X';
                              count++;
                              thiefCaptured = true;
                              break;
                          }
                      }
                      int y;
                      if(j+K &lt; A[i].length){
                          y = j+K;
                      }else{
                          y = A[i].length - 1;
                      }
                      for(;(y&gt;j) &amp;&amp; (thiefCaptured == false);y--){
                          if(A[i][y]=='T'){
                              A[i][y] = 'X';
                              A[i][j] = 'X';
                              count++;
                              break;
                          }
                      }
                  }
              }
          }
          return count;
      }
  }
  </code></pre>
  
  <p><strong>My Logic</strong>
  If an element is considered as the center of our search, then I am first looking for the thieves from the farthest left(by k units) and iterating towards the center. If the thief is not found, then I am looking for the thief from the farthest right(by k units) towards the center.</p>
  
  <p>Failing test case input:</p>
  
  <pre><code>1
  18 2
  P P T T T P T P P T T P P P T P P T
  P P P P T P P T P P T P P P T P T P
  P P P T T T T T P P T P T P T T P T 
  P P P P P P T P P P T T T P T T T P
  P P T P P T P P P T T P P T P P P T
  P T P P P P P P P P P P T T P T P P
  T P T T T P P P P T P T T T T P T P
  T T P T P P P P P P P T T T P T P P
  P T T T T P T T P T P P P P T T P T
  P T P P T T P P P P P T T P T P P P
  P T P T T P T P T P T P P P P P P T
  P T P P T P T P T P T P T T T P P P
  T T P T P P P P P P T T T P T P T P
  P T T P P P P P T P T P T P T P P T
  P T P T T P T P T P P P P T P T P P
  T P P P T P T P P P P P T T P P P P
  P P T P P P P P P P P T T T P P T P
  T T T P T P T P T P P T P P T P P P
  </code></pre>
  
  <p><strong>Expected Ouput</strong>
  113</p>
  
  <p><strong>Actual Output</strong>
  112</p>
  
  <p>Can you guys help me to figure out where I am going wrong? I am actually trying to figure out the solution for weeks but not able to progress. I know there is a different solution out there for the same question. But the thing is I would like to figure out the issue or the hole in my logic. Please help me out.</p>
  
  <p><strong>Link:</strong> <a href="https://www.hackerearth.com/practice/algorithms/searching/linear-search/practice-problems/algorithm/joker-and-thieves-53e59f4a/" rel="nofollow noreferrer"><em>Policemen and thieves</em> on hackerearth</a></p>