DEV Community: KillingLeetCode

Day 32 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#1487. Making File Names Unique(Med/JS)

KillingLeetCode — Sat, 19 Mar 2022 02:14:58 +0000

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.

1487. Making File Names Unique
Difficulty: Medium Language: JavaScript

Given an array of strings names of size n. You will create n folders in your file system such that, at the ith minute, you will create a folder with the name names[i].

Since two files cannot have the same name, if you enter a folder name that was previously used, the system will have a suffix addition to its name in the form of (k), where, k is the smallest positive integer such that the obtained name remains unique.

Return an array of strings of length n where ans[i] is the actual name the system will assign to the ith folder when you create it.

Example 1:

Input: names = ["pes","fifa","gta","pes(2019)"]
Output: ["pes","fifa","gta","pes(2019)"]
Explanation: Let's see how the file system creates folder names:
"pes" --> not assigned before, remains "pes"
"fifa" --> not assigned before, remains "fifa"
"gta" --> not assigned before, remains "gta"
"pes(2019)" --> not assigned before, remains "pes(2019)"

Example 2:

Input: names = ["gta","gta(1)","gta","avalon"]
Output: ["gta","gta(1)","gta(2)","avalon"]
Explanation: Let's see how the file system creates folder names:
"gta" --> not assigned before, remains "gta"
"gta(1)" --> not assigned before, remains "gta(1)"
"gta" --> the name is reserved, system adds (k), since "gta(1)" is
also reserved, systems put k = 2. it becomes "gta(2)"
"avalon" --> not assigned before, remains "avalon"

Example 3:

Input: names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)",
"onepiece"]
Output: ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)",
"onepiece(4)"]
Explanation: When the last folder is created, the smallest
positive valid k is 4, and it becomes "onepiece(4)".

Constraints:

1 <= names.length <= 5 * 104
1 <= names[i].length <= 20
names[i]consists of lowercase English letters, digits, and/or round brackets.

Solution:

Keep a map of each name and the smallest valid integer that can be appended as a suffix to it.
If the name is not present in the map, you can use it without adding any suffixes.
If the name is present in the map, append the smallest proper suffix, and add the new name to the map.

 var getFolderNames = function(names) {

    const folders = {}, counters = {}; const ans = [];

//initial three variables to respectively store name of the
//folder, count of each name if duplicated and final answer array 

    for(let i = 0; i < names.length; i++) {

//Loop through each name in the given array

        const name = names[i];
        let folderName = name, num = counters[name] || 1;

//if the ith name in the 'names' array is seen in 'counters', then
//assign it's value to num, otherwise num = 1.

        while(folders[folderName] !== undefined) {

//if the ith name in the 'names' array is seen in 'folders'

            folderName = `${name}(${num++})`;

//update folder name to the original name + number of time
//appeared

        }
        folders[folderName] = i;

//if the ith name in the 'names' array is NOT seen in 'folders',
//assign i as it's value.

        counters[name] = num;

//if the ith name in the 'names' array is NOT seen in 'counters',
//assign num as it's value.

        ans.push(folderName);

//Push updated folder name in the answer array

    }

    return ans;
};

Time Complexity: O(n)
Space Complexity: O(n)

References:
LeetCode Problem Link
LeetCode Discussion: _savely
Blog Cover Image Credit

Day 31 of Studying LeetCode until I Can Solve One on My Own: #1481. Least Number of Unique Integers after K Removals(M/JS)

KillingLeetCode — Sat, 19 Mar 2022 01:43:11 +0000

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.

1481. Least Number of Unique Integers after K Removals
Difficulty: Medium Language: JavaScript

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s.
1 and 3 will be left.

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length

Solution:

Use a map to count the frequencies of the numbers in the array.
Remove the numbers with the smallest count first.

