- Practice
- Algorithms
- Implementation
- Cavity Map
- Discussions

# Cavity Map

# Cavity Map

Michael123 + 16 comments no need to read the input as string . read it as int using "scanf("%1d",your array[i)[j]);" ...read only a single digit at a time

Hitesh_Parmar + 1 comment Thanks a lot...Your solution helped

Michael123 + 0 comments You're welcome

callmesahil21 + 1 comment Thanks man it helped.

Michael123 + 0 comments Your're Welcome

H1996 + 1 comment Thanks

Michael123 + 0 comments You're Welcome

shivam_merothiya + 0 comments thanx alot

_Radix_ + 2 comments Can you do it in C++ without using C commands?

saksham1999 + 0 comments Using C++

int main(){ int n; cin >> n; vector grid(n); for(int i = 0; i < n; i++){ cin >> grid[i]; } std::string::iterator it,jt1,jt2; int c=0; char temp; for(int i = 1; i < n-1; i++) { c=0; int d=0,e=0; for (it=grid[i].begin(); it!=grid[i].end(); it++) { c++; if(c>1 && c*jt1) {

`for(jt2=grid[i+1].begin(); jt2!=grid[i+1].end(); jt2++) { e++; if(e==c) { if(temp>*jt2) temp='X'; } } } } } } *it=temp; } } } for(int i = 0; i < n; i++) cout<< grid[i]<<endl; return 0;`

}

thevkc + 3 comments vector <string> cavityMap(vector <string> arr) { int n = arr.size() ; for(int i = 1 ; i < n-1 ; i++) //ignoring first and last rows { for(int j = 1 ; j < n-1 ; j++) //ignoring first and last columns { if( arr[i][j]-48 > arr[i-1][j]-48 && arr[i][j]-48 > arr[i+1][j]-48 && arr[i][j]-48 > arr[i][j-1]-48 && arr[i][j]-48 > arr[i][j+1]-48) arr[i][j] = 'X'; } } return arr ; }

yashu191298 + 0 comments you cant replace it during the check.

akshaykumsharma + 0 comments not need to put 48 in comparison

meaditi + 2 comments Why u substracted with 48???

viigihabe + 0 comments https://stackoverflow.com/questions/439573/how-to-convert-a-single-char-into-an-int There is a comment in top answer that states that -48 woun't work on every encoding. There is another aspect - your question. Would you have a question if the code was: arr[i][j] - '0' ...? Probably not. In my opinion the use of -48 falls into bad practice. And note: because both operands are subtracted the subtraction itself is obsolete.

h160040582 + 0 comments he has taken the array as string and so for comparing numbers he subtracted the array with ascii value of number '0' i.e. 48 which will give the number directly during comparison.

Mandeep31 + 1 comment That works, but it's easier to do using string (or char array) because you can easily assign a cell to 'X' if it's a cavity, which would be a better approach (in my opinion). Moreover, comparing characters works fine as well since ascii value '9' > '8' > '7' > ...

learningprakash + 0 comments for scanning use int and For Placing X put it in string row grid[]

omkar8kadam + 4 comments how to store X in int array

phoenixRises + 0 comments You can't. What you can do is, do the comparisons and output at the same time, so when you find a cavity, output an X instead of the digit. While you could have read the input as characters and compared and assigned the X, using integers is generally easier to understand, so I would prefer reading the input as integer. But if you want to stick to keeping the processing and output separate, use a 2D character array.

lakshmikantd + 0 comments Why would one store X if you can store a sentinel value(say Integer.MAX_INT), and print X while printing, when a sentinel is encountered

rvrishav7 + 0 comments make it string array

sharadsingh + 0 comments I suggest you to change the number when their is any cavity to any negative number (let us change cavity a[i][j] to value -1) and then while printing you print the value 'X' in place of that negative number.

ennorehling + 0 comments There's also no need to interpret the input as digits. '9' is strictly larger than '8' as well, etc.

archit_agrawal31 + 1 comment how do i print the array

lakshmikantd + 1 comment for loops will exclude all elements at the edge (Only - elements in the following diagram)

+++++ +---+ +---+ +---+ +++++

check all the inner elements' left, right, upper and lower elements. If these elements are smaller than the center element, change it to Integer.MAX_INT.

While printing, simply print X if Integer.MAX_INT is encountered. ;)

positivedeist_07 + 1 comment Same I did, but instead of assigning MAX_INT, I assigned -1. Not working :(

lakshmikantd + 2 comments Let's consider a test case

let the original matrix be

1 1 1 1 1 5 4 1 1 1 1 1 1 1 1 1

In this case, your program will mark 5 to -1, as all the surrounding elements are smaller than 5.

1 1 1 1 1 -1 4 1 1 1 1 1 1 1 1 1

But now in the next iteration for 4, all the surrounding elements (including -1) are smaller than 4, so it will mark 4 as -1 as well.

it will print output as

1 1 1 1 1 x x 1 1 1 1 1 1 1 1 1

But it should have printed

1 1 1 1 1 x 1 1 1 1 1 1 1 1 1 1

I faced the same problem. So I changed -1 to Integer.MAX_INT.

Let me know if you need more help. All the best.

yashp241195 + 0 comments You saved my life bro :)

Power_Of_Chi + 0 comments The output will be .... right?

1 1 1 1 1 x 4 1 1 1 1 1 1 1 1 1

archit_agrawal31 + 0 comments how do i print the array

charan_sai + 0 comments [deleted]leech932 + 1 comment If you're dong this in C there's no point in doing the ascii to number conversion, use scanf(" %c",&array[x][y]);

You can take advantage of the fact that ascii 'X' > ascii'9' > ascii '1' and just compare the chars directly.

viigihabe + 0 comments Basically there is no need to convert them in any language, since comparison of characters leads to same conclusion. Any language will consider "12" > "13" as falsy. And "9" > "8" as truthy.

edrouwendaal + 1 comment C# read as string

static string[] cavityMap(string[] grid) { for (int i = 1; i < grid.Length - 1; i++) { for (int j = 1; j < grid[i].Length - 1; j++) { int middleUpper = (int)char.GetNumericValue(grid[i - 1][j]); int left = (int)char.GetNumericValue(grid[i][j - 1]); int right = (int)char.GetNumericValue(grid[i][j + 1]); int middleUnder = (int)char.GetNumericValue(grid[i + 1][j]); var adjacent = new int[4] { middleUpper, left, right, middleUnder }; if (adjacent.Any(a => a < 0)) continue;//smaller than 0 if X in adjacent cell int ij = (int)char.GetNumericValue(grid[i][j]); if (adjacent.All(a => a < ij))//Can use StringBuilder instead(faster?) grid[i] = grid[i].Remove(j, 1).Insert(j, "X"); } } return grid; }

sduhigg + 0 comments Nice.

I got hung up on the replacing the X part, almost had it, just didn't have the remove before the insert.

harshchaplot11 + 0 comments Thanks man!!! I was confused how to take the input

hrshtvrm + 0 comments For the Java people wondering how to accept the String matrix, here is a way,

` char c[][]=new char[n][n]; String s[]=new String[n];

`for(int i=0;i<n;i++){ s[i]=sc.next(); } for(int i=0;i<n;i++){ int k=0; for(int j=0;j<n;j++){ c[i][j]=s[i].charAt(k); k++; }}`

kumar_ak16121999 + 0 comments thanks a lot man i have just wasted more than 1 hr and i was not able to figure out my mistake.

sayantanmaiti + 1 comment Why does Test Case #2 have spaces in the input grid? Although submitting the code that works for the Test Case #1 (one without the spaces) works fine for everything else, and gives the full 30 points,

I kind-of wasted my time because my code was reading the spaces in the grid rather than the number itself.

turkerunlu + 1 comment I also had the same issue, there is also the same issue in one of test cases when you submit but I still got full points even though that case failed.

cheesus + 2 comments the conditions are:

1) is right or left of the current value a value that is greater or equals

2) is above or below of the current value a value that is greater or equals

3) is it in the first or last row or is it the first or last number

if so it cant be a cavity

I just created an inverse of a 2 dimensional array and checked those conditions for both matrices. Even its O(N*N) it doesnt needs a 1/10 of a second

thanhbinh84 + 0 comments strictly smaller depth

->

1) is right or left of the current value a value that is greater or equals

2) is above or below of the current value a value that is greater or equals

Should be

1) is right or left of the current value a value that is greater

2) is above or below of the current value a value that is greater

ashish09712 + 2 comments Conditions: right,left,top,down < center

RoshithS + 0 comments helpful. i ws nt getting the scenario exactly

theoriginscode13 + 1 comment Thanks brother you saved my time. Initially I just took for the adjacent ones in the row only.

rohit1007raj + 0 comments Same here buddy. Thanks for this thread.

selftaught91 + 4 comments Read your input as string and not as integers then the problem can be solved

ajayu2bono + 1 comment Thanks that was my mistake

devs_338374 + 1 comment if i take input as string the how will you print the numbers inside it

PRASHANTB1984 + 1 comment you need to use the equivalent of Java's Big Integer after processing the string and parsing it into numbers. Or, in languages like Ruby and Python, you don't need to do anything special to handle very large numbers, much of the time.

harshulgandhi + 1 comment Do we really need to parse it into numbers. We can simply take Char 2D array and input each integer as a string. Then divide this string into individual characters (there are multiple ways of doing that). Comparison also works fine if we keep it to char array because ascii value of (char) '9' > '8' > '7' ...'2' > '1'

Moghaak + 0 comments I tried this one in CPP my code reduced from 75+ lines to 25 lines.

Thanks.

khalludi123 + 2 comments Not always. You can still read it as numbers. I used Java's BigInteger.

thejay10125 + 0 comments [deleted]Omnikron13 + 1 comment What is the point though? It ISN'T an integer, it is a string of integers...

mlobosco + 0 comments I ended up using BigInteger as well and it ended up being relatively simple. The difficult part was keeping track of the Int/BigInteger operations.

rsb33 + 0 comments thnX..

Gautham_B_A + 4 comments Use Python. You don't have to worry about the type. :P

roryneil + 1 comment Ha! So true. I converted the ints to strings to convert them into lists, and solved the problem. I never noticed that I never converted each char in the array back to an int for comparison, but everything worked! Plus, I saw something about 75 lines above?

amazing_naina + 0 comments How did you mutate the str object?

akashshetty08 + 0 comments [deleted]akashshetty08 + 0 comments [deleted]akashshetty08 + 5 comments n = int(input())

a = []

for i in range(n):

`a.append(list(input()))`

for i in range(1,n-1):

`for j in range(1,n-1): if a[i][j] > a[i+1][j] and a[i][j] > a[i-1][j] and a[i][j] > a[i][j+1] and a[i][j] > a[i][j+1]: a[i][j]="X"`

for i in range(n):

`print("".join(str(x) for x in a[i]))`

Can you tell me what the error is?

AffineStructure + 0 comments you can make your code more readable if you stack the if statement like this

for j in range(1,n-1): if (a[i][j] > a[i+1][j] and a[i][j] > a[i-1][j] and a[i][j] > a[i][j+1] and a[i][j] > a[i][j-1]): a[i][j]="X"

I also fixed the error in the code. the for loop in your code had j+1 for both the first and second check.

pbppiyush + 0 comments grid[i][j]>=grid[i-1][j-1] && grid[i][j]>=grid[i-1][j] && grid[i][j]>=grid[i-1][j+1] && grid[i][j]>=grid[i][j-1] && grid[i][j]>=grid[i][j+1] && grid[i][j]>=grid[i+1][j-1] && grid[i][j]>=grid[i+1][j] && grid[i][j]>=grid[i+1][j+1]

maitrayan6p + 0 comments how can you compare str values? You first have to convert in into string then you can compare the values

murali_111 + 1 comment You replace the element with 'X' while iterating, and again whn you are checking the previous element with [j-1] , if it is 'X' it will check if your element is greater than 'X'., so you should check if your [j-1] or [i-1] is 'X' or not. Just add this to your if statement.

mike_buttery + 0 comments Python can evaluate strings including numbers and letters

>>> '0'<'1'<'2'<'3'<'4'<'5'<'6'<'7'<'8'<'9'<'X' True

As you iterate through the grid the cavities are marked with the

`'X'`

where all the adjacent cells are less than. For example1111 1911 1911 1111

returns with no cavities as

`9`

and`9`

are equal.If we replace with an

`X`

it is because the surrounding cells evaluate as less than.So if

`9 > 8`

so too is`X > 8`

so the relationship between the cells is maintained and there is no need to check for`X`

Devicharith + 0 comments how does line 3 and 4 work in python??

_CAAI + 10 comments Instead of using two arrays, compare the center matrix (formed excluding boundary values) while printing the matrix..! ;)

`int n,i,j; scanf("%d",&n); int a[n][n]; for(i=0;i<n;i++) { for(j=0;j<n;j++) { scanf("%1d",&a[i][j]); } } for(i=0;i<n;i++) { for(j=0;j<n;j++) { if( (i>=1)&&(i<n-1) && (j>=1)&&(j<n-1) ) { if( (a[i][j] > a[i-1][j]) && (a[i][j] > a[i][j+1]) && (a[i][j] > a[i+1][j]) && (a[i][j] > a[i][j-1]) ) printf("X"); else printf("%d",a[i][j]); } else printf("%d",a[i][j]); } printf("\n"); }`

inkhl + 0 comments Thanks!

SushmaN + 1 comment if we replace %1d with %d... why the input contains extra zeros?? what is the significance of 1? can you please explain..

phoenixRises + 2 comments %1d signifies read 1 digit at a time. If you write %d, one entire row of digits will be read at once, which is not what you want.

patomack + 0 comments Nifty!

priyank042 + 0 comments yeah..!! Thanks.....

amanakmsd + 0 comments Thanks! Very helpful

sb2098 + 0 comments coool!

160216733001_cs + 0 comments nice

ME_170070246 + 0 comments thank you for the code

psatishkumar720 + 0 comments [deleted]hardikkamboj1 + 1 comment I had also gone with the same logic..but the problem is that some test cases contain spaces whereas some test cases don't have spaces.. Please help me on that..

zalak_delvadiya + 1 comment Same problem....... Any solution?????

frankdeadlycaste + 0 comments def cavityMap(grid): M = grid N = len(M)

`for i in range(N): for j in range(N): if not ( i in [0,N-1] or j in [0,N-1] ): c = M[i][j] if M[i-1][j] < c and M[i+1][j] < c and M[i][j-1] < c and M[i][j+1] < c : temp = M[i] temp = list(temp) temp[j] = 'X' temp2='' for j in temp: temp2+=j M[i] = temp2 return M`

yashtekena + 0 comments Python Implementation:

Just concentrate on (n-2)X(n-2) matrix as we need to ignore the borders

n = int(input().strip()) grid = [] grid_i = 0 for grid_i in range(n): grid_t = list(str(input().strip())) grid.append(grid_t) for i in range(1,(n-2)+1): for j in range(1,(n-2)+1): if grid[i][j]>max(grid[i-1][j],grid[i+1][j],grid[i][j-1],grid[i][j+1]): grid[i][j]='X' for i in range(n): print (''.join(grid[i]))

maximshen + 5 comments I implemented as following, but I don't think it is efficient enough. Does anyone have some suggestions ?

import java.io.

*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*;{code}

public class Solution {

`public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); String grid[] = new String[n]; for(int grid_i=0; grid_i < n; grid_i++){ grid[grid_i] = in.next(); } for(int i=1; i<n-1; i++){ for(int j=1; j<n-1; j++){ int left = Character.getNumericValue(grid[i].charAt(j-1)); int right = Character.getNumericValue(grid[i].charAt(j+1)); int up = Character.getNumericValue(grid[i-1].charAt(j)); int down = Character.getNumericValue(grid[i+1].charAt(j)); int middle = Character.getNumericValue(grid[i].charAt(j)); char mid = grid[i].charAt(j); if(left<middle && up<middle && right<middle && down<middle){ StringBuilder sb = new StringBuilder(grid[i]); sb.setCharAt(j, 'X'); grid[i] = sb.toString(); } } } for(int grid_i=0; grid_i < n; grid_i++){ System.out.println(grid[grid_i]); } }`

}

{code}

SergioGM + 0 comments [deleted]SergioGM + 0 comments I did it almost like you. I just didnt use StringBuilder, only System.out.print(char) everytime you deal with one of them into the deepest for loop, and System.out.println() everytime that loop ends, so you can keep some memory space and also the last for loop for printing the grid is not necessary.

I dont know if there's a better solution in Java, but I bet this one could be =)

yli131 + 0 comments no need to use stringbuilder

grid[i] = grid[i].substring(0,j) + "X" + grid[i].substring(j+1);

FilipF + 0 comments I'll add my voice in

*favor*of using a StringBuilder, although I admit not in the way that maxinshen chose to use it.The problem with SergioGM's suggestion is that writing to the output buffer one character at a time can really slow things down, because it will get flushed after each of those write operations. There's challenges on HR where trying that will result in a TE.

With yli131's suggestion, you'd be slowing things down, because ironically the compiler will use a StringBuilder to perform those concatinations. It's slower overally because it will need the substrings first, so it produces wholly new String objects for each one, and then throws them away.

My own suggest is to move the

`sb`

instantiation outside of the`for(int j ...)`

loop, modify`sb`

as needed, and then after the inner loop finishes write the new value back to`grid[i]`

.### One other thing...

Instead of doing a somewhat expensive and unnecessary function call with

`.getNumericValue()`

, you can convert the digits yourself. To do that, you take advantage of the fact that`char`

s are just numbers under the hood, and that the input format for this challenge uses simple ASCII. That means the digits 0 to 9 have sequential integer values, and so`'3' - '0' == 3`

. If you're curious, you can click through the source here.Hope some of that was interesting and useful!

madhu703 + 0 comments Thanx

gautamji + 1 comment Just create a 2 dimensional array and check each value for the conditions, if it is at the border or less than an adjacent cell, print out the number else print out X

roughneckgrub + 1 comment this is how I did it, 2 dimension array then compared in for loop against adjacent arrays, using key of current char and replaced current value with X if conditions are met. No tests took longer than .02s.

Avinash014 + 0 comments my solution is same as you describing and it is running fine on dev-c++ but here its not working.

iDamOo + 2 comments I read each line as a string then converted the whole thing to a 2D array. This isn't the full code, but the technique works for me

`Scanner in = new Scanner(System.in); int n = in.nextInt(); char [][]charArray = new char[n][n]; for (int i = 0; i < n; i++) { String lines = in.next(); charArray[i] = lines.toCharArray(); } for (int i = 1; i < n-1; i++) { for(int j = 1; j < n-1; j++) { if((charArray[i][j] > charArray[i-1][j]) && (charArray[i][j] > charArray[i+1][j]) && (charArray[i][j] > charArray[i][j-1]) && (charArray[i][j] > charArray[i][j+1])) charArray[i][j] = 'X'; } }`

Tannia + 1 comment You are assigning a line of string into a 1D array. Then how does it automatically become a 2D array?

iDamOo + 0 comments The code does not assign the line of string into a 1D array. In the code, charArray is a 2D array (an array of arrays). The line which has "charArray[i] = lines.toCharArray" converts the string to an array of characters, and this array of characters is then stored in charArray[i]. Hence, filling the i-th position of the 2D array.

ArtyomKarpov + 1 comment Authors or administrators! Test cases are wrong. They have ' ' or sometime they don't! Nothing about that in the statement. Wasted time on this

Coder_MS + 0 comments Yes absolutely! Even Sample test case 1 has ' ' in it, while 0 clearly does not. pfft!

Sort 430 Discussions, By:

Please Login in order to post a comment