public-notes/LeetCode - JavaScript.md at main · ajvsol/public-notes

Related: [[JavaScript]] : ((6341c12f-21ed-489f-bb16-1734abd32b1f))
Meta
Takeaways
TEMPLATE collapsed:: true
- My solution
- Best practice
Completed solutions

[Learning Resources]

Grind 75 (v2 of ((64bcadf7-2fb0-4d59-89a7-7b565d18560b)) ) collapsed:: true

Array

Easy

Two Sum id:: 0e542595-2f6d-4864-9ff5-9f953ccd7a29 collapsed:: true

My solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j]
            }
        }
    }
};

Best practice - Solutions

Approach 1: Brute Force collapsed:: true

Cons
- Succeeds the first test cases, but fails the ones where they use huge integers

var twoSum = function(nums, target) {
    for (let j = 0; j < nums.length; j++) {
        for (let i = j + 1; i < nums.length; i++) {
            console.log(`j: ${j} and i: ${i} and target: ${target}`)
            if (nums[j] === target - nums[i]) {
                return [j, i]
            }
        }
    }
    return null
};

Approach 2: Two-pass Hash Table

var twoSum = function(nums, target) {
    // create a new Map
    let map = new Map();
    // loop over the nums
    for (let i = 0; i < nums.length; i++) {
      // store the complement between current num and the target
	  // if target 10, and num[i] = 6 there is only ONE number that we can add to 6 to make it 10. 
        // That is the number 4. We call it the complement because it complements 6 to hit the target 10.
        // EG if target = 10 and nums[i] = 6....  10 - 6 = complement = 4
        let complement = target - nums[i];
        // What we are going to do is check if the complement exists in the hashmap.
        // If the map already contains the complement we will return an array with the index of the complieent. And current index.
        // When calling map.get(complement) in the return, this will return the VALUE at that key 
        if (map.has(complement)) {
           return [map.get(complement), i];
        } else {
          // Since the complement does not exist as a key in the map.
          // We store the key num[i], and index as the value for that key.
          map.set(nums[i] , i)
        }
    }
    // If there is no complement we will return an empty array. 
return [];
};

((63904f3d-96c1-429e-af8b-4a46b1bf89c5))
((63904f3d-6b67-461e-bf92-5f55bc24fa36))

var twoSum = function(nums, target) {
    let map = new Map();
    for(let i = 0; i < nums.length; i ++) {
        if(map.has(target - nums[i])) {
            return [map.get(target - nums[i]), i];
        } else {
            map.set(nums[i], i);
        }
    }
	return [];
};

One-pass Hash Table

var twoSum = function(nums, target) {
    const indices = new Map();
    for (let index = 0; index < nums.length; index++) {
        const complement = target - nums[index];
        if (indices.has(complement)) {
            return [indices.get(complement), index]
        }
        indices.set(nums[index], index)
    }
};

Best Time to Buy and Sell Stock collapsed:: true
- My solution
- Best practice
Contains Duplicate id:: 63f3d7d0-a1ab-4f21-8ce8-fa4ae7aed53d
Majority Element

Medium

String collapsed:: true
- Easy
- Medium
- Hard
  - Minimum Window Substring
Matrix - Medium collapsed:: true
- Spiral Matrix
Graph collapsed:: true
- Easy
  - Flood Fill
- Medium
- Hard
  - Word Ladder
Binary - Easy collapsed:: true
- Add Binary
Binary Search collapsed:: true
- Easy
  - Binary Search
  - First Bad Version
- Medium
  - Search in Rotated Sorted Array
  - Time Based Key-Value Store
- Hard
  - Maximum Profit in Job Scheduling
Binary Search Tree collapsed:: true
- Easy
  - Lowest Common Ancestor of a Binary Search Tree
- Medium
  - Validate Binary Search Tree
  - Kth Smallest Element in a BST
Binary Tree collapsed:: true
Hash Table - Easy collapsed:: true
- Ransom Note
Recursion - Medium collapsed:: true
Linked List collapsed:: true
- Easy
- Medium
  - LRU Cache
Stack collapsed:: true
- Easy
  - Valid Parentheses
  - Implement Queue using Stacks
- Medium
  - Evaluate Reverse Polish Notation
  - Min Stack
- Hard
Heap collapsed:: true
- Medium
  - K Closest Points to Origin
  - Task Scheduler
