Loop diagonally through two dimensional array

Question

I wrote the following code to walk half the diagonals of an array:

String[][] b = [a,b,c]
               [d,e,f]
               [g,h,i];  

public void LoopDiag()
   for (int i = b.length - 1; i > 0; i--) {
       String temp = "";
       for (int j = 0, x = i; x <= b.length - 1; j++, x++) {
          temp = temp+b[x][j];
       }
       System.out.println(temp)
   }


   for (int i = 0; i <= b.length - 1; i++) {
        String temp = "";
        for (int j = 0, y = i; y <= b.length - 1; j++, y++) {
        temp = temp+b[j][y];
        }
        System.out.println(temp);
   }
}

Right now it prints the diagonals i.e current output:

g dh aei bf c

How do I make it print the other half diagonals i.e required output:

a db gec hf i 

Answer 1

Initialize array only for test purpose:

    int dim = 5;
    char ch = 'A';
    String[][] array = new String[dim][];
    for( int i = 0 ; i < dim ; i++ ) {
        array[i] = new String[dim];
        for( int j = 0 ; j < dim ; j++, ch++ ) {
            array[i][j] = "" + ch;
        }
    }

Output our matrix:

    for( int i = 0 ; i < dim ; i++ ) {
        for( int j = 0 ; j < dim ; j++, ch++ ) {
            System.out.print( array[i][j] + " " );
        }
        System.out.println();
    }
    System.out.println( "============================" );

Solution

Element indexes from diagonals have one rule - their sum is constant on one diagonal:

VARIANT 1

Use two loops to extract all diagonals.

First loop extracts top half of diagonals:

    for( int k = 0 ; k < dim ; k++ ) {
        for( int j = 0 ; j <= k ; j++ ) {
            int i = k - j;
            System.out.print( array[i][j] + " " );
        }
        System.out.println();
    }

Second loop iterates on bottom half of diagonals:

    for( int k = dim - 2 ; k >= 0 ; k-- ) {
        for( int j = 0 ; j <= k ; j++ ) {
            int i = k - j;
            System.out.print( array[dim - j - 1][dim - i - 1] + " " );
        }
        System.out.println();
    }

VARIANT 2

Use one loop to extract all diagonals, but there are extra iterations and one additional check:

    for( int k = 0 ; k < dim * 2 ; k++ ) {
        for( int j = 0 ; j <= k ; j++ ) {
            int i = k - j;
            if( i < dim && j < dim ) {
                System.out.print( array[i][j] + " " );
            }
        }
        System.out.println();
    }

The output:

A B C D E 
F G H I J 
K L M N O 
P Q R S T 
U V W X Y 
============================
A 
F B 
K G C 
P L H D 
U Q M I E 
V R N J 
W S O 
X T 
Y 

Update

There are questions about rectangular matrix (height != width) in comments. Here is solution for rectangular matrix:

The rule remains the same: Sum of element indexes from the same diagonal is constant

The minimum sum of indexes is 0 (for first element in matrix with indexes [0;0])

The maximum sum of indexes is width + height - 2 (for last element in matrix with indexes [height-1; with-1])

Initialize rectangular matrix only for test purpose:

    int WIDTH = 7;
    int HEIGHT = 3;
    char ch = 'A';
    String[][] array = new String[HEIGHT][];
    for( int i = 0 ; i < HEIGHT ; i++ ) {
        array[i] = new String[WIDTH];
        for( int j = 0 ; j < WIDTH ; j++, ch++ ) {
            array[i][j] = "" + ch;
        }
    }

Print our rectangular matrix:

    for( int i = 0 ; i < HEIGHT ; i++ ) {
        for( int j = 0 ; j < WIDTH ; j++, ch++ ) {
            System.out.print( array[i][j] + " " );
        }
        System.out.println();
    }
    System.out.println( "============================" );

Solution

    for( int k = 0 ; k <= WIDTH + HEIGHT - 2; k++ ) {
        for( int j = 0 ; j <= k ; j++ ) {
            int i = k - j;
            if( i < HEIGHT && j < WIDTH ) {
                System.out.print( array[i][j] + " " );
            }
        }
        System.out.println();
    }

Output:

A B C D E F G 
H I J K L M N 
O P Q R S T U 
============================
A 
H B 
O I C 
P J D 
Q K E 
R L F 
S M G 
T N 
U 

Answer 2

Just help yourself, have a look at the indices you need to loop through:

#1 (0,0)               -> a
#2 (1,0)  (0,1)        -> bd
#3 (2,0)  (1,1)  (0,2) -> gec
#4 (2,1)  (1,2)        -> hf
#5 (2,2)               -> i

Look at the change of the indices in each iteration and create your algorithm. Not so difficult, so do your homework yourself ;)

Answer 3

I wrote the following code. The key is to exhaust all of the diagonals that start at the top and then move onto the diagonals that start on the sides. I included a method that combines the two angles to traverse diagonals Northwest - Southeast and Northeast - Southwest and stand alone methods for traversing the respective angles.

public static void main(String[] args){
    int[][] m = {{1,2,3},{4,5,6},{7,8,9},{10,11,12}};
    printDiagonals(m, DiagonalDirection.NEtoSW, new DiagonalVisitor() {     
        public void visit(int x, int y, int[][] m) {
            System.out.println(m[x][y]);
        }
    });
}

public enum DiagonalDirection{
    NWToSE,
    NEtoSW
}

