Challenge: Shortest Subarray with Sum at Least K (Prefix Sums with a Monotonic Deque)

• This problem finds the shortest subarray with sum >= k in an array with possible negatives.
• The simple positive-only window fails because negatives break monotonicity.
• Prefix sums turn subarray sums into prefix differences: P[i] - P[j] >= k.
• A monotonic deque of indices keeps prefix values strictly increasing front to back.
• Front pop: qualified left endpoints are never needed again for shorter subarrays.
• Back pop: a higher earlier prefix is dominated by a lower later one as a left endpoint.
• Time is O(N) and space is O(N).

What is the Shortest Subarray with Sum at Least K problem?

Given an array of integers that may include negatives and a target k, find the length of the shortest contiguous non-empty subarray whose sum is at least k. Return -1 if none exists. This is LeetCode 862.

For example, given [2, -1, 2] and k = 3, the answer is 3 (the entire array sums to 3).

Why does the simple sliding window fail?

With positive-only arrays, shrinking from the left always decreases the sum, so the greedy window works. With negatives, shrinking can increase the sum (removing a negative element), which means you might miss a shorter qualifying subarray by shrinking too early or not enough.

How do prefix sums help?

Let P be the prefix-sum array where P[0] = 0 and P[i] = sum of first i elements. The sum of the subarray from index j to i-1 is P[i] - P[j]. We want the shortest span i - j such that P[i] - P[j] >= k.

How does the monotonic deque work?

package com.bank.service;

import java.util.ArrayDeque;
import java.util.Deque;

public class ShortestSubarrayAtLeastKService {

    /**
     * Finds the shortest transaction run reaching the liquidity target.
     * Handles negative flows using prefix sums + monotonic deque.
     * Used by the National Bank of India intraday-liquidity desk.
     */
    public static int shortestSubarray(int[] flows, int k) {
        int n = flows.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + flows[i];
        }

        Deque<Integer> deque = new ArrayDeque<>();
        int best = Integer.MAX_VALUE;

        for (int i = 0; i <= n; i++) {
            // Front pop: qualified left endpoints
            while (!deque.isEmpty()
                    && prefix[i] - prefix[deque.peekFirst()] >= k) {
                best = Math.min(best, i - deque.pollFirst());
            }
            // Back pop: dominated left endpoints
            while (!deque.isEmpty()
                    && prefix[deque.peekLast()] >= prefix[i]) {
                deque.pollLast();
            }
            deque.addLast(i);
        }
        return best == Integer.MAX_VALUE ? -1 : best;
    }

    public static void main(String[] args) {
        int[] flows = {20000, -10000, 30000, -5000, 15000};
        int target = 40000;
        int len = shortestSubarray(flows, target);
        System.out.println("Shortest run reaching Rs." + target + ": "
            + (len == -1 ? "impossible" : len + " transactions"));
    }
}

javac -d out com/bank/service/ShortestSubarrayAtLeastKService.java
java -cp out com.bank.service.ShortestSubarrayAtLeastKService

Shortest run reaching Rs.40000: 4 transactions

Why is the front pop valid?

When prefix[i] - prefix[front] >= k, the span from front to i qualifies. Any future i' > i would give a longer span with the same front, so this left endpoint can never produce a shorter answer. We record the length and pop it permanently.

Why is the back pop valid?

If prefix[back] >= prefix[i], then the back index is a worse left endpoint than i for any future right endpoint: it is earlier (giving a longer span) and has a higher or equal prefix (giving a smaller difference). So it is strictly dominated and can be removed.

Why is this O(N)?

Each index is pushed onto the deque exactly once and popped at most once (either from the front or the back). So the total deque operations are at most 2N, and the prefix-sum computation is N. Total time is O(N).

What are the edge cases?

Several edge cases require attention.

• No qualifying subarray: return -1 when even the total sum is less than k.
• Single element >= k: the answer is 1.
• All negatives: impossible to reach a positive k, return -1.
• k = 0: every non-empty subarray with non-negative sum qualifies; the answer is 1 if any non-negative element exists.

package com.bank.core;

public class ShortestSubarrayEdgeCases {
    public static void main(String[] args) {
        System.out.println(shortest(new int[]{1, 2, 3}, 100));   // -1
        System.out.println(shortest(new int[]{50000}, 50000));    // 1
        System.out.println(shortest(new int[]{-1, -2, -3}, 1));  // -1
    }

    static int shortest(int[] arr, int k) {
        int n = arr.length; long[] p = new long[n + 1];
        for (int i = 0; i < n; i++) p[i + 1] = p[i] + arr[i];
        java.util.Deque<Integer> dq = new java.util.ArrayDeque<>();
        int best = Integer.MAX_VALUE;
        for (int i = 0; i <= n; i++) {
            while (!dq.isEmpty() && p[i] - p[dq.peekFirst()] >= k) best = Math.min(best, i - dq.pollFirst());
            while (!dq.isEmpty() && p[dq.peekLast()] >= p[i]) dq.pollLast();
            dq.addLast(i);
        }
        return best == Integer.MAX_VALUE ? -1 : best;
    }
}

-1
1
-1

What is the time and space complexity?

Time is O(N): prefix computation is O(N) and each deque operation is amortized O(1). Space is O(N) for the prefix array and the deque.

How does this compare to the positive-only variant?

| Variant | Array type | Algorithm | Time | Space |
|---|---|---|---|---|
| Positive only | All positive | Sliding window | O(N) | O(1) |
| With negatives | Mixed signs | Prefix + deque | O(N) | O(N) |

Recognizing when the simple window fails and reaching for prefix sums plus a monotonic deque is the real signal of depth.

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• The dual pop is the core invariant: front pops handle qualification, back pops handle domination. Being able to articulate both is what proves understanding.
• Use long for prefix sums: monetary data can overflow int across many transactions.
• The positive-only window is a special case: when all elements are positive, the deque degenerates into a simple two-pointer because prefix sums are already monotonically increasing.
• Related problems: sliding window maximum/minimum also use monotonic deques but for different invariants.