4
\$\begingroup\$

Please can you suggest a better / Optimized logic or code for the question. It has been asked that when you find a zero value in a matrix, make that element the sum of its upper, lower ,left, right value and make the upper, lower ,left, right elements zero. I assume to the matrix provided has at least 2 rows and 2 columns but if you can post code for any type of matrix , it would be of utmost help. I have fully commented the code for easy understanding, just copy and paste it in editor and tweak the values of the matrix variable in the main function of the program.


import java.util.ArrayList;

public class Main {
    static void MakeSurroundingElementsZero(int i,int j,int[][]matrix){
        //when the element is not on the boundary of matrix.means it has
        // all surrounding elements
        if(i >0 && i < matrix.length-1 && j >0 && j < matrix[i].length-1){
             matrix[i][j-1]=matrix[i][j+1]=matrix[i-1][j]=matrix[i+1][j]=0;
        }
        //when it is in the first row
        else if(i ==0){
            // when it is not the first or last element in the first row
            if(j >0 && j < matrix[i].length-1){
                 matrix[i][j+1]=matrix[i][j-1]=matrix[i+1][j]=0;
            }
            //when it is the first element of the first row
            else if(j ==0){
                 matrix[i][j+1]=matrix[i+1][j]=0;
            }
            // when it is the last element of the first row
            else{
                matrix[i][j-1]=matrix[i+1][j]=0;
            }
        }
        //when the element is present in the last row
        else{
            //element not the last or the first in the last row
            if (j >0 && j < matrix[i].length-1 ){
                matrix[i][j+1]=matrix[i-1][j]=matrix[i][j-1]=0;
            }
            //first element in the last row
            else if (j==0){
                matrix[i-1][j]=matrix[i][j+1]=0;
            }
            //last element of the last row
            else{
                matrix[i][j-1]=matrix[i-1][j]=0;
            }
        }
    }
    static void addElements(int i,int j,int[][]matrix){
        //when the element is not on the boundary of matrix.means it has
        // all surrounding elements
        if(i >0 && i < matrix.length-1 && j >0 && j < matrix[i].length-1){
            matrix[i][j] = matrix[i][j-1]+matrix[i][j+1]+matrix[i-1][j]+matrix[i+1][j];
        }
        //when it is in the first row
        else if(i ==0){
            // when it is not the first or last element in the first row
            if(j >0 && j < matrix[i].length-1){
                matrix[i][j] = matrix[i][j+1]+matrix[i][j-1]+matrix[i+1][j];
            }
            //when it is the first element of the first row
            else if(j ==0){
                matrix[i][j] = matrix[i][j+1]+matrix[i+1][j];
            }
            // when it is the last element of the first row
            else{
                matrix[i][j] = matrix[i][j-1]+matrix[i+1][j];
            }
        }
        //when the element is present in the last row
        else{
            //element not the last or the first in the last row
            if (j >0 && j < matrix[i].length-1 ){
                matrix[i][j] = matrix[i][j+1]+matrix[i-1][j]+matrix[i][j-1];
            }
            //first element in the last row
            else if (j==0){
                matrix[i][j]= matrix[i-1][j]+matrix[i][j+1];
            }
            //last element of the last row
            else{
                matrix[i][j] = matrix[i][j-1]+matrix[i-1][j];
            }
        }
    }
    static void MakeZeroes(int[][] matrix) {
        ArrayList<Integer[]> zeroElements = new ArrayList<Integer[]>();
        for (int i = 0;i < matrix.length;i++) {
            for(int j = 0;j < matrix[i].length;j++){
                //checking each element for zero value
                if(matrix[i][j] == 0){
                    addElements(i,j,matrix);
                    //store it as we haven't made the surrounding elements zero yet

                    Integer[] zeroelem = {i,j};
                    zeroElements.add(zeroelem);

                }
            }
        }
        //finally, make surrounding elements zero
        for (int i = 0;i<zeroElements.size();i++){

                MakeSurroundingElementsZero(zeroElements.get(i)[0],zeroElements.get(i)[1],matrix);

        }
    }
    public static void main(String[] args) {
        int[][] matrix = {{2,0,4,0},
                          {5,9,7,9},
                          {2,0,8,0}};
        MakeZeroes(matrix);
        for (int i =0;i < matrix.length;i++){
            for (int j = 0; j < matrix[i].length;j++){
                System.out.print(matrix[i][j]+" ");
            }
            System.out.println();
        }


    }
}

