8000 Add sum of sub squares of a given nxn matrix (#631) · LeetCode-Interview/algorithms@ebc8de4 · GitHub
[go: up one dir, main page]

Skip to content

Commit ebc8de4

Browse files
author
siderism
authored
Add sum of sub squares of a given nxn matrix (keon#631)
* Added function to calculate sum of all sub-squares in a square matrix * Added test for sum_sub_squares function * Updated README
1 parent 38173ae commit ebc8de4

File tree

3 files changed

+42
-1
lines changed

3 files changed

+42
-1
lines changed

README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -236,6 +236,7 @@ If you want to uninstall algorithms, it is as simple as:
236236
- [spiral_traversal](algorithms/matrix/spiral_traversal.py)
237237
- [crout_matrix_decomposition](algorithms/matrix/crout_matrix_decomposition.py)
238238
- [cholesky_matrix_decomposition](algorithms/matrix/cholesky_matrix_decomposition.py)
239+
- [sum_sub_squares](algorithms/matrix/sum_sub_squares.py)
239240
- [queues](algorithms/queues)
240241
- [max_sliding_window](algorithms/queues/max_sliding_window.py)
241242
- [moving_average](algorithms/queues/moving_average.py)

algorithms/matrix/sum_sub_squares.py

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
# Function to find sum of all
2+
# sub-squares of size k x k in a given
3+
# square matrix of size n x n
4+
def sum_sub_squares(matrix, k):
5+
n = len(matrix)
6+
result = [[0 for i in range(k)] for j in range(k)]
7+
8+
if k > n:
9+
return
10+
for i in range(n - k + 1):
11+
l = 0
12+
for j in range(n - k + 1):
13+
sum = 0
14+
15+
# Calculate and print sum of current sub-square
16+
for p in range(i, k + i):
17+
for q in range(j, k + j):
18+
sum += matrix[p][q]
19+
20+
result[i][l] = sum
21+
l += 1
22+
23+
return result
24+

tests/test_matrix.py

Lines changed: 17 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,8 @@
77
rotate_image,
88
sparse_dot_vector,
99
spiral_traversal,
10-
sudoku_validator
10+
sudoku_validator,
11+
sum_sub_squares
1112
)
1213
import unittest
1314

@@ -272,6 +273,21 @@ def test_sudoku_validator(self):
272273
[3, 0, 0, 4, 8, 1, 1, 7, 9]
273274
]))
274275

276+
class TestSumSubSquares(unittest.TestCase):
277+
"""[summary]
278+
Test for the file sum_sub_squares.py
279+
280+
Arguments:
281+
unittest {[type]} -- [description]
282+
"""
283+
def test_sum_sub_squares(self):
284+
mat = [[1, 1, 1, 1, 1],
285+
[2, 2, 2, 2, 2],
286+
[3, 3, 3, 3, 3],
287+
[4, 4, 4, 4, 4],
288+
[5, 5, 5, 5, 5]]
289+
self.assertEqual(sum_sub_squares.sum_sub_squares(mat, 3),
290+
[[18, 18, 18], [27, 27, 27], [36, 36, 36]])
275291

276292
if __name__ == "__main__":
277293
unittest.main()

0 commit comments

Comments
 (0)
0