# Leetcode

###### tags: `interview`

## Reference
https://github.com/azl397985856/leetcode
刷題順序: https://www.zhihu.com/question/321738058/answer/1279464192
LeetCode題目分類: https://www.zhihu.com/question/280279208/answer/824585814

## Progress

Coco

| Date | Progress |
| -------- | ------------------------------ |
| 12/12~15 | 26,66,121,122,283,575,821,1260 |
| 12/15~20 | 33,229,238,20,155,232,103,144,150,394,445,199 |

Meeting
| Date | Progress |
| -------- | ------------------------------ |
| 12/12~15 | 26,66,121,122,283,575,821,1260 |
| 12/15~20 | 33,229,238,20,155,232,103,144 |
| 12/21~23 | 150,394,445,199 |
| 12/23~27 | 21,160,203,206 |
| 12/29 | 1,219,349,599 |
| 1/3 | 49,3,451,454 |
| 1/5 | 101,108,94,95 |

## Tags
191 frequently asked questions

**Progress 1**
Data Structure:
- [ ] String
- [ ] Array
Easy: 26,66,121,122,283,575,821,1260
Medium: 33,229,238
- [ ] Stack
Easy:20,155,232
Medium: 103,144,150,394,445
- [ ] Queue
Medium: 199
- [ ] Linked List
Easy: 21,160,203,206
Medium: 2,19,24,61,86,92,147,328,445
- [ ] Hash Table
Easy:1,219(hashmap),349,599
Medium:49,3,451,454
- [ ] Tree, Binary Search Tree
Easy: 101,108,
Medium: 94,95,96,98,144,230,236,337
- [ ] Two Pointers
Easy:26,125,160,167,190,283,455
Medium: 11,15,19,61,80,209,334

Algorithm:
- [ ] Sort(Merge Sort, )
Easy:88
Medium: 15,49,56,75,147
- [ ] Recursion
Easy:21,101,104,108,172,226,
Medium: 50,94,129,236,279,343

**Progress 2**
Data Structure:
- [ ] Binary Search
Medium: 29,33,209,240,378
- [ ] Graph

Algorithm:
- [ ] Backtracking
Medium: 17,22,31,39,40,46,47,60,78,79,90,113,131
- [ ] DFS
Medium: 22,113,129,130,200
- [ ] BFS
Medium: 102,103,365,513
- [ ] Dynamic Programming
Easy:53,198
Medium: 62,91,95,139,152,221,279,309,322,337,343,416,494,516,518
- [ ] Sliding Window
Easy:53
Medium: 3,152,209

**Progress 3**
Data Structure:
- [ ] Heap
Medium: 215,378

Algorithm:
- [ ] Divide and Conquer
Medium: 15,95,96,215,240
- [ ] Trie
Medium:208,211
- [ ] Greedy
Easy:455
Medium: 55,322
- [ ] Segment Tree
- [ ] Union Find
Medium:547
- [ ] Bit Manipulation
Easy: 136,191,371
Medium: 50,201

**Remaining**
, Design, Binary Indexed Tree, Brainteaser, Memoization, Minimax, Reservoir Sampling, Ordered Map, Geometry, Random, Rejection Sampling, , Line Sweep, Rollling Hash, Suffix Array, Dequeue, OOP

- [ ] Boyer–Moore majority vote
Easy:169
Medium:229
- [ ] Math
Easy:263,342,1260
- [ ] Palindromic
Easy:1332
Medium: 5
- [ ] in-place algorithm
Medium:48
- [ ] Matrix
Medium:48,73

## Array

### Q66 Plus One
> Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.
> \
> The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.
> \
> You may assume the integer does not contain any leading zero, except the number 0 itself.
>
> Example1:
> Input: digits = [1,2,3]
> Output: [1,2,4]
> Explanation: The array represents the integer 123.

