-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathcontinuous-subarray-sum.py
98 lines (89 loc) · 3.16 KB
/
continuous-subarray-sum.py
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
# 523. Continuous Subarray Sum
# 🟠 Medium
#
# https://leetcode.com/problems/continuous-subarray-sum/
#
# Tags: Array - Hash Table - Math - Prefix Sum
import timeit
from typing import List
# Compute the prefix sums then iterate over each combination of two
# indexes checking if the sum of values between them is a multiple of k.
#
# Time complexity: O(n^2) - We iterate over all the combinations of two
# indexes.
# Space complexity: O(n) - The prefix sum array has the same length as
# the input.
#
# This solution fails with Time Limit Exceeded.
class Naive:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
# Compute an array of prefix sums.
pre = [nums[0]] + ([0] * (len(nums) - 1))
for i in range(1, len(nums)):
pre[i] = nums[i] + pre[i - 1]
# Iterate over all pairs of two indexes.
for i in range(len(nums) - 1):
for j in range(i + 1, len(nums)):
range_sum = pre[j]
if i > 0:
range_sum -= pre[i - 1]
if range_sum % k == 0:
return True
return False
# Iterate over the input computing the cumulative sum up to the current
# index, calculate sum[0:i] % k and store the result in a hashmap, if we
# ever find a repeated value, the sum of values between the indexes that
# resulted in the same remainder will be a multiple of k.
#
# Time complexity: O(n) - We iterate over the array once.
# Space complexity: O(k) - The hashmap holds the result of mod K
# operations so it can grow at most to size k.
#
# Runtime: 1563 ms, faster than 71.44%
# Memory Usage: 33.3 MB, less than 39.30%
class UseHashMap:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
# Use a hashmap. Initialize it with a zero to represent the sum
# of values at the index left of 0.
seen = {0: 0}
current_sum = 0
for i in range(len(nums)):
current_sum += nums[i]
rem = current_sum % k
if rem % k not in seen:
seen[rem] = i + 1
# If we have seen this sum in a previous index.
elif seen[rem] < i:
return True
return False
def test():
executors = [
Naive,
UseHashMap,
]
tests = [
[[0], 1, False],
[[10], 10, False],
[[5, 10, 35], 10, True],
[[23, 2, 4, 6, 7], 6, True],
[[23, 2, 4, 6, 6], 7, True],
[[23, 2, 6, 4, 7], 6, True],
[[23, 2, 6, 4, 7], 13, False],
]
for executor in executors:
start = timeit.default_timer()
for _ in range(1):
for col, t in enumerate(tests):
sol = executor()
result = sol.checkSubarraySum(t[0], t[1])
exp = t[2]
assert result == exp, (
f"\033[93m» {result} <> {exp}\033[91m for"
+ f" test {col} using \033[1m{executor.__name__}"
)
stop = timeit.default_timer()
used = str(round(stop - start, 5))
cols = "{0:20}{1:10}{2:10}"
res = cols.format(executor.__name__, used, "seconds")
print(f"\033[92m» {res}\033[0m")
test()