1

I need to write a program that loops through a 2d array of which the elements consist of either a 1 or 0 and checks if there are two 1's in a row or in a column and then prints true, if I find two 1's on same col or row I can stop there (I don't need to count the 1's).

So I planned on creating a counter for the 1's in the rows and a counter for the 1's in columns and if that counter goes above 1 then the loop breaks and prints. However the counters doesn't reset per row or column, so currently if it finds any two 1's regardless of their position it will print.

I tried adding a rowTotal = 0 & colTotal = 0 at the end of the for loop for each one but doing this then doesn't find any 1's at all.

Also, this is for my data structures & algorithm class so I need to provide a full algorithm, so I don't want to use any functions for this. Any tips on improving my code or a better way to solve this problem would be appreciated. I can do this in either Python or Java.

Many thanks

int[][] board = new int[4][4];



// number to look for
        int findNum = 1;
        // initial total 
        int total = 0;  
        // flag variable to end loop
        boolean found = false;       
        // loops only if found is not 
        for (int i = 0; i < board.length && !found; i++)
        {     
            // resets for each new iteration 
            total = 0;  
            // loops only if found is not 
            for(int j = 0; j < board[i].length && !found; j++)
            {              
                //check row
                if(board[i][j] == findNum) {
                    total++;
                }
                // check column
                if(board[j][i] == findNum) {
                    total++;
                }
                // if more total greater than 1 then end
                if(total > 1) {
                    found = true;
                }
            }

        }

1
  • Posted corrected code above. Because this was for DSA class I was not able to use any other functions and teacher wanted it within two loops. All I needed was to add if(board[j][i] == findNum) {total++;} Thanks for all the answers they helped me clean my code and find answer. It still took me hours to find this though.
    – KingHarry
    Nov 22, 2019 at 19:54

3 Answers 3

2

Inside inner loop change if condition to use colTotal instead of rowTotal

 if (colTotal > 1) {
   System.out.println("2 lying on col");
   break;
 } 

Remember this break will not break outer loop so you need a flag for eg.

 boolean found = false; // outside loops

when you print and break just assign true

 found = true; // before break inside inner loop, adjecent to print statement

Now use this flag to check as first statement inside outer loop

 if (found) {
    break;
 }

Or simply you can have it as condition in outer loop

 for (int i = 0; i < board.length && !found; i++)
1
  • Thanks for the insight, I completely forgot that my break would not break the outer loop. Also really helpfull how you put it all into one line - for (int i = 0; i < board.length && !found; i++)
    – KingHarry
    Nov 15, 2019 at 15:49
0

Create two sets: one for rows and another for columns.

Loop through the array.

Each time you find a cell with a set bit, check that cell's row and column in your sets. If it exists for either, you're done. If not, update the sets and move on.

0

I think you can iterate through the whole 2d array row wise and check if there are more than one 1's, now transpose the array and repeat the process to check column wise :

 public static void main(String[] args) {

    int[][] board = {   { 0, 0, 0, 0 }, 
                        { 0, 1, 0, 0 }, 
                        { 1, 0, 0, 1 }, 
                        { 0, 0, 1, 0 } };

    if (checkMoreThanOne(board)) {
        System.out.println("Found more than one 1's in rows.");
    }
    int[][] transpose = transpose(board);
    if (checkMoreThanOne(transpose)) {
        System.out.println("Found more than one 1's in columns.");
    }
}

private static boolean checkMoreThanOne(int[][] board) {
    for (int i = 0; i < board.length; i++) {
        int count = 0;
        for (int j = 0; j < board[i].length; j++) {
            if (board[i][j] == 1) {
                if (count > 0)
                    return true;
                else
                    count++;
            }
        }
    }
    return false;
}

private static int[][] transpose(int[][] array) {
    if (array == null || array.length == 0)
        return array;

    int width = array.length;
    int height = array[0].length;

    int[][] array_new = new int[height][width];

    for (int x = 0; x < width; x++) {
        for (int y = 0; y < height; y++) {
            array_new[y][x] = array[x][y];
        }
    }
    return array_new;
}
3
  • You can replace System.exit(0); with appropriate return statements etc. Nov 15, 2019 at 14:02
  • Amazing, thank you so much. However, this would only check if the very next element is a 1, whereas I only need to check if they are on same row. so if the first row is 1001 then I should print true. Is there anyway t change the line: if(j < board[i].length - 1 && board[i][j + 1] == 1) so it does it for the whole row & collumn? I was thinking changing "&&" to " | | " and adding J + 2 & a J + 3 etc ?
    – KingHarry
    Nov 15, 2019 at 15:50
  • Sorry the question was not clear to me earlier, I have modified the answer now. Nov 15, 2019 at 17:45

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.