Cavity Map

Based on an email message from HackerRank I decided to accept the Cavity Map challenge. The description for the challenge may be found using the following URL:  https://www.hackerrank.com/challenges/cavity-map?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=3-day-campaign

As usual, if interested please read the description and give it a try.

The Need Help link on the page discusses string basics. In this case I did not find the help of use.

Following is a screen capture of the console in the Eclipse IDE using the sample input and my output:

4

1112

1912

1892

1234

1112

1X12

18X2

1234

The top row, left column, bottom row and right column should not have any cell flagged with an X. If you have an X in them there is an issue with your solution. The challenge states:

“We will call a cell of the map a cavity if and only if this cell is not on the border of the map and each cell adjacent to it has strictly smaller depth. Two cells are adjacent if they have a common side (edge)”.

My solution could have been simplified by directly writing the output to the console instead of flagging it in the map[][] and then using it to generate the output using the outputMap() method. That said, since it passed all 22 test cases, I decided to leave it as is.

My solution to the challenge written in Java follows:

import java.util.Scanner;

public class Solution {

/**

* Check and flag if this position is a cavity.

* This cell is a cavity if each cell adjacent to it has STRICTLY smaller depth.

*/

static void checkIfCavity (int[][] map, int i, int j) {

// **** top ****

if (Math.abs(map[i – 1][j]) >= map[i][j]) {

return;

}

// **** right ****

if (Math.abs(map[i][j + 1]) >= map[i][j]) {

return;

}

// **** bottom ****

if (Math.abs(map[i + 1][j]) >= map[i][j]) {

return;

}

// **** left ****

if (Math.abs(map[i][j – 1]) >= map[i][j]) {

return;

}

// **** flag it as a cavity ****

map[i][j] *= -1;

}

/**

* Flag cavities in the specified map

*/

static void flagCavities(int[][] map) {

int n = map.length;

if (n <= 2) {

return;

}

for (int i = 1; i < (n – 1); i++) {

for (int j = 1; j < (n – 1); j++) {

checkIfCavity(map, i, j);

}

}

}

/**

* Display the map.

*/

static void show(int[][] map) {

int n = map.length;

System.out.println(“show <<< n: ” + n);

for (int i = 0; i < map.length; i++) {

for (int j = 0; j < map.length; j++) {

System.out.print(map[i][j]);

}

System.out.println();

}

}

/**

* Output the map showing cavities.

*/

static void outputMap(int[][] map) {

int n = map.length;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

if (map[i][j] > 0) {

System.out.print(map[i][j]);

} else {

System.out.print(“X”);

}

}

System.out.println();

}

}

/**

* Test code.

*/

public static void main(String[] args) {

// **** ****

Scanner sc    = new Scanner(System.in);

int n         = sc.nextInt();

String line = sc.nextLine();

int[][] map = new int[n][n];

for (int i = 0; i < n; i++) {

line = sc.nextLine();

for (int j = 0; j < n; j++) {

map[i][j] = line.charAt(j) – 48;

}

}

// **** ****

sc.close();

//            show(map);

// **** ****

flagCavities(map);

//            show(map);

// **** ****

outputMap(map);

}

}

The show() method was only used during development of the solution.

If you have comments / questions regarding this blog entry or any other entry in this blog, please do not hesitate and send me an email message. I will reply as soon as possible and will not use your name unless you explicitly allow me.

John

john.canessa@gmail.com

Follow me on Twitter: @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.