var findLeastNumOfUniqueInts = function(arr, k) {
    let frequency = {}, uiqueInt=0

//Initial a map to count the frequencies of the numbers in the
//array. Also initial "uniqueInt" to keep count of unique integers. 

    for(let i = 0;i < arr.length;i++){

//Loop (note 1) through each interger in the array

        if(!frequency[arr[i]]){

//If the ith element in the array does NOT exsit in the map

            frequency[arr[i]] = 0

//initial the count for the ith element in the map

            uiqueInt++

//When new element is added in the map, increate the count of the
//unique element.

        }
        frequency[arr[i]]++

//If the ith element exists in the map, increase the frequency of
//that element.

    }

        let sortedFreq = Object.entries(frequency).sort((a,b)=>
{return a[1]-b[1]})

//sort the frequency map created from steps above in ascending
//order

    for(let i = 0;i < sortedFreq.length;i++){

//Loop through the sorted frequency map

        if(k >= sortedFreq[i][1]){

//If k is greater or equal to the frequency of the element

            k=k-sortedFreq[i][1]

//Subtract the frequency of that element from k. That means we
//made k moves to remove all of that element entirely.

            uiqueInt--

//Once removed, reduce the count for unique interger

        }else{
            break;

//if update k is less than frequency than any of the remainding
//element, break out of the loop. That means the element will
//still exist in the array even if we make k moves.

        }
    }
    return uiqueInt

//Return the number of unique interger(s).

};

Time Complexity: O(nlogn)
Space Complexity: O(n)

References:
LeetCode Problem Link
LeetCode Discussion: Suyash1798
Note 1: for loop
Blog Cover Image Credit

Day 30 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#1492. The kth Factor of n(Medium/JavaScript)

KillingLeetCode — Sat, 19 Mar 2022 00:32:51 +0000

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.

1492. The kth Factor of n
Difficulty: Medium Language: JavaScript

You are given two positive integers n and k. A factor of an integer n is defined as an integer i where n % i == 0.

Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors.

Example 1:

Input: n = 12, k = 3
Output: 3
Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor
is 3.

Example 2:

Input: n = 7, k = 2
Output: 7
Explanation: Factors list is [1, 7], the 2nd factor is 7.

Example 3:

Input: n = 4, k = 4
Output: -1
Explanation: Factors list is [1, 2, 4], there is only 3 factors.
We should return -1.

Constraints:

1 <= k <= n <= 1000

Solution:
My first thought was to get a list of all factors and store them in a new array; then find out if kth factor exists. The solution below didn't need to new array, which improved space complexity from O(n) to O(1).

var kthFactor = function(n, k) {
    for(let i = 1; i <= n; i++) {

//Iterating (note 1) every positive integer between 1 and n.

        if((n % i) === 0) {

//for every factor found (a factor is found when remainder is 0)
//(note 2 & 3).

            k--

//reduce the value of k

        }

        if(k === 0) return i

//if k is 0, then this is the target factor we are looking for

    }
    return -1

//otherwise return -1

};

Time Complexity: O(n)
Space Complexity: O(1)

References:
LeetCode Problem Link
LeetCode Discussion: Jeanstaquet
Note 1: for loop
Note 2: remainder%
Note 3: strict equality (===)
Blog Cover Image Credit

Day 29 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#70. Climbing Stairs(Easy/JavaScript)

KillingLeetCode — Thu, 10 Mar 2022 21:51:25 +0000

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.

70. Climbing Stairs
Difficulty: Hard Language: JavaScript

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

1 <= n <= 45

Solution (Recursive with Memoization):
This method might exceed the time limit as testing performed on 3/10/2022.

The key to solve this problem is that you can only climb 1 or 2 steps each time. If it takes 4 steps to get to the top of a staircase, we can climb to either the 1th level or the 2nd level on the first climb. Respectively, we have 3 more and 2 more steps left to climb. And if we already know the total distinct ways to climb 3 and 2 steps, then the total distinct ways to climb 4 steps will be 'total distinct ways to climb 3 steps + total distinct ways to climb 2 steps.' Recursive with Memoization will help us perform this calculation.

const cache = { 0: 0, 1: 1, 2: 2 }

//Initiate a map (note 2) that stores total distinct ways of
//climbing steps of 0, 1 and 2. There are 0 way to climb to the
//top of a staircase with 0 step. There are 1 way to climb to the
//top of a staircase with 1 step. There are 2 ways to climb to
//the top of a staircase with 2 steps. The value can be accessed
//with 'cashe[n].'(note 3)

