Similar to a one-dimensional array, a two-dimensional array also consists of a sequence of elements. But the elements can be laid out in a rectangular grid rather than a line.

Diagonal Traverse

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:

1
2
3
4
5
6
7
8
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]

Output: [1,2,4,7,5,3,6,8,9]

LeetCode Link


Solution

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
const findDiagonalOrder = function(matrix)
{
const result = [];

let RowSize = matrix.length;
if(RowSize === 0){
return result;
}

let ColumnSize = matrix[0].length;
if(ColumnSize === 0){
return result;
}

const resultSize = RowSize * ColumnSize;
if(resultSize === 0){
return result;
}

let row = 0;
let col = 0;

while(result.length < resultSize){
// Puts the number to the result list
result.push( matrix[row][col] );

// Moves up
if( (row + col) % 2 === 0 ){
// Checks column boundary, this has to be done before checking row boundary
if( col === (ColumnSize - 1) ){
row++;
}
// Checks row boundary
else if( row === 0 ){
col++;
}
// Not boundary
else{
row--;
col++;
}
}
// Moves down
else{
// Checks row boundary, this has to be done before checking column boundary
if( row === (RowSize - 1) ){
col++;
}
// Checks column boundary
else if(col === 0 ){
row++;
}
// Not boundary
else{
row++;
col--;
}
}
}
return result;
};


Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

1
2
3
4
5
6
7
8
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]

Output: [1,2,3,6,9,8,7,4,5]

Example 2:

1
2
3
4
5
6
7
8
Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]

Output: [1,2,3,4,8,12,11,10,9,5,6,7]

LeetCode Link


Solution

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
const spiralOrder = function(matrix) {
const result = [];

let RowSize = matrix.length;
if(RowSize === 0){
return result;
}

let ColumnSize = matrix[0].length;
if(ColumnSize === 0){
return result;
}

// Moving right first, movable length equals to column size
let horizontalMovableLength = ColumnSize;

// Moving down next, movable length equals to row size minus one
let verticalMovableLength = RowSize - 1;

// Initializes indexs
let row = 0;
let col = 0;

// Initializes flag
let increasementFlag = 1;

const resultLength = RowSize * ColumnSize;
while(result.length < resultLength)
{
moveHorizontally();

moveVertically();

// Changes the flag to change the moving direction
increasementFlag = increasementFlag * -1;
}

return result;

function moveHorizontally(){
if(horizontalMovableLength === 0){
return;
}

for(let i = 0; i < horizontalMovableLength; i++){
// Adds the number to result
result.push(matrix[row][col]);

// Increases the column to move horizontally
col += increasementFlag;
}

// Resets the for loop last move
col -= increasementFlag;

// Moves the row to avoid duplicate
row += increasementFlag;

// Consumes a horizontal length
horizontalMovableLength--;
}

function moveVertically(){
if(verticalMovableLength === 0){
return;
}

for(let i = 0; i < verticalMovableLength; i++){
// Adds the number to result
result.push(matrix[row][col]);

// Increases the row to move vertically
row += increasementFlag;
}

// Resets the for loop last move
row -= increasementFlag;

// Moves the column to avoid duplicate
col -= increasementFlag;

// Consumes a vertical length
verticalMovableLength--;
}
};


Pascal’s Triangle

Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

1
2
3
4
5
6
7
8
9
Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

LeetCode Link


Solution

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
const generate = function (numRows) {
// Initializes indexs and result
let row = 0;
let col = 0;
let result = [];

for (row = 0; row < numRows; row++) {
// Creates a new list for every row
let rowList = [];

for (col = 0; col <= row; col++) {
// Puts the specific number to the current row list
rowList.push(getTriangleNumber(row, col));
}

// Puts the current row list to result list
result.push(rowList);
}

return result;
};

function getFactorials(num) {
if (num < 0) {
return -1;
}
else if (num == 0) {
return 1;
}
else {
return ( num * getFactorials(num - 1) );
}
}

// https://medium.com/i-math/top-10-secrets-of-pascals-triangle-6012ba9c5e23 (Secret #7)
// https://www.mathsisfun.com/pascals-triangle.html
// Gets the specific number
function getTriangleNumber(row, col) {
return getFactorials(row) / (getFactorials(col) * getFactorials(row - col));
}