aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--diagonal_traverse.c57
-rw-r--r--diagonal_traverse.py43
2 files changed, 100 insertions, 0 deletions
diff --git a/diagonal_traverse.c b/diagonal_traverse.c
new file mode 100644
index 0000000..802271d
--- /dev/null
+++ b/diagonal_traverse.c
@@ -0,0 +1,57 @@
+// 498. Diagonal Traverse
+#include "leetcode.h"
+
+/*
+ * given an 'm x n' matrix 'mat', return an array of all the elements of the
+ * array in a diagonal order.
+ */
+
+int *findDiagonalOrder(int **mat, int matSize, int *matColSize,
+ int *returnSize) {
+ int n = matSize * matColSize[0], row = 0, col = 0;
+ int *ans = (int *)malloc(n * sizeof(int));
+ *returnSize = n;
+ for (int i = 0; i < n; i++) {
+ ans[i] = mat[row][col];
+ if (!((row + col) % 2)) {
+ if (col == matSize - 1)
+ row++;
+ else if (!row)
+ col++;
+ else {
+ row--;
+ col++;
+ }
+ } else {
+ if (row == matColSize[0] - 1)
+ col++;
+ else if (!col)
+ row++;
+ else {
+ row++;
+ col--;
+ }
+ }
+ }
+ return ans;
+}
+
+int main() {
+ int m1i[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}},
+ m2i[2][2] = {{1, 2}, {3, 4}};
+ struct two_d_arr m1, m2;
+ two_d_arr_init(&m1, ARRAY_SIZE(m1i), ARRAY_SIZE(m1i[0]), m1i);
+ two_d_arr_init(&m2, ARRAY_SIZE(m2i), ARRAY_SIZE(m2i[0]), m2i);
+ int rs1, *fdo1 = findDiagonalOrder(m1.arr, m1.row_size, m1.col_size, &rs1);
+ int rs2, *fdo2 = findDiagonalOrder(m2.arr, m2.row_size, m2.col_size, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", fdo1[i]); // expect: 1 2 4 7 5 3 6 8 9
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", fdo2[i]); // expect: 1 2 3 4
+ printf("\n");
+ free(fdo1);
+ free(fdo2);
+ two_d_arr_free(&m1);
+ two_d_arr_free(&m2);
+}
diff --git a/diagonal_traverse.py b/diagonal_traverse.py
new file mode 100644
index 0000000..d75deec
--- /dev/null
+++ b/diagonal_traverse.py
@@ -0,0 +1,43 @@
+# 498. Diagonal Traverse
+
+"""
+given an 'm x n' matrix 'mat', return an array of all the elements of the
+array in a diagonal order.
+"""
+
+
+class Solution(object):
+ def findDiagonalOrder(self, mat):
+ """
+ :type mat: List[List[int]]
+ :rtype: List[int]
+ """
+ if not mat or not mat[0]:
+ return []
+ m, n = len(mat), len(mat[0])
+ ans, row, col = [], 0, 0
+ for _ in range(m * n):
+ ans.append(mat[row][col])
+ if (row + col) % 2 == 0:
+ if col == n - 1:
+ row += 1
+ elif row == 0:
+ col += 1
+ else:
+ row -= 1
+ col += 1
+ else:
+ if row == m - 1:
+ col += 1
+ elif col == 0:
+ row += 1
+ else:
+ row += 1
+ col -= 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findDiagonalOrder(mat=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]))
+ print(obj.findDiagonalOrder(mat=[[1, 2], [3, 4]]))