Blog

Home / Blog / My PHP solution to Queen's Attack II @ HackerRank

My PHP solution to Queen's Attack II @ HackerRank

Jul 15, 2019

Please check the problem explanation here: https://www.hackerrank.com/challenges/queens-attack-2/problem

Therefore, we need to check how many moves the queen can make on the board with size of NxN. Also calculate that the queen can not jump over obstacles.

Few examples:

Example #1:

Solution: 24

Example #2:

 

Solution: 9

Example #3:

Solution: 10

I googled for a solution and all of them was hard to explain and write. So I tried to find my solution.

My first idea was to calculate distances between the quen and the edges of the board (in all 8 ways) by calculating X and Y coordinates of the queen and N (size of the board). Then subtract distances between obstacles getting into the way between the queen and edges.

But it was quite hard to implement, at least for me. It might be easier for a good mathematician.

Final solution

The 2nd solution is to move the queen in all 8 ways and count steps until we get to a obstacle or an edge of the board. We simply use 2 pointers X and Y and make 8 while loops.

Optimization

To avoid looping through the array of obstacles (max size of 10 ^ 5) to find if there is an obstacle on the current field, I simply indexed all obstacles in the array like this:

$obstacles_indexed[$row . ‘-‘ .$col] = true

so checking if the point is obstacle is complexity of O(1).

The solution implementation in PHP is here:

function queensAttack($n, $k, $r_q, $c_q, $obstacles) {

               // Index obstacles in next format: ob[row-col] = true

               $obstacles_indexed = [];

               foreach ($obstacles as $ob) {

                               $obstacles_indexed[$ob[0].'-'.$ob[1]] = true;

               }



               // Go each direction and increase counter until we get to the end of the board or to an obstacle



               $counter = 0;



               // up:

               $r_p = $r_q + 1;

               $c_p = $c_q;

               while ( ! isset($obstacles_indexed[$r_p.'-'.$c_p]) && $r_p <= $n ) {

                               $counter++;

                               $r_p++; // go up

               }

               //down:

               $r_p = $r_q - 1;

               $c_p = $c_q;

               while ( ! isset($obstacles_indexed[$r_p.'-'.$c_p]) && $r_p >= 1 ) {

                               $counter++;

                               $r_p--;//go down

               }

               //left:

               $r_p = $r_q;

               $c_p = $c_q - 1;

               while ( ! isset($obstacles_indexed[$r_p.'-'.$c_p]) && $c_p > 0 ) {

                               $counter++;

                               $c_p--;//go left

               }

               //right:

               $r_p = $r_q;

               $c_p = $c_q + 1;

               while ( ! isset($obstacles_indexed[$r_p.'-'.$c_p]) && $c_p <= $n ) {

                               $counter++;

                               $c_p++;//go left

               }



               // up-right:

               $r_p = $r_q + 1;

               $c_p = $c_q + 1;

               while( ! isset($obstacles_indexed[$r_p.'-'.$c_p]) && $c_p <= $n && $r_p <= $n ){

                               $counter++;

                               $c_p++;//go right

                               $r_p++;//go up

               }



               // up-left:

               $r_p = $r_q + 1;

               $c_p = $c_q - 1;

               while( ! isset($obstacles_indexed[$r_p.'-'.$c_p]) && $c_p > 0 && $r_p <= $n ){

                               $counter++;

                               $c_p--;//go left

                               $r_p++;//go up

               }

               // down-right:

               $r_p = $r_q - 1;

               $c_p = $c_q + 1;

               while( ! isset($obstacles_indexed[$r_p.'-'.$c_p]) && $c_p <= $n && $r_p > 0 ){

                               $counter++;

                               $c_p++;//go right

                               $r_p--;//go down

               }

               // down-left:

               $r_p = $r_q - 1;

               $c_p = $c_q - 1;

               while( ! isset($obstacles_indexed[$r_p.'-'.$c_p]) && $c_p > 0 && $r_p > 0 ){

                               $counter++;

                               $c_p--;//go left

                               $r_p--;//go down

               }



               return $counter;



} // function

 

Complexity of this solution is: O ( 5n + k ).