Shortest Subarray with Sum at Least K

class Solution {
public:
    int minSubarrayLength(vector<int>& array, int threshold) {
        int len = array.size();
        vector<long long> cumulativeSum(len + 1, 0);
    
        // Generating prefix sums
        for (int idx = 1; idx <= len; idx++) {
            cumulativeSum[idx] = cumulativeSum[idx - 1] + array[idx - 1];
        }
    
        deque<int> indices;
        int minimalLength = INT_MAX;
    
        for (int i = 0; i <= len; i++) {
            // Remove elements from deque that enable threshold achievement
            while (!indices.empty() && cumulativeSum[i] - cumulativeSum[indices.front()] >= threshold) {
                minimalLength = min(minimalLength, i - indices.front());
                indices.pop_front();
            }
    
            // Maintain a deque that is increasing with respect to cumulative sum values
            while (!indices.empty() && cumulativeSum[i] <= cumulativeSum[indices.back()]) {
                indices.pop_back();
            }
    
            // Include current index in deque
            indices.push_back(i);
        }
    
        // If no valid subarray is found, return -1
        return minimalLength == INT_MAX ? -1 : minimalLength;
    }
};

The provided CPP code aims to solve the problem of finding the shortest subarray's length with a sum equal to or exceeding a specified threshold in a given array. The solution utilizes a combination of prefix sums and a double-ended queue (deque) to efficiently manage and update the cumulative sums during iteration.

• Prefix Sum Computation: The code first computes the cumulative sum of the elements in the array, storing these sums in a vector. This step is crucial as it allows the calculation of any subarray's sum in constant time.

• Double-ended Queue (Deque) Usage: The deque is used to store indices of the array in a manner that the cumulative sums at these indices are in increasing order. This strategy is key for efficiently evaluating which parts of the array contribute to the sum reaching or exceeding the threshold.

• Two Main Operations in the Loop:

  1. If the difference between the cumulative sum at the current index and the cumulative sum at the index at the front of the deque is at least the threshold, update the shortest length and remove the front index from the deque.
  2. Ensure that the deque remains oriented with increasing cumulative sums. If the current cumulative sum is less than the one at the back of the deque, remove the back index until the deque is correctly ordered again and then add the current index.

• Result Evaluation: At the end of iteration through the array, if no subarray meets or exceeds the threshold, the function returns -1. If at least one subarray meets the criteria, the function returns the length of the shortest such subarray.

Through clever use of data structures and careful control of the computational complexity, this code efficiently solves the problem without needing to check each possible subarray explicitly. This results in a more scalable solution, suitable for handling larger input sizes.

class Solution {
    
    public int findShortestSubarrayLength(int[] elements, int desiredSum) {
        int length = elements.length;
    
        // Prepares to calculate cumulative sums
        long[] cumulativeSums = new long[length + 1];
    
        // Generate all cumulative sums
        for (int idx = 1; idx <= length; idx++) {
            cumulativeSums[idx] = cumulativeSums[idx - 1] + elements[idx - 1];
        }
    
        Deque<Integer> indexDeque = new ArrayDeque<>();
    
        int minSubarrayLength = Integer.MAX_VALUE;
    
        // Traverse each cumulative sum
        for (int current = 0; current <= length; current++) {
            // Process potential indices where subarrays start
            while (
                !indexDeque.isEmpty() &&
                cumulativeSums[current] - cumulativeSums[indexDeque.peekFirst()] >=
                desiredSum
            ) {
                minSubarrayLength = Math.min(
                    minSubarrayLength,
                    current - indexDeque.pollFirst()
                );
            }
    
            // Remove larger sums to keep deque monotonic
            while (
                !indexDeque.isEmpty() &&
                cumulativeSums[current] <= cumulativeSums[indexDeque.peekLast()]
            ) {
                indexDeque.pollLast();
            }
    
            // Add current index as a possible start point
            indexDeque.offerLast(current);
        }
    
        // Check if a valid subarray was found
        return minSubarrayLength == Integer.MAX_VALUE
            ? -1
            : minSubarrayLength;
    }
}

In this solution summary, explore the implementation details for finding the shortest subarray with a sum at least K in a given array using Java. The approach employs a sliding window technique facilitated by a deque (double-ended queue) to efficiently track the potential minimum length subarrays that meet or exceed the target sum.

Here's an overview of how the Java solution operates:

• Initialize Data Structures: Begin by setting up an array to hold cumulative sums starting from the head of the array. This prepares you to quickly calculate any subarray sum. Additionally, initialize a deque to assist in tracking the indices of interest for potential subarrays.

• Calculate Cumulative Sums: Compute the cumulative sums for the array such that each entry at index i in the new cumulative sum array represents the sum of the elements from the start up to the element at index i - 1 in the original array.

• Process Each Element: Traverse through each cumulative sum. For each element in the cumulative sums:

  • While the deque is not empty and the difference between the current cumulative sum and the cumulative sum at the index represented by the front of the deque is greater than or equal to K, update the minimum length of the subarray.
  • Continuously remove elements from the back of the deque if the current cumulative sum is less than or equal to the cumulative sum at the index represented by the back of the deque. This step maintains the deque's property of storing indices in increasing order of their cumulative sums.
  • Append the current index to the deque as it might be the start of a possible shortest subarray meeting the required sum.

• Handle No Valid Subarray: After processing all elements, if the minimum subarray length remains unchanged from the initialized value (indicating that no valid subarray was found), return -1. Otherwise, return the length of the shortest subarray found.

This implementation offers an efficient way of solving the problem by leveraging the properties of cumulative sums and using a deque to maintain a running window of potential subarray starts. This ensures that the solution operates within optimal time complexity constraints, making it suitable for large arrays.

class Solution:
    def findMinSubarrayLen(self, array: List[int], needed_sum: int) -> int:
        array_length = len(array)
    
        sum_up_to = [0] * (array_length + 1)
    
        for idx in range(1, array_length + 1):
            sum_up_to[idx] = sum_up_to[idx - 1] + array[idx - 1]
    
        indices = deque()
        min_length = float("inf")
    
        for current in range(array_length + 1):
            while (indices and sum_up_to[current] - sum_up_to[indices[0]] >= needed_sum):
                min_length = min(min_length, current - indices.popleft())
    
            while (indices and sum_up_to[current] <= sum_up_to[indices[-1]]):
                indices.pop()
    
            indices.append(current)
    
        return min_length if min_length != float("inf") else -1

The provided Python solution addresses the problem of finding the length of the shortest contiguous subarray where the sum of its elements is at least a given value k. Utilize a sliding window combined with a deque to efficiently determine the minimum length that satisfies this condition. Below is a conceptual understanding to execute this solution effectively:

• First, calculate prefix sums for the array, which helps in obtaining the sum of any subarray in constant time.
• Use a deque to store indices of these prefix sums in an increasing order. This assists in quickly finding the minimum subarray length that meets or exceeds the needed sum.
• As you iterate through each prefix sum:
  • Remove indices from the front of the deque when the difference between current prefix sum and the prefix sum at the deque's front index is greater than or equal to the needed sum. Update the minimum length each time such a subarray is found.
  • Also, maintain the deque in such a way that prefix sums are in increasing order. This is crucial because a smaller prefix sum that comes later could potentially form a subarray that meets the required sum condition with a future element.

If no valid subarray is found, the function returns -1. Otherwise, it returns the length of the shortest such subarray. This solution efficiently handles various array scenarios by ensuring that each element is processed in a way that maintains or improves the current best solution for the shortest subarray length. Remember to ensure edge cases like empty arrays or sums that cannot be met by any subarrays are handled gracefully.