function climbStairs(n) {
    if (n === 1) return 1;
    if (n === 2) return 2

//If n equals to (note 4) 1 or 2 then return the total possible
//combinations we already know from the problem itself.There are 1
//way to climb to the top of a staircase with 1 step. There are 2
//ways to climb to the top of a staircase with 2 steps. 

    if (!cache[n]) {

//'cache[n]' helps us access the staircase we have already
//climbed. If 'n' cannot (note 1) be found in 'cache,' that means
//it is a staircase we have not climbed before. Then we will
//calculate that in the step below and store it in 'cache'.

        cache[n] = climbStairs(n - 1) + climbStairs(n - 2);

//With recursion, the calculation will continue until n is equal
//to 1 or 2. 
//For n = 3,cache[3] = climbStairs(3 - 1) + climbStairs(3 - 2)
//total possible way to climb 3 steps is subtracting total ways to
//climb 2 steps by total ways to climb 1 step; that we can already
//find in cache { 0: 0, 1: 1, 2: 2 }.

//By performing 'cache[n] = X,' we can store value 'X' in the map
//with corresponding key of n. The update cache will be
//{ 0: 0, 1: 1, 2: 2, n: x }. And if we need to know how many
//distinct way we can climb a staircase with n step in the future
//calculation; we can use 'cache[n]' to get to the value 'x.'

    }
    return cache[n];

//Find the value in 'cache' with a key of n

}

Solution (Dynamic Programming):

function climbStairs(n){
    const dp = new Array(n).fill(0);
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;

//Create an array with n element and filled with 0.
//Initialize 'dp' with some base Cases

    for(let i=3; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2]

// Start from n=3 since we have covered the solutions up to N=2 above
// Sum the last 2 results behind me to get the current result.

    }
    return dp[n];
}

References:
LeetCode Problem Link
LeetCode Discussion: dclif
Note 1: Logical NOT (!)
Note 2: Map
Note 3: Access an array item by its index
Note 4: Strict equality (===)
Note 4: Javascript Recursion
Blog Cover Image Credit

Day 28 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#166. Fraction to Recurring Decimal(Med/JavaScript)

KillingLeetCode — Thu, 10 Mar 2022 00:45:15 +0000

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.

166. Fraction to Recurring Decimal
Difficulty: Hard Language: JavaScript

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than 104 for all the given inputs.

Example 1:

Input: numerator = 1, denominator = 2
Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

Input: numerator = 4, denominator = 333
Output: "0.(012)"

Constraints:

-231 <= numerator, denominator <= 231 - 1
denominator != 0

Solution:
To solve this problem:

