CodingQuestion/src/LeetCode-498-Diagonal-Traverse.java at master · drinkbeer/CodingQuestion · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
class Solution {
    // Traverse from two directions
    /*
    Time: O(M * N)
    Space: O(1)
    */
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[] res = new int[m * n];

        int idx = 0;
        int i = 0, j = 0;
        boolean up = true;
        while (true) {
            res[idx++] = mat[i][j];

            if (i == m - 1 && j == n - 1) break;

            int x = 0, y = 0;

            if (up) {
                x = -1;
                y = 1;
                if (j == n - 1) {
                    // move down to [i + 1, n - 1]
                    x = 1;
                    y = 0;

                    up = !up;
                } else if (i == 0) {
                    // move right to [0, j + 1]
                    x = 0;
                    y = 1;

                    up = !up;
                }
            } else {
                x = 1;
                y = -1;
                if (i == m - 1) {
                    // move right to [m - 1, j + 1]
                    x = 0;
                    y = 1;

                    up = !up;
                } else  if (j == 0) {
                   // move down to [i + 1, 0]
                    x = 1;
                    y = 0;

                    up = !up;
                }
            }

            i += x;
            j += y;
        }

        return res;
    }

    // Traverse from same direction
    /*
    Time: O(M*N)
    Space: O(min(M, N))
    */
//     public int[] findDiagonalOrder(int[][] mat) {

//         int m = mat.length, n = mat[0].length;

//         int[] res = new int[m * n];
//         int idx = 0;
//         boolean up = true;
//         for (int k = 0; k < m; k++) {
//             int i = k, j = 0;

//             idx = traverse(res, mat, i, j, idx, up);
//             up = !up;
//         }

//         for (int k = 1; k < n; k++) {
//             int i = m - 1, j = k;
//             idx = traverse(res, mat, i, j, idx, up);
//             up = !up;
//         }

//         return res;
//     }

//     private int traverse(int[] result, int[][] mat, int i, int j, int idx, boolean up) {
//         List<Integer> list = new ArrayList<>();
//         while (i < mat.length && i >= 0 && j < mat[0].length && j >= 0) {
//             list.add(mat[i--][j++]);
//         }

//         if (!up) {
//             Collections.reverse(list);
//         }

//         for (int num : list) {
//             result[idx++] = num;
//         }

//         return idx;
//     }
}