Leetcode discuss: 862. Shortest Subarray with Sum at Least K

March 11, 2022

Here is the link.

What I did is to add more detail about failed test case and then I could fully follow the idea how to use deque to find minimum length. 

C# | Design a deque | Review Array - Subarray | 2022 March

March 10, 2022
Introduction
I plan to spend two weeks to prepare for Meta phone screen. I had three onsite interview from Meta in the row from 2019 to 2021, and this time I have to take another phone screen again. I did a few hours research on Leetcode.com, and kept blogging those case study of FB, Google, MSFT interview, and then I found the book through one of sharings. I like to go through those patterns - book chapter: Part VII Problem-patterns, and review all those algorithms. Here is the link of the book. I am reviewing Array - subarray algorithms, here is the list written in the book chapter.

C# | LinkedList | Deque data structure
It is hard for me to review the algorithm using deque. I think that I can do my best, and make sure that deque will work perfectly with test case [3, -2, 5], target = 4.

Time complexity: O(N)

1. Using O(N) time to calculate prefix sum;
2. C# LinkedList - a deque
3. What to remove - remove those ones impossible to be smallest one from the end
4. What to remove - remove those ones impossible to be smallest one from the beginning.
5. Study the test case [3, -2, 5]
6. Read more carefully about discuss post, how deque solve the problem. Here is the link.

Follow up on March 11, 2022
I still think that I miss something important in my practice. I chose to continue to test the code and then figure out things to learn. I used Visual studio debugger and then I can work on the simple test case, and then undersand better about design, and learn from my own debugging experience.

Case study: [3, -2, 5], K = 4 | Deque
prefix sum: {0, 3, 1, 6], K = 4, minimum length is 1, start and end index = 3
How to find it?

1. put index = 0 onto deque, deque: 0
2. iterate index = 1, deque size is 2, deque: 0<->1;
3. iterate index = 2, compare prefix sum value 1 with last one in deque, prefix sum: 3
4. Continue on item 3, argue that index = 1 will not make shortest one, since value is bigger than value at index = 2; Remove 1 from deque at end side. deque: 0
5. Add index = 2 on deque, 0 <->2;
6. Fact: if deque has more than one number, then check current index with next to first, if the range's sum is not smaller than K = 4, than first one in deque cannot compete the second one in deque, so it can be removed. Remove 0 from deque. deque: 2
7. index = 2, comparing to first one in deque, O(1) time to get range sum = 5 > 4, record shortest value as 1

In summary, every index in the array will be pushed into deque once and at most it will be pushed out deque as well.

In order to get the minimum length, check from start side of deque, make sure that if deque size is bigger than one (we add extra one beside the length of the array), first one should be only one if range sum ended at current index is not less than K. This way the range is minimum.

Trial and errors | Remove first in deque
Remove the following statements in the code:

while (linkedList.Count > 1 && (current - prefix[linkedList.First.Next.Value] >= K))
                {
                    linkedList.RemoveFirst();
                }

I played with the following C# code, argue that Remove first is important, otherwise, it will find first one and it cannot find second one.

Failed test case:
[17,85,93,-45,-21]
K = 150
output: 3
Expected: 2

The subarray [17,85,93] fits into K = 150 target, but it is not minimum length, length is 3. The subarray [85, 93] with sum = 178 > 150, and the length is 2.

So it is important to maintain the deque, and if there are possible two consecutive ones to fit into target K, remove one with smaller index.

Trial and errors | Remove last in deque
Remove the following statements:

while (linkedList.Count > 1 && prefix[linkedList.Last.Value] >= current)
 {
    linkedList.RemoveLast();
 }

Failed test case:
[84,-37,32,40,95]
K = 167
output: 5
Expected: 3

I like to study the above test case carefully, so that I can understand step by step change of deque, for loop, and shortest variable.

Prefix array
[0, 84, 47, 79, 119, 214]
Second iteration, i = 2, deque: 0 <->1, remove last functionality will remove last one index =1 from deque, argue that current prefix sum is 47 < 84, so if there is a range later to fit in target not less requirement, i = 2 is better one and short one compared to i = 1. We like to remove i = 1 from deque, since for loop is not intelligent enough to handle multiple one. This makes deque's index's mapping prefix sum value non-descending order.

