Day 27 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#862. Shortest Subarray with Sum at Least K(H/JS)

Intro: I am a former accountant turned software engineer graduated from coding bootcamp. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.

Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:

• Pick a leetcode problem randomly or Online Assessment from targeted companies.
• Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
• Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
• Code out the solution in LeetCode without looking at the solutions
• Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.

---

862. Shortest Subarray with Sum at Least K
Difficulty: Hard Language: JavaScript

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1], k = 1
Output: 1

Example 2:

Input: nums = [1,2], k = 4
Output: -1

Example 3:

Input: nums = [2,-1,2], k = 3
Output: 3

Constraints:

• 1 <= nums.length <= 105
• -105 <= nums[i] <= 105
• 1 <= k <= 109

---

Solution(Prefix Sum/Deque):
The key to solve this problem is to find the prefix sum of given array. I linked a youtube video in the reference section, which very well explained the concept of prefix sum algorithm. Since the problem ask for a contiguous part of array; that makes deque a perfect method. A simple example for prefix sum: given array [1,2,3,4], if I want the sum of 3 and 4, I can get it by subtracting sum of 1 and 2 from sum of 1, 2, 3 and 4. This is a complicated problem and hard to explain with just words. Get a pen and paper ready to draw/write.

var shortestSubarray = function (A, K) {
    let n = A.length;

//Obtain the length of array 'A'(note 2)

    let len = Number.MAX_VALUE;

//Initialize 'len' with maximum integer in Javascript. The problem
//asks for shortest subarray and we will use Max.min (note 5) to
//get that min subarray amoung all eligible subarray. If we
//initialize the variable with 0 as we usually do, then the min
//value will always be 0.

    let prefixSum = new Array(n + 1);

//Create a 'prefixSum' array (note 3) with n+1 elements.

    prefixSum[0] = 0;

//Since prefixSum is calculated by adding current element in array
//'A' to previous element in array 'prefixSum'. We set the element
// (note 4) at index 0 as '0', so that the previous element of the
//first element is '0' instead of undefined/null.

    for (let i = 1; i < n + 1; i++)
        prefixSum[i] = A[i - 1] + prefixSum[i - 1];

//Loop (note 1) through 'prefixSum' array and calculate the prefix
//sum. For array [1,2,3,4], we will get a prefixSum array of
//[0,1,3,6,10]. That is 1, 1+2, 3+3, 6+4 respectively.

    let dq = [];

//We will keep prefixSum indices in here, remove the ones that are
//already verified or can be eliminated.Deque (Double Ended Queue)
//will allow us to remove/add element from front or end of an
//array (note 10).

  for (let i = 0; i < n + 1; i++) {

     while (dq.length && (prefixSum[i] - prefixSum[dq[0]]) >= K) {

//while (note 6) 'dq' is not empty and a prefixSum greater or
//equal to target 'K' is found，perform action below.

            len = Math.min(len, i - dq[0]);

//Update 'len' to current 'len' or 'i-dq[0]' whichever is smaller.

            dq.shift();

//Note that shift(note 9) will remove the first element from 'dq'.
//Once an eligible subarray is found, remove the used element
//in 'dq' and seek for the next possible shorter subarray. The
//while loop will continue as long as
//"prefixSum[i] - prefixSum[dq[0]]) >= K" is still valid. 

        }

while (dq.length && prefixSum[i] < prefixSum[dq[dq.length - 1]]) {
            dq.pop();

//In case where current prefixSum is less than previous prefixSum,
//a negative integer has appeared in array 'A' (only negative
//integer can reduce the sum). When that happens, we can pop off
//(note 11) the last element in 'dq'. Because in order to find the
//shortest array, we will start reducing element one by one from
//the left. That way we can reduce less amount from the total with
//a shorter subarray.

        }

        dq.push(i);

//regardless of condition above is met, push 'i' into 'dq'. 

    }

    return len == Number.MAX_VALUE ? -1 : len;

//if 'len' is still (note 7) it's initial value (Number.MAX_VALUE)
//, that means no eligible subarray is found, return -1. If found,
//return the min 'len' found.

};

---

References:
LeetCode Problem Link
LeetCode Discussion: steven_hai
Youtube: JAVAAID - Coding Interview Preparation
Note 1: while Loop
Note 2: Array.length
Note 3: Array constructor with a single parameter
Note 4: Access an array item by its index
Note 5: Math.min()
Note 6: while loop
Note 7: Conditional(ternary) operator
Note 8: Logical AND (&&)
Note 9: Array.shift()
Note 10: Double Ended Queue
Note 11: Array.pop()
Blog Cover Image Credit