My approach is to:-

  • Go to each element.
  • Check if it is zero or not.
  • If zero, then check where that element lies , whether totally inside the matrix or on the boundary.
  • Add accordingly the elements around that zero value element.
  • Store the index of that zero element in an ArrayList.
  • Loop the ArrayList to make the surrounding elements zero.
\$\endgroup\$
1
  • \$\begingroup\$ Can you use libraries other than the standard lib? \$\endgroup\$
    – IEatBagels
    Sep 8, 2021 at 12:35

4 Answers 4

3
\$\begingroup\$

There's something you'll learn while programming, it's that nesting (having multiple conditions/loops inside one another) makes code difficult to read. In this case, it also promotes code repetition, which is something we usually like to avoid.

Let's first look at MakeSurroundingElementsZero. The goal of that function is pretty clear, good job on that naming. Although something could be made better : Is it really the whole neighborhood or really just the directly adjacent elements? For example, is the result to :

[1, 2, 3]
[4, 0, 6]
[7, 8, 9] 

Supposed to be the first result or the second?

[1, 0, 3]
[0, 20, 0]
[7, 0, 9]

or

[0, 0, 0]
[0, 40, 0]
[0, 0, 0]

Looking at your code, it looks like the first answer is the right one, but from the description of the problem, it isn't clear. There's a name for these kind of neighborhoods in image processing that is 4-neighbor and 8-neighbor. The 4-neighbor represents the first example and 8-neighbord the second. Well, now that this is cleared up, onwards!

Regarding the code itself : my trick, when I work with algorithms, is to try and think of the simplest way to explain the algorithm, and start with that. In this case, we want to make the left,right,up,down positions values zero if they are within bounds of our matrix.

So, we have the following positions : [i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1] and we want to set them to zero if it's possible :

static void MakeSurroundingElementsZero(int i, int j, int[][] matrix){
    if (i - 1 > 0) {
        matrix[i-1][j] = 0;
    }
    if (i + 1 < matrix[i].length) {
        matrix[i+1][j] = 0;
    }
    if (j - 1 > 0) {
        matrix[i][j-1] = 0;
    }
    if (j + 1 < matrix[j].length) {
        matrix[i][j+1] = 0;
    }
}

This code checks if the 4 neighbors can be set to zero and does it. It's also much simpler than what you've written, but it does the job. The main takeaway from this is that you should try to decompose big problems into smaller ones, where solving all the small problems take care of the big one.

The same goes for the addElements function. We can use pretty much the same code. However, I introduced a variable named sumOfNeighbors. It's helpful to use variables when dealing with matrices because the whole indexing clutters the code, it makes it hard to read. Using a variable, we can define exactly what we're doing and we can then assign the sumOfNeighbors value to the center cell :

static void addElements(int i,int j,int[][]matrix){
    int sumOfNeighbors = 0

    if (i - 1 > 0) {
        sumOfNeighbors += matrix[i-1][j];
    }
    if (i + 1 < matrix[i].length) {
        sumOfNeighbors += matrix[i+1][j];
    }
    if (j - 1 > 0) {
        sumOfNeighbors += matrix[i][j-1];
    }
    if (j + 1 < matrix[j].length) {
        sumOfNeighbors += matrix[i][j+1];
    }

    matrix[i][j] = sumOfNeighbors;
}

As @Joop Eggen pointed out in their answer, there's an edge case that isn't considered in your description of the problem.

What happens in this scenario?

[1,2,3,4]
[5,0,0,6]
[7,8,9,10]

Should the result be :

[1,0,0,4]
[0,15,18,0]
[7,0,0,10]

or

[1,0,0,4]
[0,0,33,0]
[7,0,0,10]

or