Address the edge case where numerator is 0
Accese the sign ('+' or '-') of final result
Get the digit(s) on the left of the decimal point
Get the digit(s) on the right of the decimal point (use map for repeating digits.

var fractionToDecimal = function(numerator, denominator) {
    if(!numerator) return '0';

//if numerator(note 1)0 is 0 return 0. 

    let str = '';

//initiate an empty string

  if(Math.sign(numerator) !== Math.sign(denominator)) str += '-';

//Add (note 4) '-' to the string if the sign (note 2) for
//numerator and denominator is different (note 3)

    const numer = Math.abs(numerator)
    const denom = Math.abs(denominator)

//Obtain the absolute value (note 5) for the numerator and
//denominator. So that we are working with positive integers in
//below process. The sign of the output is already decided on the
//step above.

    str += Math.floor(numer/denom);

//Find the largest integer less than or equal to a given number
//(the number on the left of the decimal point) and add(note 4) it
//to the string. For exmaple, give [5,2], 5/2 = 2.5, 
//Math.floor (5/2) is 2. We will add '2' to the string.

    let rem = numer%denom;

//access the remainder (note 7)of numerator devided by denominator

    if(!rem) return str;

//if there is no (note 1) remainder, the output is a while number,
//return string.

    str += '.'

//If there is remainder, that means output will have decimal
//point. Add (note 4) '.' to the string.

    const map = new Map();

//Create map (note 8) to store remainders, which will help us
//access repeating numbers after the decimal points.

    while(rem !== 0) {

//start calculating the digit(s) after the dicimal point until
//remainder is 0.

        map.set(rem, str.length);

//Update map (note 9) and set new remainder as key and new
//str.length as value. The length of string here will be used in
//case where there are repeating digits after decimal point; to
//insert '()' around repeating digits.

        rem *= 10;
        str += Math.floor(rem/denom);
        rem %= denom

//This is an important step to access the numbers after the
//decimal point.For example, 1/8 = 0.125. To access the '1' and
//add it to the string, we 
//1. multiply the numberator 1 by 10; then divide it by 8; the
//result is 1*10/8 = 1.25. Use Math.floor (note 6) to access the
//'1' on the left of the decimal point. 
//2. We have a remainder of 2 from 10 devided by 8 above. Repeat
//the process to get 2*10/8 = 2.5. Use Math.floor (note 6) to
//access the '2'.
//3.We have a remainder of 4 from 20 devided by 8 above. Repeat
//the process to get 4*10/8 = 5. Use Math.floor (note 6) to access
//the '5'.
//4.Combine the three steps above, we have '125' which is what we
// need to get the final output of '0.125.'

        if(map.has(rem)) {

//This is how we find the repeating digits:
//As we calculate the remainder from steps above, we are also
//saving remainders in the 'map'. Given [4,333], we will have a
//map that looks like below:
//{ [4 ,2],   //  At index 2 of 'str', 4/333 => remainder is 4
//  [40,3],   //  At index 3 of 'str', 40/333 => remainder is 40
//  [67,4] }  //  At index 4 of 'str', 400/333 => remainder is 67
//Then again, at index 5 we will meet a remainder of 4 from
//670/333, this is when we know we find the repeating digit and it
//starts at index 5.

            const idx = map.get(rem);

//Get (note 11) the index that can help us locate the
//repeating digit and it will be where we insert the '()'. In case
//of [4,333] from above, the first remainder we will find in the
//'map' is 4, which has a value of '2'. That means the numbers
//from index 2 through 4 will repeat at index 5 though 7 and so
//on.

            return str.slice(0, idx) + `(${str.slice(idx)})`; 

//Current 'str' is '0.012', index 0 though 1 (2 is excluded) is
//sliced off (note 12). And starting from index 2, we add "()"
//around it. Now we have '0.' + '(012)' which is '0.(012)'.

        }
    }
    return str;
};

References:
LeetCode Problem Link
LeetCode Discussion: control_the_narrative
Note 1: Logical NOT (!)
Note 2: Math.sign()
Note 3: Strict inequality(!==)
Note 4: Addition assignment(+=)
Note 5: Math.abs()
Note 6: Math.floor()
Note 7: Remainder (%)
Note 8: Map
Note 9: Map.set()
Note 10: Map.has
Note 11: Map.get
Note 12: String.slice()
Note 13: String Interpolation
Blog Cover Image Credit

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)

KillingLeetCode — Wed, 09 Mar 2022 06:56:53 +0000

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

Day 26 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#42. Trapping Rain Water(Hard/JavaScript)

KillingLeetCode — Mon, 07 Mar 2022 01:35:50 +0000

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.

42. Trapping Rain Water
Difficulty: Hard Language: JavaScript

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is
represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6
units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

Solution(Two pointers):
Key to this method is compare the height of bar on the left end (index 0) and right end (index length - 1).

If the bar on the right end is taller, start calculating water being trapped from the left end (the lower end). Because it is guaranteed that the water will be trapped at the lower level until a new height shows up that makes the left end taller than the right end.
If the bar on the left end is taller or equal to the right end, we will calculater the water from the right end (the lower end)

