diff options
-rw-r--r-- | find_two_non_overlap_subarr.c | 115 | ||||
-rw-r--r-- | find_two_non_overlap_subarr.py | 39 |
2 files changed, 154 insertions, 0 deletions
diff --git a/find_two_non_overlap_subarr.c b/find_two_non_overlap_subarr.c new file mode 100644 index 0000000..679d9a0 --- /dev/null +++ b/find_two_non_overlap_subarr.c @@ -0,0 +1,115 @@ +// 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum +#include "leetcode.h" + +/* + * you are given an array of integers 'arr' and an integer 'target'. you have to + * find two non overlapping subarrays of 'arr' each with a sum equal to + * 'target'. there can be multiple answers so you have to finmd an answer where + * the sum of the lengths of the two subarrays is minimum. return the minimum + * sum of the lengths of the two required subarrays or return -1 if you cannot + * find such two subarrays. + */ + +const int INT_NONE = 0x0BADC0DE; + +struct window { + int *ptr; + size_t len; + int target; + size_t ptr_frnt; + size_t ptr_back; + int window_sum; + int *res_ptr; + size_t res_size; +}; + +struct window create_window(int *ptr, size_t len, int target) { + size_t ptr_frnt = 0, ptr_back = 0, res_size = len + 1; + int window_sum = 0, *res_ptr = (int *)calloc(res_size, sizeof(int)); + for (size_t i = 0; i < res_size; i++) + res_ptr[i] = INT_NONE; + struct window res = { + .ptr = ptr, + .len = len, + .target = target, + .ptr_frnt = ptr_frnt, + .ptr_back = ptr_back, + .window_sum = window_sum, + .res_ptr = res_ptr, + .res_size = res_size, + }; + return res; +} + +bool next_window(struct window *self) { + if (self->ptr_frnt >= self->len) + return false; + if (self->window_sum > self->target) { + int token_frnt = self->ptr[self->ptr_frnt]; + self->ptr_frnt += 1; + self->window_sum -= token_frnt; + return true; + } + if (self->ptr_back >= self->len) + return false; + int token_back = self->ptr[self->ptr_back]; + self->ptr_back += 1; + self->window_sum += token_back; + return true; +} + +void log_window(struct window *self) { + if (self->window_sum != self->target) + return; + self->res_ptr[self->ptr_back] = self->ptr_back - self->ptr_frnt; +} + +void to_pref_min_vec(int *ptr, size_t len) { + int pref_min = INT_NONE; + for (size_t i = 0; i < len; i++) { + if (ptr[i] < pref_min) + pref_min = ptr[i]; + ptr[i] = pref_min; + } +} + +void to_rev_vec(int *ptr, size_t len) { + for (size_t i = 0; i < len / 2; i++) { + int t0 = ptr[i]; + ptr[i] = ptr[len - i - 1]; + ptr[len - i - 1] = t0; + } +} + +int minSumOfLengths(int *vec_ptr, int vec_len, int target) { + struct window window_0 = create_window(vec_ptr, vec_len, target); + while (next_window(&window_0)) + log_window(&window_0); + int *res_0_ptr = window_0.res_ptr; + size_t res_0_len = window_0.res_size; + to_pref_min_vec(res_0_ptr, res_0_len); + to_rev_vec(vec_ptr, vec_len); + struct window window_1 = create_window(vec_ptr, vec_len, target); + while (next_window(&window_1)) + log_window(&window_1); + int *res_1_ptr = window_1.res_ptr; + size_t res_1_len = window_1.res_size; + to_pref_min_vec(res_1_ptr, res_1_len); + to_rev_vec(res_1_ptr, res_1_len); + int ans = INT_NONE; + for (size_t bound = 0; bound < res_0_len; bound++) { + int tmp = res_0_ptr[bound] + res_1_ptr[bound]; + if (tmp < ans) + ans = tmp; + } + if (ans == INT_NONE) + return -1; + return ans; +} + +int main() { + int a1[] = {3, 2, 2, 4, 3}, a2[] = {7, 3, 4, 7}, a3[] = {4, 3, 2, 6, 2, 3, 4}; + printf("%d\n", minSumOfLengths(a1, ARRAY_SIZE(a1), 3)); // expect: 2 + printf("%d\n", minSumOfLengths(a2, ARRAY_SIZE(a2), 7)); // expect: 2 + printf("%d\n", minSumOfLengths(a3, ARRAY_SIZE(a3), 6)); // expect: -1 +} diff --git a/find_two_non_overlap_subarr.py b/find_two_non_overlap_subarr.py new file mode 100644 index 0000000..96508a8 --- /dev/null +++ b/find_two_non_overlap_subarr.py @@ -0,0 +1,39 @@ +# 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum +from itertools import accumulate + +""" +you are given an array of integers 'arr' and an integer 'target'. you have to +find two non overlapping subarrays of 'arr' each with a sum equal to +'target'. there can be multiple answers so you have to finmd an answer where +the sum of the lengths of the two subarrays is minimum. return the minimum +sum of the lengths of the two required subarrays or return -1 if you cannot +find such two subarrays. +""" + + +class Solution(object): + def minSumOfLengths(self, arr, target): + """ + :type arr: List[int] + :type target: int + :rtype: int + """ + prefix = {0: -1} + curr_bestl = [float("inf")] * len(arr) + ans, best = float("inf"), float("inf") + for i, curr in enumerate(accumulate(arr)): + if curr - target in prefix: + end = prefix[curr - target] + if end > -1: + ans = min(ans, i - end + curr_bestl[end]) + best = min(best, i - end) + curr_bestl[i] = best + prefix[curr] = i + return -1 if ans == float("inf") else ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.minSumOfLengths(arr=[3, 2, 2, 4, 3], target=3)) + print(obj.minSumOfLengths(arr=[7, 3, 4, 7], target=7)) + print(obj.minSumOfLengths(arr=[4, 3, 2, 6, 2, 3, 4], target=6)) |