Loop diagonally through two dimensional array
Solution 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
Solution 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 ;)
Solution 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);
}
}
}