[1,0,0,4]
[0,33,0,0]
[7,0,0,10]

Maybe you don't have the answer to this question, but it's also important to think about edge cases when programming!

All in all, your code really wasn't that bad, but you need to take a look at the problem in your head (or on paper) before writing the code in order to simplify it, so you can write better code :)

\$\endgroup\$
3
  • \$\begingroup\$ Yes, IEatBagels , My code has a lot of flaws, I realised now . Can you tell me is this a beginner level problem, I mean as a beginner am I supposed to have solved this question considering all the edge cases. I am still wondering what can be the proper code for this- Which can be understood by a beginner \$\endgroup\$
    – Aryaman
    Sep 8, 2021 at 18:36
  • \$\begingroup\$ I think the latter two options are rather far fetched, if just because they use some kind of unspecified ordering. Having a row of all zeros would also be an option if you ask me (and that may actually be the result in the code in the question, as you store which positions to zero in the List). But yeah, good catch of a problematic question. \$\endgroup\$ Sep 8, 2021 at 21:28
  • \$\begingroup\$ @Aryaman It's a good problem, I think you would've been able to solve this problem if you knew about how to handle the edge case. This might be a good exercise. Also, don't worry about flaws in your code, every code has some :) \$\endgroup\$
    – IEatBagels
    Sep 9, 2021 at 0:53
4
\$\begingroup\$
    }
    //when it is in the first row
    else if(i ==0){

Please don't do this. Yes, C-style languages support arbitrary amounts of whitespace (including comments) between a } and an else. The compiler will be happy with this. But separating the end of the previous block and the code that tells you the next block is part of the same structure is just making things more difficult. It makes it much easier for the next person who is editing the code to do something like

    } else {
        // do something here
    }
    //when it is in the first row
    else if(i ==0){

Which can either cause a compiler error or worse, can move your else if into a different control structure.

C-style languages do not differ between ending a block and ending the control structure. So please help readers by always keeping the } and the else as close as possible. If not on the same line (which I personally prefer), at least on adjacent lines. Code that does one thing when it looks like it does something else can be incredibly hard to debug.

\$\endgroup\$
3
\$\begingroup\$

Fitting Abstraction

Use spaces please. Let the IDE reformat your code.

The neighbors' offsets can be elements from {(1, 0), (-1, 0), (0, 1), (0, -1)}.

For instance:

private static final int[] UP = {-1, 0};
private static final int[] DOWN = {1, 0};
private static final int[] LEFT = {0, -1};
private static final int[] RIGHT = {0, 1};
// Num Pad orientaton:
// 7 8 9
// 4 5 6
// 1 2 3
private static final int[][] NEIGHBORS7 = {DOWN, RIGHT};
private static final int[][] NEIGHBORS8 = {DOWN, LEFT, RIGHT};
private static final int[][] NEIGHBORS9 = {DOWN, LEFT};
private static final int[][] NEIGHBORS4 = {UP, DOWN, RIGHT};
private static final int[][] NEIGHBORS5 = {UP, DOWN, LEFT, RIGHT};
private static final int[][] NEIGHBORS6 = {UP, DOWN, LEFT};
private static final int[][] NEIGHBORS1 = {UP, RIGHT};
private static final int[][] NEIGHBORS2 = {UP, LEFT, RIGHT};
private static final int[][] NEIGHBORS3 = {UP, LEFT};

int[][] neighbors(int i, int j, int[][] matrix) {
    if (i == 0) {
        if (j == 0) return NEIGHBORS7;
        if (j == matrix[0].length - 1) return NEIGHBORS9;
        return NEIGHBORS8;
    }
    if (i == matrix.length - 1) {
        if (j == 0) return NEIGHBORS1;
        if (j == matrix[0].length - 1) return NEIGHBORS3;
        return NEIGHBORS2;
    }
    if (j == 0) return NEIGHBORS4;
    if (j == matrix[0].length - 1) return NEIGHBORS6;
    return NEIGHBORS5;
}

for (int[] neighborIJ: neighbors(i, j, matrix)) {
    int nI = i + neighborIJ[0];
    int nJ = j + neighborIJ[1];
    ...
}

