diff options
author | jack <[email protected]> | 2024-06-15 18:41:41 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-15 18:41:41 -0600 |
commit | 6a9ee45101a4a2d17d48b5b8167fca200eb4aa6a (patch) | |
tree | 8156afe68442510cb7de03e7a07a2b6f68aaee69 /patching_array.py | |
parent | bfa816e4d0bcdb3996fb4d0de074dbf71155373d (diff) | |
download | leetcode-6a9ee45101a4a2d17d48b5b8167fca200eb4aa6a.tar.gz leetcode-6a9ee45101a4a2d17d48b5b8167fca200eb4aa6a.zip |
330. patching array
Diffstat (limited to 'patching_array.py')
-rw-r--r-- | patching_array.py | 43 |
1 files changed, 43 insertions, 0 deletions
diff --git a/patching_array.py b/patching_array.py new file mode 100644 index 0000000..de7d5a2 --- /dev/null +++ b/patching_array.py @@ -0,0 +1,43 @@ +# 330. Patching Array + +""" +given a sorted integer array 'nums' and an integer 'n', add/patch elements to +the array such that any number in the range '[1, n]' inclusive can be formed +by the sum of some elements in the array. return the minimum number of +patches required. +""" + + +class Solution(object): + def merge(self, intervals): + intervals.sort(key=lambda x: x[0]) + merged = [] + for i in intervals: + if not merged or merged[-1][1] < i[0] - 1: + merged.append(i) + else: + merged[-1][1] = max(merged[-1][1], i[1]) + return merged + + def minPatches(self, nums, n): + """ + :type nums: List[int] + :type n: int + :rtype: int + """ + ints, patches = [[0, 0]], 0 + for i in nums: + ints = self.merge(ints + [[j + i, k + i] for j, k in ints]) + while ints[0][1] < n: + ints = self.merge( + ints + [[i + ints[0][1] + 1, j + ints[0][1] + 1] for i, j in ints] + ) + patches += 1 + return patches + + +if __name__ == "__main__": + obj = Solution() + print(obj.minPatches(nums=[1, 3], n=6)) + print(obj.minPatches(nums=[1, 5, 10], n=20)) + print(obj.minPatches(nums=[1, 2, 2], n=5)) |