Traverse 2D array (matrix) diagonally

Question

So, I found this thread, which was extremely useful when traversing an array diagonally. I was stuck, although I reflected it. For example:

var m = 3; var n = 4; var a = new Array(); var b = 0; for(var i = 0; i < m; i++) { a[i] = new Array(n); for(var j = 0; j < n; j++) { a[i][j] = b; b++; } } for (var i = 0; i < m + n - 1; i++) { var z1 = (i < n) ? 0 : i - n + 1; var z2 = (i < m) ? 0 : i - m + 1; for (var j = i - z2; j >= z1; j--) { console.log(a[j][i - j]); } } 

The console reads [[0],[4,1],[8,5,2],[9,6,3],[10,7],[11]]

I would like to read [[8],[4,9],[0,5,10],[1,6,11],[2,7],[3]]

For a while he was at a standstill, he was like a rubik cube> _ <

Answer 1

Well, I found the logic z1, z2 a bit unreadable, so I did it a little differently:

 var m = 3; var n = 4; var a = new Array(); var b = 0; for(var i = 0; i < m; i++) { a[i] = new Array(n); for(var j = 0; j < n; j++) { a[i][j] = b; b++; } } var out = new Array(); for (var i = 1 - m; i < n; i++) { var group = new Array(); for (var j = 0; j < m; j++) { if ((i + j) >= 0 && (i + j) < n) { group.push(a[j][i + j]); } } out.push(group); } console.log(out); 

Prints [[8], [4, 9], [0, 5, 10], [1, 6, 11], [2, 7], [3]] on the console.

How it works

Your matrix construction gives you a rectangle like this (where your array a is a collection of rows):

  0 1 2 3
  4 5 6 7
  8 9 10 11

This means that the diagonals above this grid:

  # # 0 1 2 3
     # 4 5 6 7 #
        8 9 10 11 # #

Now we just iterate over the skewed rectangle, which will look like this:

  # # 0 1 2 3
  # 4 5 6 7 #
  8 9 10 11 # #

Now you will notice that for each row you add, you will get an additional column (starting with # ) and that the first column is now skewed by this sum (if you assume that you hold the first row in place and the sliding rows are at the bottom left). Thus, for our outer for loop (column by column), the first column is actually the old first column, 0 , minus the number of rows m , plus 1 , which gives 0 - m + 1 or 1 - m . The last column effectively remains in place, so we are still moving to n . Then this is just a question about each column and a traversal of each of the rows m (inner for loop).

Of course, this leaves you with a bunch of undefined ( # in the grid above), but we can skip them with a simple if to make sure that our i and j are within m and n .

It is probably a little less efficient than the z1 / z1 version, since we are now sorting through the redundant # cells and not pre-calculating them, but this should not make any real difference in the world, and I think the code is becoming much more readable.

Answer 2

 /* Initialize the 2-D array. */ String array2D[] = { "mvjlixape", "jhbxeenpp", "hktthbswy", "rwainuyzh", "ppfxrdzkq", "tpnlqoyjy", "anhapfgbg", "hxmshwyly", "ujfjhrsoa" }; // Print 2D array diagonally for left top to right down for(int j = 0; j < array2D.length; j ++){ for(int i = 0; i < array2D.length; i++){ if(i+j >= array2D.length) break; System.out.print(array2D[i].charAt(i+j)); } System.out.println(); } for(int j = 1; j < array2D.length; j ++){ for(int i = 0; i < array2D.length; i++){ if(i+j >= array2D.length) break; System.out.print(array2D[i + j].charAt(i)); } System.out.println(); } // Print diagonally right top to left bottom diagonal for(int j = 0; j < array2D.length; j++){ for(int i = j; i >= 0; i--){ System.out.print(array2D[j - i].charAt(i)); } System.out.println(); } for(int j = 1; j < array2D.length; j ++){ for(int i = j; i < array2D.length; i++){ System.out.print(array2D[array2D.length - i + j - 1].charAt(i)); } System.out.println(); }