Array-1/problem30.py at 1cadb19f5f857c3ed1fda6a00a0cfcc25dbc5440 · super30admin/Array-1 · 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
from typing import List


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:

        #top bottom left and right defines the boundaries and after each spiral, these boundaries
        #changes

        m = len(matrix) #rows
        n = len(matrix[0]) #cols
        result = []

        top, left, right, bottom = 0, 0, n - 1, m - 1

        while top <= bottom and left <= right:

            for i in range(left, right+1):
                result.append(matrix[top][i])

            top += 1

            for i in range(top, bottom+1): #if top > bottom then this for loop won't run
                result.append(matrix[i][right])

            right -= 1

            if top <= bottom: #if base condition var gets mutated always check them again
                for i in range(right, left-1, -1):
                    result.append(matrix[bottom][i])

            bottom -= 1

            if left <= right:
                for i in range(bottom, top-1, -1):
                    result.append(matrix[i][left])
            left += 1


        return result

# Time Complexity: O(m*n)
# Space Complexity: O(1)

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:

        #top bottom left and right defines the boundaries and after each spiral, these boundaries
        #changes

        m = len(matrix) #rows
        n = len(matrix[0]) #cols
        result = []

        top, left, right, bottom = 0, 0, n - 1, m - 1

        def helper(matrix, top, left, right, bottom, result):

            if top > bottom or left > right: #That’s the key reason recursion depth is min(m, n). Stop when either dimensionality is
                #exhausted
                return

            for i in range(left, right+1):
                result.append(matrix[top][i])

            top += 1

            for i in range(top, bottom+1):
                result.append(matrix[i][right])
            right -= 1

            if top <= bottom:
                for i in range(right, left-1, -1):
                    result.append(matrix[bottom][i])

            bottom -= 1

            if left <= right:
                for i in range(bottom, top-1, -1):
                    result.append(matrix[i][left])

            left += 1

            helper(matrix, top, left, right, bottom,result)

        helper (matrix, top, left, right, bottom, result)

        return result

# Recursive solution:

# Time Complexity: O(m*n)
# Space Complexity:  recursive stack depends no. of spirals
# O(min(m, n))
# because each recursive call removes one spiral layer, and the number of layers is bounded by the smaller matrix dimension.
# After one recursive call, the matrix shrinks like this (m-2) rows*(n-2) cols. Each call reduces both dimensions.
#ceil(min(m, n) / 2) = 3, basically whichever exhausts first either row or col.