aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--shortest_subarr_sum_k.c91
-rw-r--r--shortest_subarr_sum_k.py34
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))