var trap = function(height) {
    let leftMax = 0;
    let rightMax = 0;
    let result = 0;
    let left = 0;
    let right = height.length - 1;

//Initialize variables to keep track of starting from the left end
//(index 0) and the right end (index height.length - 1)(note 2).

    while(left < right) {

//while (note 1) left index is smaller than right index, loop
//continues.

        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);

//Max height (note 5) of left and right end bar will be updated as
//the index updates.

        if(height[left] < height[right]) {
            result += leftMax - height[left++];

//If the bar on the right end is taller, get the amount of trapped
//water by substracting height of next bar from current left max
//height. For example, give height [4,2,0,3,2,5], right bar '5' is
//taller than left bar '4'; it is guaranteed that the water will
//be trapped between these two bars until a new height shows up
//that makes the left end taller than the right end. Since all
//bars in between are less than 4 in this case. The left max
//remains at 4 and left index continue moves to the right
//(left++)(note 4); we will be adding (note 6) the total of 
//'4-2', '4-0','4-3','4-2' to our 'result' to get amount of
//trapped water. 

        } else {
            result += rightMax - height[right--];

//If the bar on the left end is taller or equal to the right end,
//we will calculater the water from the right end (the lower end).
//And move index towards left (right--) (note 3).

        }
    }
    return result;
};

Time Complexity - O(n)
Space Complexity - O(1)

References:
LeetCode Problem Link
LeetCode Discussion: Hongbo-Miao
LeetCode Discussion: ShashwatBangar
Youtube: TerribleWhiteboard
Note 1: while Loop
Note 2: Array.length
Note 3: Decrement (--)
Note 4: Increment (++)
Note 5: Math.max()
Note 6: Addition Assignment(+=)
Blog Cover Image Credit

Day 25 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#121. Best Time to Buy and Sell Stock(Easy/JS)

KillingLeetCode — Sun, 06 Mar 2022 20:19:55 +0000

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.

121. Best Time to Buy and Sell Stock
Difficulty: Easy Language: JavaScript

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price =
6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed
because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max
profit = 0.

Constraints:

1 <= prices.length <= 105
0 <= prices[i] <= 104

Solution:
My first though is to find all possible profits and get the max profit with two for loops, but that exceeds the time limit. Key to solve this problem is understanding that stock can only be sold after it's bought. We will set the prices on day one as purchase and loop through the prices array:

If a higher price is seem on the next day, save profit made by subtracting purchase price from the higher price. Note that the profit will be constantly updated whenever a new higher profit is found.
If a lower price is seem on the next day, set it as the new puchase price. Note the purchase price variable will be constantly updated whenever a new lower price is seem.
When the loop ends, the final profit is our answer.

var maxProfit = function(prices) {
    let purchase = prices[0] 
    let profit = 0

//set initial profit as 0 and the prices on day one (note 2) as
//puchase price

     for(let i = 1; i < prices.length; i++){

//Loop (note 1) prices array starting on index 1 as index 0 is
//already set as purchase price.

         if(prices[i] < purchase){
             purchase = prices[i]

//If (note 3) a lower price is seem on the next day, set it as the
//new puchase price.

         } else profit = Math.max(profit, prices[i] - purchase)

//If a higher price is seem on the next day, save profit made by
//subtracting purchase price from the higher price.Note that the
//profit will be constantly updated (note 4) whenever a new higher
//profit is found.

     }

    return profit
};

References:
LeetCode Problem Link
Youtube: ThinkFWD
Note 1: For Loop
Note 2: Access an array item by its index
Note 3: if...else
Note 4: Math.max()
Blog Cover Image Credit

Day 24 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#1395. Count Number of Teams(Medium/JavaScript)

KillingLeetCode — Sun, 06 Mar 2022 00:54:47 +0000

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.

1395. Count Number of Teams
Difficulty: Medium Language: JavaScript

There are n soldiers standing in a line. Each soldier is assigned a *unique *rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n). Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions.
(2,3,4), (5,4,1), (5,3,1).

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]
Output: 4

Constraints:

n == rating.length
3 <= n <= 1000
1 <= rating[i] <= 105
All the integers in rating are unique.

Solution:
Key to this solution is the number of teams that meets the condition can be calculated by finding the middle rating of the team. Multiply the count of ratings smaller than the middle rating by the count of ratings greater than middle rating will give us all posible combination that meets the condition. For example, given rating [1,2,3,4], there are 4 outputs that meet the conditon: [1,2,3],[1,2,4],[1,3,4],[2,3,4]. If we pick '2' as the middle rating, there are two numbers ('3' & '4') that are greater AND one number ('1') smaller than the middle rating. Therefore, total eligible combinations is two * one = 2. Based on this calculation, if we pick '3' as the middle rating; there are also two combinations. Total combinations is 2 + 2 = 4. Since 0 <= i < j < k < n, the middle rating can only be '2' or '3'. This problem allows the combinations to be ascending and descending order; so we will consider these two situation when we write code.