It is better to provide the available neighbors from every point, and walk through them to take their values.

So two abstractions: provide neighbors to loop over. And neighbor as offset, not calculated anew for every (i, j).

This will give less code, less branches, so glitches will be captured faster.

Java Style

Then there is:

    ArrayList<Integer[]> zeroElements = new ArrayList<Integer[]>();

which should be

    List<int[]> zeroElements = new ArrayList<>();

That is:

  • program against interfaces, most general code that way;
  • use diamond operator <>;
  • int[] is a class too, usable as generic type.

Beautifying

Instead of

System.out.print(matrix[i][j]+" ");

formatted looks nicer when the sums get more digits:

System.out.printf("%3d ", matrix[i][j]);

Algorithmic Questions

You collect candidates, and after that do the summation/heaping of values.

If one candidate is summed, then two other neighboring candidates may no longer be candidates, or get different sums. One steals from neighbor candidates.

It is probably done, as if one candidate is summed, automatically its neighbors become zero, hence a candidate too.

\$\endgroup\$
6
  • \$\begingroup\$ Apart from the spelling of "neighbor" or "neighbour" if you like, I truly dislike identifiers named using a counter such as NAYBOURS7 to be honest. What does that number represent? \$\endgroup\$ Sep 8, 2021 at 10:20
  • \$\begingroup\$ @MaartenBodewes I tried to americanize the British neighbour. The numbering is as one the numeric keypad 789 top line, then 456 in the middle and 123 at the bottom. I thought of adding a comment, but did not want to lengthen the answer. I'll correct the spelling \$\endgroup\$
    – Joop Eggen
    Sep 8, 2021 at 11:26
  • \$\begingroup\$ Yeah, I was assuming that it was a mistranslation. I'm a leighman myself when it comes to US spelling :P NEIGHBORS5 will probably hunt me tonight though. \$\endgroup\$ Sep 8, 2021 at 11:33
  • \$\begingroup\$ @MaartenBodewes your name seems Flamish, mine is Dutch, neighbours so to say. I thought to remember a larger distinction than colour/color, but that must have been an other word. \$\endgroup\$
    – Joop Eggen
    Sep 8, 2021 at 11:47
  • \$\begingroup\$ It originated from Groningen it seems, and I'm currently situated in Haarlem. There is even a shipyard named "Bodewes" in NL of one far away relative. It's not as uncommon a name as you might think. \$\endgroup\$ Sep 8, 2021 at 13:34
3
\$\begingroup\$

Styling specific:

  1. multiple assignments on a single line is only harder to read, it won't make your code faster;
  2. there is way too little whitespace:
    • after comma's;
    • surrounding assignments using =;
    • surrounding operators such as +;
    • after the int[][] array of arrays type;
    • before opening parentheses and after closing parentheses;
    • after else;
  3. MakeZeroes is not using the Java coding convention to start methods with a small cap letter.

Note that (2) can be obtained by simply using a formatter for you code, in case you don't want to explicitly type out every space. That way you get convenience and nicely formatted / readable code.


Programming specific:

  1. there is copy / paste code when assigning to zero and when adding up, this is a generic red flag;
  2. you are using indexing for the ArrayList while you go through the indices sequentially when you are setting values. For this you'd use an iterator, or more generally, a for-each construct.

Design specific:

  1. i and j (commonly used for loops) are used instead of e.g. x and y, commonly used for coordinates;
  2. addElements(i,j,matrix) is called in MakeZeroes which goes completely against the principle of least surprise;
  3. Main is of course not a good class name;
  4. (minor): I commonly use the table as initial parameter, but if it was a field, it may not have to be a parameter at all.

The design would have been much easier if you would have created a Position class. This would have allowed you to create functions to check if a position is valid (you might be astounded how many 0 and such literals are suddenly not required anymore). If you wanted to store the locations that needed to be zerod then you could then simply store the Position instead of another array.