- Hard
  - Find Median from Data Stream
  - Merge k Sorted Lists
Trie - Medium collapsed:: true
- Implement Trie (Prefix Tree)
- Word Break
Dynamic Programming collapsed:: true
- Easy
  - Climbing Stairs
- Medium

Blind 75 id:: 64bcadf7-2fb0-4d59-89a7-7b565d18560b collapsed:: true

LeetCode - Top Interview Questions - Easy Collection collapsed:: true

Array

Remove Duplicates from Sorted Array collapsed:: true

My solution

var removeDuplicates = function(nums) {
    
    nums.forEach((el, ind) => {
        if (nums.indexOf(el) !== nums.lastIndexOf(el)) {
            nums.splice(el, 1)
        }
    })
    console.log(`nums:`, nums)
    return nums.length
};

Best practice

```
var removeDuplicates = function (nums) {
    var i = 0;
    nums.forEach(el => {
        if (el !== nums[i]) {
            nums[++i] = el;
        }
    });
    return nums.length && i + 1;
};
```
- Explanation 1
  - ```
  var removeDuplicates = function (nums) {
      var i = 0;
      nums.forEach(function (elem) { // iterate over each element of the nums array
          if (elem !== nums[i]) { // if elem is not the same as the previous element
              nums[++i] = elem; // add elem to the array and then increment i to point to the next index after setting elem
          }
      });
      return nums.length && i + 1;  // if nums is empty, return 0, otherwise return i + 1
  };
```
- Explanation 2
  - ((635eb08f-9a44-4545-88c0-b7064e94f590)) because the algorithm has to be done in-place - no creation of additional arrays
  - i was incremented for every new unique element
  - return nums.length && i + 1
    - The expression nums.length && i + 1 in this function returns the length of the modified array if it is not empty (has at least one element) and i + 1 otherwise.
    - The && operator in JavaScript is known as the logical AND operator. It returns the first operand if it is falsy, and the second operand otherwise. In this case, nums.length is the first operand and i + 1 is the second operand. If nums.length is 0 (which is a falsy value), the expression returns 0, indicating that the array is empty. Otherwise, if nums.length is not 0, the expression returns i + 1, which is the length of the modified array with duplicates removed.
    - This way, if the input array is empty, the function will return 0, and if there are any elements in the array, it will return the length of the modified array.

var removeDuplicates = function(nums) {
    let pointer = 0;    
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== nums[i+1]) {
            nums[pointer] = nums[i];
            pointer++;
        }
    }
    return pointer;
};

Best Time to Buy and Sell Stock II collapsed:: true

My solution

var maxProfit = function(prices) {
    let profit = 0
    let prev
    prices.reduce((acc, val, ind, arr) => {
      // reduce starts with index 1 unlike other methods, so first need to set value of `prev` as otherwise the 0th index item is unassigned
        if (!prev) {
            prev = arr[ind-1]
        }
      // if next item is higher value than previous, then the profit is the difference
        if (val > prev) {
            profit += val - prev
        }
        prev = val // set `prev` to the current value
    })
        
    return profit 
};

Note: not using acc here. Probably should be swapped for profit

Similar "Implementation based on O(1) aux space"

var maxProfit = function(prices) {
    let profitFromPriceGain = 0;
    for( let i = 0 ; i < prices.length-1 ; i++ ){
        if( prices[i] < prices[i+1] ){
            profitFromPriceGain += (prices[i+1] - prices[i]);
        }
    }
    return profitFromPriceGain;
}

((6350374d-3846-414b-a27e-7d32b86eec86))

Best practice

O(n) sol by DP + state machine. Bottom-up DP + iteration

var maxProfit = function(prices) {
    // It is impossible to sell stock on first day, set -infinity as initial value for curHold
    let [curHold, curNotHold] = [-Infinity, 0];
    
    for(const stockPrice of prices){
        let [prevHold, prevNotHold] = [curHold, curNotHold];
        // either keep hold, or buy in stock today at stock price
        curHold = Math.max(prevHold, prevNotHold - stockPrice );
        // either keep not-hold, or sell out stock today at stock price
        curNotHold = Math.max(prevNotHold, prevHold + stockPrice );
    }
    // Max profit must come from notHold state finally.
    return curNotHold; 
};

Rotate Array collapsed:: true