var numTeams = function(rating) {

    let solution = 0;

//initialize solution as 0

    for (let i = 1; i < rating.length - 1; i++){

//Loop (ntoe 1) through 'rating' array and keep count of numbers
//that are greater or smaller than raiting[i]. Because we are
//locating the middle ratings, the iteration will start at 1 and
//end at the second last number (rating.length-1)(ntoe 2) in the
//array.

    let ascSmaller = 0,
        ascGreater = 0,
        descSmaller = 0,
        descGreater = 0;

//Declare variables and set initial value as 0, these counts are
//used to calculate the solution 

        for (let j = i+1; j < rating.length; j++){
            if (rating[j] > rating[i]) ascGreater++
            if (rating[j] < rating[i]) descSmaller++
        }

//starting from the number next to middle number and end at last
//element of the array. If the numbers are greater than middle
//number increase (note 4) count for 'ascGreater' and
//'descSmaller' respectively.

        for (let j = i-1; j >= 0; j--){
            if (rating[j] > rating[i]) descGreater++
            if (rating[j] < rating[i]) ascSmaller++
        }

//starting from the number prior to middle number and end at first
//element of the array. If the numbers are smaller than middle
//number increase (note 4) count for 'descGreater' and
//'ascSmaller' respectively.

       solution += ascSmaller*ascGreater + descSmaller*descGreater

//as mentioned in the explanation above, this problem allows the
//combination to be ascending and descending order. Hence, we
//combine (note 3) the total output for each order together.

    }

    return solution
};

Time and Space Complexity

Time: O(n^2)
Space: ?

References:
LeetCode Problem Link
Note 1: For Loop
Note 2: Array.length
Note 3: Addition assignment (+=)
Note 4: Increment (++)
Blog Cover Image Credit

Day 23 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#155. Min Stack(Easy/JavaScript)

KillingLeetCode — Sat, 05 Mar 2022 01:55:19 +0000

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.

155. Min Stack
Difficulty: Easy Language: JavaScript

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:

-231 <= val <= 231 - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 104 calls will be made to push, pop, top, and getMin.

Solution:
Highlight of this problem is constant time O(1) (note 2) is required instead of linear time. And the key to solve it is to create two stack: one regular 'stack' and a 'min' stack to store minimun value of all elements being added. To further explain, when a new element is added to the 'stack', compare this element with the smallest element in 'min' stack. If the new element is smaller than the smallest element in 'min' stack, add this new element to the 'min' stack. Otherwise, duplicate the smallest element in 'min' stack and push it to 'min' stack again. This way, the top element in the 'min' stack in always the minimum. And when we need to access the minimum value, we just need to get the top element in 'min' stack.

class MinStack {
    constructor() {
        this.stack = [];
        this.min = [];
    }

//construct (note 1) two stack under class MinStack. One regular
//'stack and the other 'min' stack used to store minimum value

    push(x) {
        if (!this.min.length) this.min.push(x);
        else this.min.push(Math.min(x, this.getMin()));

//If length (note 3) of 'min' stack does not exist (note 4), then
//it's an empty array. Push (note 5) element 'x' into 'min'
//stack.If 'min' stack is not empty, compare 'x' and the smallest
//value currently in 'min' stack, and push the smaller value into
//'min' stack. 

        this.stack.push(x);

//Push (note 5) element 'x' into the regular 'stack'.

    }

    pop() {
        this.min.pop()
        return this.stack.pop()

//Pop (note 6) last element from both stack

    }

    top() {
        return this.stack[this.stack.length-1];

//return last element of the stack

    }

    getMin() {
        return this.min[this.min.length-1];

//return last element of the stack which is also the minumum

    }
}

Time and Space Complexity

Time: O(1)
Space: O(2N)