I would also encourage you to create a Matrix or Table class of sorts. This would allow you to make sure that the field is a nice table - currently the array sizes within the array could well be different. Generally you use classes to encapsulate data and keep your program from reaching an invalid state.


Instead of keeping track of all zero values, you can also create a copy of the matrix and perform the operations immediately, using the data of the original matrix. This has, of course, the disadvantage that you require the memory for two matrices, but you only have to traverse the matrix once and can calculate and/or zero the values directly. Besides, a list of integer arrays is rather expensive as well.

This is however more of a alternative than a criticism, your current design is pretty decent.

Do note that you may get duplicate positions that are zero'd, so you could also use a Set of positions. But note that this requires you to have the right equals and hashCode functionality - easily created using a record for Position (Java 14 and onwards).


One more advanced trick is to use enums to get positions relative to the other position.

E.g. you could use

enum Neighbor {
    NORD, EAST, SOUTH, WEST;
}

or even parameterized

enum Neighbor {
    NORD(0, -1), EAST(1, 0), SOUTH(0, 1), WEST(-1, 0);

    private Neighbor(deltaX, deltaY) {
        ...
    }

    ...
}

That's all great, but that's a lot of work for a beginner. Hence, here's a template to play around with:


public static record Position(int x, int y) {
    Position getNeighbor(Neighbor neighbor) {
        return new Position(this.x + neighbor.getDeltaX(), this.y + neighbor.getDeltaY());
    }
}

public static record Dimensions(int width, int height) {}


public enum Neighbor {
    NORTH(0, -1), EAST(1, 0), SOUTH(0, 1), WEST(-1, 0);

    private int deltaX;
    private int deltaY;

    private Neighbor(int deltaX, int deltaY) {
        this.deltaX = deltaX;
        this.deltaY = deltaY;
        
    }
    
    public int getDeltaX() {
        return deltaX;
    }
    
    public int getDeltaY() {
        return deltaY;
    }
}

public static class Matrix implements Cloneable {
    private int[][] matrix;
    private Dimensions dimensions;
    
    public Matrix(int[][] initialMatrix) {
        this.dimensions = new Dimensions(initialMatrix[0].length, initialMatrix.length);
     
        // clones 2-dimensional array and checks row size
        this.matrix = initialMatrix.clone();
        for (int y = 0; y < dimensions.height(); y++) {
            int[] row = initialMatrix[y];
            if (row.length != dimensions.width()) {
                throw new IllegalArgumentException("Row " + y + " is not of the same width as the preceding rows");
            }
            this.matrix[y] = row.clone();
        }
    }
            
    public boolean isValid(Position pos) {
        return pos.x >= 0 && pos.x < dimensions.width() && pos.y >= 0 && pos.y < dimensions.height();
    }
    
    public void set(Position pos, int value) {
        assert isValid(pos);
        matrix[pos.y()][pos.x()] = value;
    }
    
    public int get(Position pos) {
        assert isValid(pos);
        return matrix[pos.y()][pos.x()];
    }
    
    public Matrix clone() {
        return new Matrix(matrix);
    }
    
    public Dimensions getDimensions() {
        return dimensions;
    }
}

This is all code you can write without even looking at the actual calculations required. Having a base set of classes and methods can really help you focus on the problem. You can copy/paste it into an alternate Main class. It is possible to use Neighbor.values() to iterate over all of the neighbors.

\$\endgroup\$
2
  • \$\begingroup\$ Really really minor points: public enum Neighbor suffices (implicitly static), and private final int deltaX; - might then use public without getters. record Position is a good idea / better abstraction. \$\endgroup\$
    – Joop Eggen
    Sep 8, 2021 at 11:43
  • \$\begingroup\$ You are of course right about enum being static by default, as the compiler will create separate class files for each enum instance. However, I don't see how I can use that fact to introduce a const value for each class instance from within the enum specification. If I'm not mistaken the above trick is straight from "Effective Java" by Joshua. In my case neighbor is relative to position, so Position is the main idea, and Neighbor enhances that as new Position(oldPos.x() - 1, oldPos.y()) is a bit too cryptic for my taste. \$\endgroup\$ Sep 8, 2021 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.