Diagonal Traverse
Problem
Print all numbers of a matrix in a zigzag over its diagonals: start at the top-left, go up and to the right along the first diagonal, then down and to the left along the next diagonal, and so on, changing the direction after each diagonal. Print the numbers separated by spaces.
Constraints
- 1 <= r, c <= 100
Examples
Input
3 3 1 2 3 4 5 6 7 8 9
Output
1 2 4 7 5 3 6 8 9
Solutions
The order of the corner checks matters: when going up, the right column check comes before the top row check, because in the top-right corner we must move down, not right. Each cell is visited once, so the time is O(r * c).
/*
* Problem : Process a matrix.
* Input : r and c, then r rows of c integers.
* Output : All numbers in zigzag order.
* Approach: A matrix.
* Time : O(r * c)
* Space : O(r * c)
* Java : 8 or newer.
*/
import java.util.Scanner;
import java.util.Arrays;
import java.util.stream.Collectors;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static int[] solve(int[][] m) {
int rows = m.length;
int cols = m[0].length;
int[] result = new int[rows * cols];
int row = 0;
int col = 0;
boolean up = true;
for (int i = 0; i < result.length; i++) {
// Step 1: Take the number at the current cell.
result[i] = m[row][col];
if (up) {
// Step 2: Going up and right. At the top row or the right column we must turn.
if (col == cols - 1) {
row++;
up = false;
} else if (row == 0) {
col++;
up = false;
} else {
row--;
col++;
}
} else {
// Step 3: Going down and left. At the left column or the bottom row we must turn.
if (row == rows - 1) {
col++;
up = true;
} else if (col == 0) {
row++;
up = true;
} else {
row++;
col--;
}
}
}
return result;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int rows = scanner.nextInt();
int cols = scanner.nextInt();
int[][] m = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
m[i][j] = scanner.nextInt();
}
}
System.out.println(Arrays.stream(solve(m)).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
}
}
Hints (1)
- Which turn rule must come first, and why?