References:
LeetCode Problem Link
LeetCode Discussion: control_the_narrative
Youtube: Andy Gala
Note 1: Classes (JS/ES6)
Note 2: Constant time
Note 3: Array.length
Note 4: Logical NOT (!)
Note 5: Array.push()
Note 6: Array.pop()
Blog Cover Image Credit

Day 22 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#1041. Robot Bounded In Circle(Medium/JavaScript)

KillingLeetCode — Fri, 04 Mar 2022 19:48:42 +0000

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.

1041. Robot Bounded In Circle
Difficulty: Medium Language: JavaScript

On an infinite plane, a robot initially stands at (0, 0) and faces north. Note that:

The north direction is the positive direction of the y-axis.
The south direction is the negative direction of the y-axis.
The east direction is the positive direction of the x-axis.
The west direction is the negative direction of the x-axis.

The robot can receive one of three instructions:

"G": go straight 1 unit.
"L": turn 90 degrees to the left (i.e., anti-clockwise direction).
"R": turn 90 degrees to the right (i.e., clockwise direction). The robot performs the instructions given in order, and repeats them forever.

Return true if and only if there exists a circle in the plane
such that the robot never leaves the circle.

Example 1:

Input: instructions = "GGLLGG"
Output: true
Explanation: The robot is initially at (0, 0) facing the north
direction.
"G": move one step. Position: (0, 1). Direction: North.
"G": move one step. Position: (0, 2). Direction: North.
"L": turn 90 degrees anti-clockwise. Position: (0, 2). Direction:
West.
"L": turn 90 degrees anti-clockwise. Position: (0, 2). Direction:
South.
"G": move one step. Position: (0, 1). Direction: South.
"G": move one step. Position: (0, 0). Direction: South.
Repeating the instructions, the robot goes into the cycle: (0, 0)
--> (0, 1) --> (0, 2) --> (0, 1) --> (0, 0).
Based on that, we return true.

Example 2:

Input: instructions = "GG"
Output: false
Explanation: The robot is initially at (0, 0) facing the north
direction.
"G": move one step. Position: (0, 1). Direction: North.
"G": move one step. Position: (0, 2). Direction: North.
Repeating the instructions, keeps advancing in the north direction
and does not go into cycles.
Based on that, we return false.

Example 3:

Input: instructions = "GL"
Output: true
Explanation: The robot is initially at (0, 0) facing the north
direction.
"G": move one step. Position: (0, 1). Direction: North.
"L": turn 90 degrees anti-clockwise. Position: (0, 1). Direction:
West.
"G": move one step. Position: (-1, 1). Direction: West.
"L": turn 90 degrees anti-clockwise. Position: (-1, 1). Direction:
South.
"G": move one step. Position: (-1, 0). Direction: South.
"L": turn 90 degrees anti-clockwise. Position: (-1, 0). Direction:
East.
"G": move one step. Position: (0, 0). Direction: East.
"L": turn 90 degrees anti-clockwise. Position: (0, 0). Direction:
North.
Repeating the instructions, the robot goes into the cycle: (0, 0)
--> (0, 1) --> (-1, 1) --> (-1, 0) --> (0, 0).
Based on that, we return true.

Constraints:

1 <= instructions.length <= 100
instructions[i] is 'G', 'L' or, 'R'.

Solution:
Key so solving this problem is figure out how to change directions. Coordinates will be set up as x and y. And direction Up, Right, Down, Left is respectively set up as
[[0, 1], [1, 0], [0, -1], [-1, 0]]. Note these direction is located at index 0, 1, 2, 3 and these indices will be used in the next step to indicate which direction the robot should move towards. For example, when direction is at index 2, we get [0,-1] and that means the Robot will move down by 1 (y-1). How do we get these indices/directions? Since robot initially stands at (0, 0) and faces north, we will declare a variable 'head' as 0 facing north. If we turn right one time from head = 0, then we get 'head + 1'. That's index 1 -> [1,0] and Robot will move to the right by 1 (x+1). In order to turn left, we have to turn right three times from head = 0, then we get 'head + 3'. That's index 3 -> [-1,0] and Robot will move to the left by 1 (x-1).mod 4 is there because we come to face the same direction when you turn 4 times.

function isRobotBounded(instructions) {
    const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];

