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

 Here is the link. 

C# A few steps to solve a hard level algorithm

Oct. 3, 2020
862. Shortest Subarray with Sum at Least K

Introduction
It is important for me to move my focus from easy and medium level algorithm to hard level ones, since I already solved over 500 algorithms and it takes me over 5 years now. I have to start to work on one by one next four weeks to prepare Google phone screen in early November.

Worked on by myself first
I thought about preprocess the array using O(N) time first, so using prefix sum of the array it will take O(1) to calculate any subarray's sum.
In order for me to consider the shortest subarray at least K value, I have to look up previous index value and it's prefix sum. How to find shortest one if there are multiple ones?

What data structure can help to solve the problem? I did not come out the idea using deque data structure, if there are more than one to satisfy at last K value requirement, then the first one in the deque is shortest one for current index - assuming that iteration from start index 0 to last step of prefix array.

In other words, deque will have only one to satify at least K value requirement. And also the first one in the deque should be the candidate.

And also I need to filter out some index which will not be candidate for the start point of subarray to fit into K value requirement, which can be related to deque.

Quick study of discussion post and Leetcode solution
I came cross the solution, and I learn from the reasoning. Here is the link.

I also read the discussion post, but I understand that I will not really learn the algorithm until I can write the code with C# implementation, bug-free, work on a few case study.

C# implementation
I practiced the code and wrote one based on the discussion post here.

Here are highlights of my practice:

1. Design prefix sum array using length + 1 instead of length of the orginal array;
2. More on step 1, I failed the test case [2, -1, 2], so prefix array definition is changed to prefix[i] = sum of the array from 0 to i - 1, i is from 0 to length + 1;
3. I missed deque.Add(i) in my first writing, always go through manual checking - deque, four operations, remove-first, append_back, remove_back, insertion at the back and removal from both end;
4. Go through prefix sum array one by one, remove from end of deque if the last one will no longer be start of shortest subarray with at least K requirement; Remember a while loop, not once only using if.
5. Remove start of deque to make sure that if there are more than ones to satisfy at least K value, the first one in deque is shortest one.

Tips to share
Since I spent whole day to learn this algorithm, and also I asked the algorithm in my 10:00 PM mock interview, I like to write down as many tips as I can. So it is easy for me to review the algorithm later.

Work on case study, the array is [2, -1, 2], K = 3, the shortest length is 3. Work on the case and calculate by hand.
Work on case study, the array is [3, -2, 5], K = 4, the shortest length is 1, the subarray is [5].

Segment tree, range sum query is over-engineering for problem solving. I worked on segment tree algorithm, and I asked one question for code review on stackexchange, the algorithm is called kindergarten adventures.

Binary search algorithm based on length of subarray does not work. The interviewee went through the length of binary search, but [3, -2, 5], k = 4, the length = 1, subarray [5]'s sum >= 4, length = 2, non of subarray works, length = 3, [3, -2, 5] with sum = 6 working.

Deque can be implemented using C# LinkedList. Prefix sum array design is hard to work out best design in the first practice.

public class Solution {
    public 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 deque = 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];
            
            // while loop - continuously remove_back
            while(deque.Count > 1 && prefix[deque.Last.Value] >= current)
            {
                deque.RemoveLast();
            }
            
            // missing LinkedList Add?
            deque.AddLast(i);
            
            // remove_front - keep maximum one
            // if start point to current index's difference is at least K, 
            // then start point should be biggest index
            while(deque.Count > 1 && (current - prefix[deque.First.Next.Value] >= K))
            {
                deque.RemoveFirst();           
            }
            
            if( i > 0 && (current - prefix[deque.First.Value] >= K))      
            {
                shortest = Math.Min(shortest, i - deque.First.Value);       
            }
        }
                  
        return shortest == length + 1? -1 : shortest;           
    }
}