Skip to content

Instantly share code, notes, and snippets.

@mohanmca

mohanmca/ShortestSubarrayWithSumAtLeastKFull.java

Forked from johnyleebrown/ShortestSubarrayWithSumAtLeastKFull.java
Created October 12, 2021 03:55
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save mohanmca/7735e729a1a243ef1629a36a9c93f701 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save mohanmca/7735e729a1a243ef1629a36a9c93f701 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @johnyleebrown johnyleebrown created this gist Feb 17, 2020.
    58 changes: 58 additions & 0 deletions ShortestSubarrayWithSumAtLeastKFull.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,58 @@
    class Solution
    {
    public int shortestSubarray(int[] A, int K)
    {
    IMQ q = new IMQ(K);
    q.push(new Item(0, -1));

    for (int i = 0; i < A.length; i++)
    {
    // rewriting array with prefix sums
    A[i] = i > 0 ? A[i] + A[i - 1] : A[0];

    q.push(new Item(A[i], i));
    }

    return q.min != Integer.MAX_VALUE ? q.min : -1;
    }

    // increasing monotonic queue
    private class IMQ
    {
    private Deque<Item> q = new ArrayDeque<>();
    private int min = Integer.MAX_VALUE;
    private int K;

    public IMQ(int K)
    {
    this.K = K;
    }

    private void push(Item newItem)
    {
    while (!q.isEmpty() && newItem.val < q.peekLast().val)
    {
    q.removeLast();
    }

    while (!q.isEmpty() && newItem.val - q.peekFirst().val >= K)
    {
    min = Math.min(min, newItem.ind - q.peekFirst().ind);
    q.removeFirst();
    }

    q.addLast(newItem);
    }
    }

    private class Item
    {
    int val, ind;

    Item(int val, int ind)
    {
    this.val = val;
    this.ind = ind;
    }
    }
    }