My solution

var rotate = function(nums, k) {
	k = k % nums.length
    nums.unshift(...nums.splice(-k));
};

Wrong solution

Doesn't work if k > nums.length

var rotate = function(nums, k) {
	nums.unshift(...nums.splice(nums.length - k))
};

Using immutable method not mutable

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    let arr1 = nums.slice(nums.length - k) 
    console.log(`arr1:`, arr1)
    let arr2 = nums.slice(0, nums.length - k)
    console.log(`arr2:`, arr2)
    return [...arr1, ...arr2]
};

Best practice

var rotate = function (nums, k) {
  for (let i = nums.length - 1; i >= 0; i--) {
    nums[i + k] = nums[i];
  }

  for (let j = k - 1; j >= 0; j--) {
    nums[j] = nums.pop();
  }

  // Time comlexity = O(a + b)
};

Explanation 1 collapsed:: true

var rotate = function (nums, k) {
  // i.e. nums = [1, 2, 3, 4, 5, 6, 7],  k = 3
  for (let i = nums.length - 1; i >= 0; i--) {
    nums[i + k] = nums[i];
    // i = 6,  k = 3
    // nums[i + k] = nums[i]
    // nums[6 + 3] = nums[6]
    // nums[9] = 7              nums = [1, 2, 3, 4, 5, 6, 7, , , 7]

    // i = 5,  k = 3
    // nums[i + k] = nums[i]
    // nums[5 + 3] = nums[5]
    // nums[8] = 6              nums = [1, 2, 3, 4, 5, 6, 7, , 6, 7]

    // i = 4,  k = 3
    // nums[i + k] = nums[i]
    // nums[4 + 3] = nums[4]
    // nums[7] = 5              nums = [1, 2, 3, 4, 5, 6, 7, 5, 6, 7]

    // i = 3,  k = 3
    // nums[i + k] = nums[i]
    // nums[3 + 3] = nums[3]
    // nums[6] = 4              nums = [1, 2, 3, 4, 5, 6, 4, 5, 6, 7]

    // i = 2,  k = 3
    // nums[i + k] = nums[i]
    // nums[2 + 3] = nums[2]
    // nums[5] = 3              nums = [1, 2, 3, 4, 5, 3, 4, 5, 6, 7]

    // i = 1,  k = 3
    // nums[i + k] = nums[i]
    // nums[1 + 3] = nums[1]
    // nums[4] = 2              nums = [1, 2, 3, 4, 2, 3, 4, 5, 6, 7]

    // i = 0,  k = 3
    // nums[i + k] = nums[i]
    // nums[0 + 3] = nums[0]
    // nums[3] = 1              nums = [1, 2, 3, 1, 2, 3, 4, 5, 6, 7]
  }

  for (let j = k - 1; j >= 0; j--) {
    // nums = [1, 2, 3, 1, 2, 3, 4, 5, 6, 7]
    nums[j] = nums.pop();

    // j = 2
    // nums[j] = nums.pop()
    // nums[2] = 7               nums = [1, 2, 7, 1, 2, 3, 4, 5, 6]

    // j = 1
    // nums[j] = nums.pop()
    // nums[1] = 6               nums = [1, 6, 7, 1, 2, 3, 4, 5]

    // j = 0
    // nums[j] = nums.pop()
    // nums[0] = 5               nums = [5, 6, 7, 1, 2, 3, 4]
  }

  // nums = [5, 6, 7, 1, 2, 3, 4]

  // Time comlexity = O(a + b)
};

var rotate = function (nums, k) {
    const len = nums.length
    k = (k % len)
    
    let end = nums.splice(len - k)

    nums.splice(0,0,...end)
};

((63f3d7d0-a1ab-4f21-8ce8-fa4ae7aed53d))
((0e542595-2f6d-4864-9ff5-9f953ccd7a29))

Strings
Linked List
Trees
Sorting and Searching
Dynamic Programming
Design
Math
Others

Study cheatsheet from Grind 75 site

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Array

Binary

Dynamic Programming

Graph

Interval

Linked List

Matrix

String

Tree

Heap

FilesExpand file tree

LeetCode - JavaScript.md

Latest commit

History

LeetCode - JavaScript.md

File metadata and controls

Array

Binary

Dynamic Programming

Graph

Interval

Linked List

Matrix

String

Tree

Heap