I have a question here and I am trying to find a solution of it. But I want to see some other opinions as well.
The problem is the following:
There is a matrix NxN which holds integer numbers. You should count all the different numbers in the matrix with the following conditions:
- If two-or-more same numbers are adjacent (left, right, above, below) each of other it counts as one.
Example of the matrix:
1 2 3 4
1 1 2 4
5 6 2 2
So for the above example there are: 7 different numbers because at the position of matrix : [1,1][2,1][2,2] there are 1s which has the condition of the problem true therefore these 3 numbers counts as one, at position [1,4][2,4] there are 4s so counts as one as well, and finally at positions [2,3],[3,3] and [3,4] there are 3s so count as one number.
My thought is to set the duplicate numbers to negative and then count only the positives, but I am not sure if that will work for all cases including and the corner cases.
My Code:
public class matrix
{
public static void main(String[] args)
{
int[][] arr =
{
{1, 2, 3, 4},
{1, 1, 2, 4},
{5, 6, 2, 2},
};
for(int row = 0; row < arr.length; ++row)
{
for(int col = 0; col < arr[row].length; ++col)
{
//top
if(row!=0)
{
if((arr[row][col] == arr[row-1][col]) || (Math.abs(arr[row][col]) == arr[row-1][col]) || (arr[row][col] == Math.abs(arr[row-1][col])))
{
arr[row-1][col] = -arr[row-1][col];
}
}
//botom
if(row!=arr.length-1)
{
if(arr[row][col] == arr[row+1][col] || Math.abs(arr[row][col]) == arr[row+1][col] || arr[row][col] == Math.abs(arr[row+1][col]))
{
arr[row+1][col] = -arr[row+1][col];
}
}
//left
if(col!=0)
{
if(arr[row][col] == arr[row][col-1] || Math.abs(arr[row][col]) == arr[row][col-1] || arr[row][col] == Math.abs(arr[row][col-1]))
{
arr[row][col-1] = -arr[row][col-1];
}
}
//right
if(col!=arr[0].length-1)
{
if(arr[row][col] == arr[row][col+1] || Math.abs(arr[row][col]) == arr[row][col+1] || arr[row][col] == Math.abs(arr[row][col+1]))
{
arr[row][col+1] = -arr[row][col+1];
}
}
}
}
for(int row = 0; row < arr.length; ++row)
{
for(int col = 0; col < arr[row].length; ++col)
{
System.out.print(arr[row][col] + " ");
}
System.out.println();
}
}
}
Expected Outcome:
1 2 3 4
-1 -1 2 -4
5 6 -2 -2
Code Outcome:
1 2 3 -4
1 -1 -2 -4
5 6 2 -2
8
My thought is to set the duplicate numbers to negative and then count only the positives
It sounds like you’re using negatives as an “isDuplicate” flag. This is a great example of the difference between competitive programming and professional programming.
In a competitive environment, you’re trying to optimize the time it takes to write the program. Declaring more variables (e.g. declaring an explicit “isDuplicate” data-structure) would require t.y.p.in.g. m.o.r.e. c.o.d.e. w.h.i.c.h. t.a.k.e.s. m.o.r.e. t.i.m.e. You don’t have to declare anything new to use negatives, so you don’t have to type as much, so it feels like that might be a productive approach.
In a professional environment, I would never consider using negatives this way. Use negatives if you actually want to perform arithmetic on negatives. There are several reasons:
- Negatives have peculiar properties — e.g. “1 + -1 == 0” and “-1 * -1 == +1”; these properties are nonsensical for the isDuplicate flag.
- Most other developers (who review/update your code) wouldn’t readily intuit the idea that “negative” means “isDuplicate” (unless, by some miracle, they were also competitive coders working from the same narrow problem-definition in the same narrow time-frame).
- Requirements change. Today, “isDuplicate” is important information. Tomorrow, “isPrime” might be important information. Next week, we might decide to drop the “isDuplicate” information. The only way to keep these things straight is to give them very clear names.
As it happens, your bug does in fact relate to one of those peculiar properties of negative numbers. (I’ll bite my tongue on the specific problems because, as the commenters noted, it’s good for you to work through it.)