Intro: I am a former accountant turned software engineer graduated from coding bootcamp in January 2022. 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.
209. Minimum Size Subarray Sum
Difficulty: Medium
Language: JavaScript
Given an array of positive integers nums
and a positive integer
target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr]
of which the sum is greater than or equal to target
. If there is no such subarray, return 0
instead.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the
problem constraint.
Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Constraints:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
Follow up: If you have figured out the O(n)
solution, try coding another solution of which the time complexity is O(n log(n))
.
Solution:
var minSubArrayLen = function(target, nums) {
let distance = Number.MAX_SAFE_INTEGER;
//initialize the distance variable with maximum safe integer in
//JavaScript
let left = 0;
// left pointer and right pointer defines the window.
let sum = 0;
//sum keep track of total value
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
//Loop (note 1) through 'nums; array and keep adding (note 3)
//value (note2) to the 'sum' until it meets the give target
while (sum >= target) {
//while (note 7) sum is greater than or equal to target, keep
//searching for the smallest window (minimal length/distance) that
//has a sum of target or larger.
distance = Math.min(distance, right - left + 1);
//the distance between start and end point of continous elements
//that adds up to the sum is 'right - left + 1'. For example, if
//given array is [2,3,1,2,4,3] and target is 7. The length of last
//two element [4,3] that adds up to 7 is 5 (right) - 4 (left) + 1
// = 2.
sum -= nums[left];
left += 1;
//continue finding the minimal distance by reducing sum in amount
//of nums[left] and adding nums[right]. In given array
//[2,3,1,2,4,3] with target of 7, even though the first four
//number [2,3,1,2] add together is already greater than 7; we
//should keep moving one element to the right (e.g: get [3,1,2,4]
//by reduce the '2' (nums[left]) and adding the '4'(nums[right]))
//until we get [4,3], the shortest distance that meets the target.
}
}
return distance === Number.MAX_SAFE_INTEGER ? 0 : distance;
//since the distance was initialized as the maximum safe integer;
//if new distance was never found, the value will stay as the
//maximum safe interger. That means there is no such subarray
//that has a sum greater or equal to target. We return 0. If
//found, return the distance. The 'Math.min' (note 5) in above
//code made sure that the distance returned is the shortest.
};
Solution Submission detail as of 2/25/2022
(Data below could vary since there are new tests/submissions daily)
- Runtime: 84 ms
- Memory Usage: 42.3 mb
References:
LeetCode Problem Link
LeetCode Discussion:DawChihLiou
Youtube: Adam Coder
Note 1: Loop and Iteration
Note 2: Access an array item by its index
Note 3: Conditional (ternary) operator
Note 4: Addition assignment(+=)
Note 5: Math.min()
Note 6: Number.MAX_SAFE_INTEGER
Note 7: while loop
Blog Cover Image Credit
Top comments (0)