Idea:
I'll firstly try for loop for this question.
The first thing that comes to my mind is the number 9 in the last digit, after adding 1, it'll become 10. How to let the number at the index that's before you to know it has to add 1, too? I'll declare a variable called `need_tobe_added`. `need_tobe_added` contains the number that should be added, so after we add it, it should deduct 1.
Until we traverse to the element that's less than 9, we can add 1 to it, and return the array.
Notice that, if it's the case like 99, after adding 1, it'll becomes 100, but we only have 2 elements in the original array. In this kind of case, we'll have to create 1 more space in the beginning of the original array. And it only happens when the for loop iterate through all elements, but there's still something that's need to be added. So we'll put an ifelse statement in after the for loop to see whether we need to push an element in the beginning of the array.

/**
 * @param {number[]} digits
 * @return {number[]}
 
 case1: [1,2,3]
 case2: [1,2,9]
 case3: [9,9,9]
 */

var plusOne = function(digits) {
    let need_tobe_added = 1
    for (let i = digits.length-1; i >=0; i-- ) {
        digits[i] += need_tobe_added
        need_tobe_added -= 1
        
        if (digits[i] > 9) {
            need_tobe_added += 1
            digits[i] -= 10
        } else {
            return digits
        }
        
    }
    if (need_tobe_added > 0) {
        digits.unshift(need_tobe_added)
    }
    return digits
    
};

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

#### Helpful Method: unshift