private static abstract class DiagonalVisitor{
    public abstract void visit(int x, int y, int[][] m);
}

public static void printDiagonals(int[][] m, DiagonalDirection d, DiagonalVisitor visitor){

    int xStart = d==DiagonalDirection.NEtoSW ? 0 : m.length-1;
    int yStart = 1;


    while(true){
        int xLoop, yLoop;
        if(xStart>=0 && xStart<m.length){
            xLoop = xStart;
            yLoop = 0;
            xStart++;
        }else if(yStart<m[0].length){
            xLoop = d==DiagonalDirection.NEtoSW ? m.length-1 : 0;
            yLoop = yStart;
            yStart++;
        }else
            break;

        for(;(xLoop<m.length && xLoop>=0)&&yLoop<m[0].length; xLoop=d==DiagonalDirection.NEtoSW ? xLoop-1 : xLoop+1, yLoop++){
            visitor.visit(xLoop, yLoop, m);
        }

    }

}

public static void printDiagonalsNEtoSW(int[][] m, DiagonalVisitor visitor){

    int xStart = 0;
    int yStart = 1;


    while(true){
        int xLoop, yLoop;
        if(xStart<m.length){
            xLoop = xStart;
            yLoop = 0;
            xStart++;
        }else if(yStart<m[0].length){
            xLoop = m.length-1;
            yLoop = yStart;
            yStart++;
        }else
            break;

        for(;xLoop>=0 && yLoop<m[0].length; xLoop--, yLoop++){
            visitor.visit(xLoop, yLoop, m);
        }


    }
}

public static void printDiagonalsNWtoSE(int[][] m, DiagonalVisitor visitor){

    int xStart = m.length-1;
    int yStart = 1;


    while(true){
        int xLoop, yLoop;
        if(xStart>=0){
            xLoop = xStart;
            yLoop = 0;
            xStart--;
        }else if(yStart<m[0].length){
            xLoop = 0;
            yLoop = yStart;
            yStart++;
        }else
            break;

        for(;xLoop<m.length && yLoop<m[0].length; xLoop++, yLoop++){
            visitor.visit(xLoop, yLoop, m);
        }       
    }
}

Answer 4

Solutions would be much easier if we break it down into 2 sub-problems:

1. Figure out the start of each diagonal.

2. Given the starting indices of a diagonal, print the diagonal.

   public void printMatrixDiagonals(int[][] matrix) {
   
       int c = 0;
       int count = matrix.length + matrix[0].length -1;
       int i = 0, j = 0;
       //There can be at most  m + n -1 diagonals to be printed
       while (c < count) {
           //Start printing diagonals from i and j
           printDiagonal(i, j, matrix);
           if (i < matrix.length -1) {
               //We increment row index until we reach the max number of rows
               i++;
           } else if (j < matrix[0].length - 1) {
               //We are at maximum index of row; so its time to increment col index
               //We increment column index until we reach the max number of columns
               j++;
           }
           c++;
       }
   }
   

Print Diagonal: Notice that every time we start printing each diagonal, the index of row should be decremented and the index of column should be incremented. So given the starting indices of each diagonal, we can print the diagonal as follows:

private void printDiagonal(int i, int j, int[][] m) {
    while (i >=0 && j< m[0].length ) {
        System.out.print(m[i][j] + " ");
        i--;
        j++;
    }
    System.out.println("");
}

Answer 5

This works for non-square arrays. It's simple to understand, but calls min() and max() once per diagonal.

int ndiags = width +  height - 1;
System.out.println("---");
for (int diag = 0; diag < ndiags; diag++) {
    int row_stop = Math.max(0,  diag -  width + 1);
    int row_start = Math.min(diag, height - 1);
    for (int row = row_start; row >= row_stop; row--) {
        // on a given diagonal row + col = constant "diag"
        // diag labels the diagonal number
        int col = diag - row;
        System.out.println(col + "," + row);
        relax(col, row);
    }
    System.out.println("---");
}

Here's output for width=3, height=3

---
0,0
---
0,1
1,0
---
0,2
1,1
2,0
---
1,2
2,1
---
2,2
---

width=3, height=2

---
0,0
---
0,1
1,0
---
1,1
2,0
---
2,1
---

width = 2, height = 3

---
0,0
---
0,1
1,0
---
0,2
1,1
---
1,2
---

Answer 6

This is very intuitive way to print diagonal matrix in while loop .

generalize the problem as whole rather than two part and optimized in terms of space complexity .

package algorithm;

public class printDiagonaly
{
    public static void main(String[] args)
    {
        int[][] a = new int[][]{{1, 2, 3, 4, 5},
                {6, 7, 8, 9, 10},
                {11, 12, 13, 14, 15},
                {16, 17, 18, 19, 20}};

        int lr = 0;
        int lc = -1;
        int fr = -1;
        int fc = 0;
        int row = a.length - 1;
        int col = a[0].length - 1;

        while (lc < col || fc < col || fr < row || lr < row)
        {
            if (fr < row)
            {
                fr++;
            }
            else
            {
                fc++;
            }

            if (lc < col)
            {
                lc++;
            }
            else
            {
                lr++;
            }

            int tfr = fr;
            int tlr = lr;
            int tlc = lc;
            int tfc = fc;

            while (tfr >= tlr && tfc <= tlc)
            {

                System.out.print(a[tfr][tfc] + " ");
                tfr--;
                tfc++;
            }
            System.out.println("\n");
        }
    }
}