Introduction

In this blog post, we will explore how to solve the LeetCode problem "862" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. Example 1: Input: nums = [1], k = 1 Output: 1 Example 2: Input: nums = [1,2], k = 4 Output: -1 Example 3: Input: nums = [2,-1,2], k = 3 Output: 3 Constraints: 1 <= nums.length <= 105 -105 <= nums[i] <= 105 1 <= k <= 109

Explanation

Here's the breakdown of the solution:

• Prefix Sums: Calculate prefix sums to efficiently compute the sum of any subarray. prefix_sum[i] stores the sum of nums[0] to nums[i-1].
• Monotonic Queue (Deque): Use a deque to maintain a monotonically increasing queue of prefix sum indices. This helps in finding the shortest subarray efficiently. The deque stores indices such that the corresponding prefix sums are in ascending order.

• Sliding Window Logic: While iterating through the prefix sums, maintain the deque. Pop elements from the left if they contribute to a subarray sum >= k, and pop elements from the right if the current element is smaller than the last element in the queue (maintaining the monotonic property).

• Runtime Complexity: O(n), where n is the length of the input array.

• Storage Complexity: O(n), due to the prefix sum array and the deque.

Code

    from collections import deque

def shortestSubarray(nums, k):
    n = len(nums)
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + nums[i]

    min_len = float('inf')
    deque_indices = deque()

    for i in range(n + 1):
        while deque_indices and prefix_sum[i] - prefix_sum[deque_indices[0]] >= k:
            min_len = min(min_len, i - deque_indices.popleft())

        while deque_indices and prefix_sum[i] <= prefix_sum[deque_indices[-1]]:
            deque_indices.pop()

        deque_indices.append(i)

    return min_len if min_len != float('inf') else -1