### Q121 Best Time to Buy and Sell Stock
> Say you have an array for which the ith element is the price of a given stock on day i.
\
> If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
\
> Note that you cannot sell a stock before you buy one.
>
> Example 1:
> Input: [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

Idea:
這題老是想得太複雜，其實不需要在意何時買賣，題目只要maxProfit。
重要的是如果遇到了一個比之前更低的價格，就紀錄 `minPrice`。
如果算出來maxProfit比原本大，就update `maxProfit`。
所以主要是這兩個變數要天天更新。

更新maxProfit時間點，如果今天價格比昨天高，有兩種情況：
第一種：比較簡單，例如1,2,3,4，走到4的時候，因為一直上漲，自然maxProfit增加
第二種：已經是第二波更賺的了，例如[3,4,5,2,1,7]，走到7的時候，原先maxProfit是5-3，現在要變成7-1，1是不斷更新的minPrice

更新minPrice時間點，當遇到一個比之前更低的價格。

 /**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    
    maxEarn = 0
    minPrice = prices[0]
    
    for (let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i-1]) {
            maxEarn = Math.max(maxEarn, prices[i]-minPrice)
        } else {
            minPrice = Math.min(prices[i], minPrice)
        }
    }
    return maxEarn
    
};

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

### 575 Distribute Candies
> Alice has n candies, where the ith candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor.
> \
> The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor's advice.
> \
> Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n / 2 of them.
> \
> Example 2:
> Input: candyType = [1,1,2,3]
> Output: 2
> Explanation: Alice can only eat 4 / 2 = 2 candies. Whether she eats types [1,2], [1,3], or [2,3], she still can only eat 2 different types.

// special condition: [1, 2, 1, 3]
// This is a math problem
var distributeCandies = function(candyType) {
    let diffTypes = new Set(candyType)
    return Math.min(diffTypes.size, candyType.length/2)
};

Time complexity: O(N)
Space complexity: O(N), since the set size is the same as the input n

#### Helpful Method: Set
create: ```new Set(array)```

### > Method: Boyer-Moore Voting Algorithm
> A A A C C B B C C C B C C
> Idea: use pairing to cancel two different voting, in the end, which number left would be the majority one.
>
> sudo-code:
> num = 'A'
> count = 0
>
> Start from the beginning, if meet 'A', count+1, else, count-1 until count is 0, replace num as the new number that's meet
>
> 'A':1, 'A':2, 'A':3, 'A':2(meet 'C'), ...

### Q229 Majority Element II
> Given an integer array of size n, find all elements that appear **more than** ⌊ n/3 ⌋ times.
>
> Constraints: linear time and in O(1) space(thus we cannot use map to store each number's count)
>
> Example 1:
> Input: nums = [3,2,3]
> Output: [3]
>
> Example 2:
> Input: nums = [1]
> Output: [1]
>
> Example 3:
> Input: nums = [1,2]
> Output: [1,2]

Since in a n-length array, only maximum two numbers would appear more than ⌊ n/3 ⌋ times, we only have to use two variables to record the two candidates.

/**
var majorityElement = function(nums) {
    if (nums.length === 0) return []
    
    let count1 = 0, count2 = 0
    let num1, num2
    
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === num1) count1++
        else if (nums[i] === num2) count2++
        else if (count1 === 0) {
            num1 = nums[i]
            count1++
        } else if (count2 === 0) {
            num2 = nums[i]
            count2++
        } else {
            count1--
            count2--
        }
    }
    
    count1 = 0
    count2 = 0
    
    //check the total count for the top2 numbers
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === num1) count1++
        if (nums[i] === num2) count2++
    }
    
    let ans = []
    if (count1 > Math.floor(nums.length/3)) ans.push(num1)
    if (count2 > Math.floor(nums.length/3)) ans.push(num2)
    
    return ans
};

---
### > Method: Iterate from beginning, then from end

### 821. Shortest Distance to a Character
> Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.
> \
> Example 1:
> Input: S = "loveleetcode", C = 'e'
> Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

var shortestToChar = function(S, C) {
    let ans = []
  
    let prevC = -10000   
    for (let i = 0; i < S.length; i++) {
      if (S[i] === C) {
          prevC = i
      }
      ans.push(i-prevC)
    }

    prevC = 10000
    for (let i = S.length-1; i >= 0; i--) {
      if (S[i] === C) {
          prevC = i
      }
      ans[i] = Math.min(ans[i], prevC-i)
    }
    
    return ans
};

### 238. Product of Array Except Self
> Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
>
> Constraint:
> 1. solve it without division
> 2. Time complexity: O(n)
> 3. Space complexity: O(1) (The output array does not count as extra space)
>
> Example:
> Input: [1,2,3,4]
> Output: [24,12,8,6]

var productExceptSelf = function(nums) {
    let output = []
    let prev_product = 1
    
    for (let i = 0; i < nums.length; i++) {
        output.push(prev_product)
        prev_product *= nums[i]
    }
    
    prev_product = 1
    
    for (let i = nums.length - 1; i >= 0; i--) {
        output[i] *= prev_product
        prev_product *= nums[i]
    }
    
    return output
};

## Stack


In JS, we can use array with ```push``` and ```pop``` method to simulate stack.

### 20. Valid Parentheses
> Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
>
> An input string is valid if:
> 1. Open brackets must be closed by the same type of brackets.
> 2. Open brackets must be closed in the correct order.
>
> s consists of parentheses only '()[]{}'.
>
> Example 1:
> Input: s = "()"
> Output: true
>
> Example 2:
> Input: s = "()[]{}"
> Output: true
>
> Example 3:
> Input: s = "(]"
> Output: false
>
> Example 4:
> Input: s = "([)]"
> Output: false
>
> Example 5:
> Input: s = "{[]}"
> Output: true

Original code:

var isValid = function(s) {
    let stack_no_match = []
    
    for (let i = 0; i < s.length; i++) {
        if (stack_no_match.length === 0) {
            stack_no_match.push(s[i])
        } else {
            let last = stack_no_match.pop()
            if (!((s[i] === '}' && last === '{') || (s[i] === ')' && last === '(') || (s[i] === ']' && last === '[')))  {
                stack_no_match.push(last)
                stack_no_match.push(s[i])
            }
        }
    }
    
    if (stack_no_match.length === 0) return true
    else return false
    
    
};

optimized code:

## Queue

## Linked List

## Hash Table

### Q1 Two Sum

#### Helpful JS DS: Map

create: ```new Map()```
set: ```map.set(key, value)```
find key: ```map.has(key)```
get value: ```map.get(key)```

## Tree