-
Notifications
You must be signed in to change notification settings - Fork 1
/
SpiralMatrix.java
98 lines (76 loc) · 2.33 KB
/
SpiralMatrix.java
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
package com.leetcode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class SpiralMatrix {
//https://leetcode.com/problems/spiral-matrix/
class Solution {
// Thing to remember is
// && cMin <= cMax and && rMin <= rMax as additional condution
// No additional memory
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> list = new LinkedList<>();
int n = matrix.length;
int m = matrix[0].length;
int rMin = 0;
int cMin = 0;
int rMax = n-1;
int cMax = m-1;
while(rMin <= rMax && cMin <= cMax){
//traverse right
for(int c = cMin ; c <= cMax && rMin <= rMax ; c++){
list.add(matrix[rMin][c]);
}
rMin++;
//traverse down
for(int r = rMin ; r <= rMax && cMin <= cMax ; r++){
list.add(matrix[r][cMax]);
}
cMax--;
//traverse left
for(int c = cMax; c>=cMin && rMin <= rMax ; c--){
list.add(matrix[rMax][c]);
}
rMax--;
//traverse up
for(int r = rMax ; r >= rMin && cMin <= cMax; r--){
list.add(matrix[r][cMin]);
}
cMin++;
}
return list;
}
}
}
//Alternate // With additional memory
/*
public List<Integer> spiralOrder(int[][] matrix) {
int[] dr = {0, 1, 0, -1};
int[] dc = {1, 0, -1, 0};
List<Integer> result = new ArrayList<>();
if(matrix == null || matrix.length == 0 )
return result;
int R = matrix.length; int C = matrix[0].length;
int size = R*C;
int ri = 0;
int ci = 0;
int di = 0;
boolean [][] seen = new boolean[R][C];
for(int i = 0 ; i < size ; i++){
seen[ri][ci] = true;
result.add(matrix[ri][ci]);
int r = ri + dr[di];
int c = ci + dc[di];
if(r < R && r >= 0 && c >=0 && c < C && !seen[r][c]){
ri = r;
ci = c;
}else{
//change direction
di = (di +1) % 4;
ri = ri + dr[di];
ci = ci + dc[di];
}
}
return result;
}
*/