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

 March 10, 2022

Here is the link. 

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 - PK, remove those ones impossible to be smallest one from the end
4. What to remove - PK, 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.

Case study: [3, -2, 5], K = 4 | Deque
prefix sum: {3, 1, 6], K = 4, minimum length is 1, start and end index = 2
How to find it?
put index = 0 onto deque
iterate index = 1, deque size is 1, skip;
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;
        }
    }
}