Shortest Subarray with Sum at Least K

A straightforward but inefficient approach involves pre-calculating prefix sums to quickly find the sum of any subarray. We then iterate through all possible start and end points of a subarray, check if its sum is at least k, and keep track of the minimum length found.

1. Create a prefix sum array prefix of size n + 1. Use long to prevent integer overflow, as sums can be large.
2. Populate the prefix array: prefix[i+1] = prefix[i] + nums[i] for i from 0 to n-1.
3. Initialize minLength = n + 1 to store the result.
4. Iterate with a start index i from 0 to n-1.
5. Inside this loop, iterate with an end index j from i to n-1.
6. Calculate the subarray sum: sum = prefix[j+1] - prefix[i].
7. If sum >= k, update minLength = Math.min(minLength, j - i + 1).
8. After the loops, if minLength is still n + 1, return -1. Otherwise, return minLength.

This method improves upon a naive brute-force solution by optimizing the sum calculation for each subarray.

1. Prefix Sum Calculation: First, we create a prefix sum array, prefix, of size n + 1, where n is the length of nums. prefix[i] stores the sum of elements from nums[0] to nums[i-1]. prefix[0] is initialized to 0. This allows us to calculate the sum of any subarray nums[i...j] in constant time using the formula prefix[j+1] - prefix[i]. This pre-computation step takes O(n) time.

2. Iterating Subarrays: After computing the prefix sums, we use two nested loops to examine every possible non-empty subarray. The outer loop selects a starting index i from 0 to n-1, and the inner loop selects an ending index j from i to n-1.

3. Checking Condition: For each subarray defined by (i, j), we calculate its sum prefix[j+1] - prefix[i]. If this sum is greater than or equal to k, we have found a valid subarray. We then update our minimum length found so far with min(minLength, j - i + 1).

4. Result: We initialize minLength to a value larger than n (e.g., n + 1). If minLength remains this value after checking all subarrays, it means no solution exists, and we return -1. Otherwise, we return the final minLength.

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        int minLength = n + 1;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                long sum = prefix[j + 1] - prefix[i];
                if (sum >= k) {
                    minLength = Math.min(minLength, j - i + 1);
                }
            }
        }

        return minLength == n + 1 ? -1 : minLength;
    }
}