diff options
-rw-r--r-- | shortest_subarr_sum_k.c | 91 | ||||
-rw-r--r-- | shortest_subarr_sum_k.py | 34 |
2 files changed, 125 insertions, 0 deletions
diff --git a/shortest_subarr_sum_k.c b/shortest_subarr_sum_k.c new file mode 100644 index 0000000..66e4fdb --- /dev/null +++ b/shortest_subarr_sum_k.c @@ -0,0 +1,91 @@ +// 862 Shortest Subarray with Sum at Least K +#include "leetcode.h" + +/* + * given an integer array 'nums' and an integer 'k' return the length of the + * shortest non empty subarray of 'nums' with a sum of at least 'k'. if there is + * no such subarray, return -1. a subarray is a contiguous part of an array + */ + +struct element { + int idx; + long long prefix_sum; +}; + +struct deque { + struct element *data; + int front; + int rear; + int size; + int capacity; +}; + +struct deque *create_deque(int capacity) { + struct deque *dq = (struct deque *)malloc(sizeof(struct deque)); + dq->data = (struct element *)malloc(capacity * sizeof(struct element)); + dq->front = 0; + dq->rear = -1; + dq->size = 0; + dq->capacity = capacity; + return dq; +} + +bool is_empty(struct deque *dq) { return !dq->size; } + +void push_back(struct deque *dq, struct element e) { + dq->rear = (dq->rear + 1) % dq->capacity; + dq->data[dq->rear] = e; + dq->size++; +} + +struct element pop_front(struct deque *dq) { + struct element e = dq->data[dq->front]; + dq->front = (dq->front + 1) % dq->capacity; + dq->size--; + return e; +} + +struct element back(struct deque *dq) { return dq->data[dq->rear]; } + +struct element front(struct deque *dq) { return dq->data[dq->front]; } + +void pop_back(struct deque *dq) { + dq->rear = (dq->rear - 1 + dq->capacity) % dq->capacity; + dq->size--; +} + +void free_deque(struct deque *dq) { + free(dq->data); + free(dq); +} + +int shortestSubarray(int *nums, int numsSize, int k) { + long long *prefix_sum = + (long long *)malloc((numsSize + 1) * sizeof(long long)); + prefix_sum[0] = 0; + for (int i = 0; i < numsSize; i++) + prefix_sum[i + 1] = prefix_sum[i] + nums[i]; + struct deque *dq = create_deque(numsSize + 1); + int min_len = INT_MAX; + for (int i = 0; i <= numsSize; i++) { + while (!is_empty(dq) && prefix_sum[i] - front(dq).prefix_sum >= k) { + min_len = (i - front(dq).idx) < min_len ? (i - front(dq).idx) : min_len; + pop_front(dq); + } + while (!is_empty(dq) && prefix_sum[i] <= back(dq).prefix_sum) { + pop_back(dq); + } + struct element e = {i, prefix_sum[i]}; + push_back(dq, e); + } + free(prefix_sum); + free_deque(dq); + return min_len == INT_MAX ? -1 : min_len; +} + +int main() { + int n1[] = {1}, n2[] = {1, 2}, n3[] = {2, -1, 2}; + printf("%d\n", shortestSubarray(n1, ARRAY_SIZE(n1), 1)); // expect: 1 + printf("%d\n", shortestSubarray(n2, ARRAY_SIZE(n2), 4)); // expect: -1 + printf("%d\n", shortestSubarray(n3, ARRAY_SIZE(n3), 3)); // expect: 3 +} diff --git a/shortest_subarr_sum_k.py b/shortest_subarr_sum_k.py new file mode 100644 index 0000000..efe319d --- /dev/null +++ b/shortest_subarr_sum_k.py @@ -0,0 +1,34 @@ +# 862 Shortest Subarray with Sum at Least K +from collections import deque + +""" +given an integer array 'nums' and an integer 'k' return the length of the +shortest non empty subarray of 'nums' with a sum of at least 'k'. if there is +no such subarray, return -1. a subarray is a contiguous part of an array +""" + + +class Solution(object): + def shortestSubarray(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + dq = deque([[0, 0]]) + ans, curr = float("inf"), 0 + for i, j in enumerate(nums): + curr += j + while dq and curr - dq[0][1] >= k: + ans = min(ans, i + 1 - dq.popleft()[0]) + while dq and curr <= dq[-1][1]: + dq.pop() + dq.append([i + 1, curr]) + return ans if ans < float("inf") else -1 + + +if __name__ == "__main__": + obj = Solution() + print(obj.shortestSubarray(nums=[1], k=1)) + print(obj.shortestSubarray(nums=[1, 2], k=4)) + print(obj.shortestSubarray(nums=[2, -1, 2], k=3)) |