It is kind of interesting to see that this remove-last action makes minimum feature possible!

Since sum of the array is bigger than K = 167, so the whole array is the subarray with sum not smaller than 167, but it is not smallest one, last three elements in the array's sum is 167 >= 167, but for loop stops at last iteration i = 5.

Deque: [0, 2, 3, 4, 5] - double check?
Prefix sum values: [0, 47, 79, 119, 214]
I am not so sure.

I use visual studio debugger to go through the process again:

[0, 84, 47, 79, 119, 214]
So the prefix sum indexes are removed and I like to document in the following:
[0 (removeFirst, i =5), 84(RemoveLast, i = 2, keep non-decreasing order), 47(First one, >=157, after removing first one - 0, i = 5), 79, 119]
So, I guess that deque's index mapping prefixSum step by step:
deque: 0
deque: 0 <->1
deque: 0, remove last one, since 47 < 84, i = 1 cannot be minimum length
deque: 0 <->2
deque: 0 <-> 2<->3
deque: 0 <-> 2 <->3<-4>
Look at the prefix sum values in deque: 0 <->47 <->79 <->119
iterate index = 5,
so index = 2, subarray from index = 2 to index = 5 >= k = 167, 214 - 47 = 167
linkedList.RemoveFirst will remove index = 0, since it is a loop, only keep last one, which makes minimum length, index = 2
shortest variable has value 3, deque 2<->3<->4, for loop last iteration i = 5.

We also like to maintain the deque's index's mapping prefix sum value is in non-descending order.

I think that working on this simple test case is best way to understand the design.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _862_minimum_subarray_at_least_k
{
    class Program
    {
        static void Main(string[] args)
        {
            var minimumLength = ShortestSubarray(new int[]{3, -2, 5}, 4);
        }

        /// <summary>
        /// code review: 
        /// 1. Read the book chapter
        /// https://github.com/liyin2015/python-coding-interview
        /// Part VII Problem-patterns
        /// Page 551 algorithm 862
        /// 2. Read the discuss post
        /// https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/189039/Detailed-intuition-behind-Deque-solution
        /// 3. Work on test case and test C# code
        /// Time complexity: O(N)
        /// </summary>
        /// <param name="A"></param>
        /// <param name="K"></param>
        /// <returns></returns>
        public static int ShortestSubarray(int[] A, int K)
        {
            if (A == null || A.Length == 0)
                return -1;

            var length = A.Length;
            var prefix = new int[length + 1]; // change from length to length + 1 since failed [2, -1, 2]

            // using O(N) time to build a prefix sum of the array
            prefix[0] = 0;
            for (int i = 0; i < length; i++)
            {
                prefix[i + 1] = prefix[i] + A[i];
            }

            var shortest = length + 1;

            // store index of the array into deque
            var linkedList = new LinkedList<int>();

            // three operations of deque
            // remove_front - it is impossible for the start point
            // append_back - it is possible for new start point
            // remove_back - it is impossible for the start point

            // check current index and first one in dequeue - prefix difference vs K
            // test case: [2, -1, 2]
            for (int i = 0; i < prefix.Length; i++)
            {
                var current = prefix[i];

                // step 1: Remove from deque - end side 
                // argue that: what is inside deque? - possible ranges 
                while (linkedList.Count > 1 && prefix[linkedList.Last.Value] >= current)
                {
                    linkedList.RemoveLast();
                }
                
				// step 2: Add to deque
                linkedList.AddLast(i);

                // step 3: remove from the start of deque
                // 
                while (linkedList.Count > 1 && (current - prefix[linkedList.First.Next.Value] >= K))
                {
                    linkedList.RemoveFirst();
                }

                // step 4: Compare to shortest range 
                if (i > 0 && (current - prefix[linkedList.First.Value] >= K))
                {
                    shortest = Math.Min(shortest, i - linkedList.First.Value);
                }
            }

            return shortest == length + 1 ? -1 : shortest;
        }
    }
}