//set up directions represent for 'Up', 'Right', 'Down', 'Left'
//respectively. We will later access these directions by their
//indices.

    let head = 0;

//Since robot initially stands at (0, 0) and faces north, we will
//declare a variable 'head' as 0 facing north.

    let x = 0;
    let y = 0;

//Coordinates is set up as `x` and `y`.

    for (const instruction of instructions) { 

//Loop (note1) through each letter in the given string

        if (instruction === 'G') {
            x = x + dirs[head][0];
            y = y + dirs[head][1];

//If (note 2) letter is 'G', update cordinate x and y based on the
//direction (note 3) obtained from steps below

        } else if (instruction === 'L') {
            head = (head + 3) % 4;

//if (note 2) letter is 'L', add 3 to 'head' then % 4 to turn
//left, see explanation above to see why we are adding 3 and % 4

        } else {
            head = (head + 1) % 4;

//if (note 2) letter is 'R', add 1 to 'head' then % 4 to turn
//right, see explanation above to see why we are adding 1 and % 4

        }
    }

    const isAtOrigin = (x === 0 && y === 0);
    const isHeadingNorth = head === 0
    return isAtOrigin || (! isHeadingNorth);

//return true if x and y both (note 5) equals to 0 (note 4), as
//[0,0] means Robot is at it's origin. 

};

Time and Space Complexity

Time: O(N)
Space: O(1)

References:
LeetCode Problem Link
LeetCode Discussion: pivacik
LeetCode Discussion: hbjORbj
Note 1: Loop and Iteration
Note 2: if...else
Note 3: Access array item by its index
Note 4: Strict equality (===)
Note 5: Logical AND (&&)
Blog Cover Image Credit

Day 21 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#387. First Unique Character in a String(Easy/JS)

KillingLeetCode — Fri, 04 Mar 2022 05:12:31 +0000

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.

387. First Unique Character in a String
Difficulty: Easy Language: JavaScript

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example 1:

Input: s = "leetcode"
Output: 0

Example 2:

Input: s = "loveleetcode"
Output: 2

Example 3:

Input: s = "aabb"
Output: -1

Constraints:

1 <= s.length <= 105
s consists of only lowercase English letters.

Solution 1 (Hashmap):

var firstUniqChar = function(s) {

    let hash = {}

//Intialize a hash table (note 6) that allows us to save data as
//such: {character1:count1, character2:count2, character3:count3}

    for(let i = 0; i < s.length; i++){

//Loop (note 1) through string 's' and save character and count
//into the hashtable created above

    hash[s.charAt(i)]? hash[s.charAt(i)]++ : hash[s.charAt(i)] = 1

//if such character exist, increase count by 1, if not (note 7),
//let count equal to 1. 's.charAt(i)' gives us the
//character at index i and 'hash[character]' will point to the
//count of that character.

    }

    for(let i = 0; i < s.length; i++){

//Loop (note 1) through the string once more time to identify the
//count for each letter that is now stored in 'hash'

        if(hash[s.charAt(i)] == 1) return i

//if (note3)count of character at (note 4) index i has count equal
//(note5) to 1, return the index. 's.charAt(i)' gives us the
//character at index i and 'hash[character]' will point to the
//count of that character.

    }

    return -1

//if such index doesn't exist, return -1

};

Solution 2 :

var firstUniqChar = function(s) {
    for(i=0; i<s.length; i++)

//Loop (note 1) through string 's' and see if there is more than
//once index for a character.

        if(s.indexOf(s[i])===s.lastIndexOf(s[i])) return i

//if the first index (note 7) and last index (note 8) found for a
//character is the same, that means this character is unique. If
//this character is found at more than one index, there are
//duplicates of this character in the string.

    return -1

//if such index doesn't exist, return -1

};

References:
LeetCode Problem Link
LeetCode Discussion: miryang
Note 1: Loop and Iteration
Note 2: Addition assignment (+=)
Note 3: if...else
Note 4: String.prototype.charAt()
Note 5: Equality (==)
Note 6: JS Hash Table
Note 7: Ternary Operator
Note 8: Array.indexOf()
Note 9: Array.lastindexOf()
Blog Cover Image Credit