Added matrix solutions

Мето Трајковски · Мето Трајковски · commit be7979618ea6 · 2019-12-15T21:26:12.000+01:00
diff --git a/Other/search_2d_matrix.py b/Other/search_2d_matrix.py
@@ -0,0 +1,58 @@
+'''
+Search a 2D Matrix
+
+Write an efficient algorithm that searches for a value in an m x n matrix.
+This matrix has the following properties:
+- Integers in each row are sorted in ascending from left to right.
+- Integers in each column are sorted in ascending from top to bottom.
+
+Input: target = 21
+[
+  [1,   4,  7, 11, 15],
+  [2,   5,  8, 12, 19],
+  [3,   6,  9, 16, 22],
+  [10, 13, 14, 17, 24],
+  [18, 21, 23, 26, 30]
+]
+Output: True
+
+=========================================
+Start from bottom left corner and search in top right direction.
+    Time Complexity:    O(N + M)
+    Space Complexity:   O(1)
+'''
+
+
+############
+# Solution #
+############
+
+def search_2d_matrix(matrix, target):
+    n = len(matrix)
+    m = len(matrix[0])
+
+    j = 0
+    i = n - 1
+
+    while (i >= 0) and (j < m):
+        if matrix[i][j] > target:
+            i -= 1
+        elif matrix[i][j] < target:
+            j += 1
+        else:
+            return True
+
+    return False
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => True
+print(search_2d_matrix([[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]], 21))
+
+# Test 2
+# Correct result => False
+print(search_2d_matrix([[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]], 20))
diff --git a/Other/set_matrix_zeroes.py b/Other/set_matrix_zeroes.py
@@ -0,0 +1,83 @@
+'''
+Set Matrix Zeroes
+
+Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
+
+Input:
+[
+  [1,1,1],
+  [1,0,1],
+  [1,1,1]
+]
+Output:
+[
+  [1,0,1],
+  [0,0,0],
+  [1,0,1]
+]
+
+=========================================
+Use first column and first row for marking when 0 is found.
+    Time Complexity:    O(N*M)
+    Space Complexity:   O(1)
+'''
+
+
+############
+# Solution #
+############
+
+def set_matrix_zeroes(matrix):
+    n = len(matrix)
+    if n == 0:
+        return
+    m = len(matrix[0])
+
+    # check if 0 exist in first row
+    is_row = False
+    for j in range(m):
+        if matrix[0][j] == 0:
+            is_row = True
+    # check if 0 exist in first column
+    is_col = False
+    for i in range(n):
+        if matrix[i][0] == 0:
+            is_col = True
+
+    # find which columns and rows should be 0
+    for i in range(1, n):
+        for j in range(1, m):
+            if matrix[i][j] == 0:
+                matrix[i][0] = matrix[0][j] = 0
+
+    # set 0 if the row or column where this element is located is 0
+    for i in range(1, n):
+        for j in range(1, m):
+            if (matrix[i][0] == 0) or (matrix[0][j] == 0):
+                matrix[i][j] = 0
+
+    # fill the first row with 0 if needed
+    if is_row:
+        for j in range(m):
+            matrix[0][j] = 0
+    # fill the first column with 0 if needed
+    if is_col:
+        for i in range(n):
+            matrix[i][0] = 0
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
+mat = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
+set_matrix_zeroes(mat)
+print(mat)
+
+# Test 2
+# Correct result => [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
+mat = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
+set_matrix_zeroes(mat)
+print(mat)
diff --git a/Other/spiral_matrix.py b/Other/spiral_matrix.py
@@ -0,0 +1,75 @@
+'''
+Spiral Matrix
+
+Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
+
+Input:
+[
+ [ 1, 2, 3 ],
+ [ 4, 5, 6 ],
+ [ 7, 8, 9 ]
+]
+Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
+
+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]
+
+=========================================
+Simulate spiral moving, start from (0,0) and when a border is reached change the X or Y direction.
+    Time Complexity:    O(N*M)
+    Space Complexity:   O(N*M)
+'''
+
+
+############
+# Solution #
+############
+
+def spiral_matrix(matrix):
+    n = len(matrix)
+    if n == 0:
+        return []
+
+    m = len(matrix[0])
+    if m == 0:
+        return []
+
+    total = n * m
+    res = []
+
+    n -= 1
+    xDir, yDir = 1, 1
+    x, y = 0, -1
+
+    while len(res) < total:
+        for i in range(m):
+            y += yDir
+            res.append(matrix[x][y])
+        m -= 1 # decrease horizontal moving steps
+        yDir *= -1 # change the Y direction
+
+        for i in range(n):
+            x += xDir
+            res.append(matrix[x][y])
+        n -= 1 # decrease vertical moving steps
+        xDir *= -1 # change the Y direction
+
+    return res
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => [1, 2, 3, 6, 9, 8, 7, 4, 5]
+print(spiral_matrix([[ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]))
+
+# Test 2
+# Correct result => [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
+print(spiral_matrix([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]))
