
# 选自行车

## 计划

想买车这个想法由来已久，之前是一直骑摩拜，真的是磨屁股，还骑不快，想着是时候升级一下装备了，然后最近也打算来一个半程川藏线然后转到丽江。

现在自行车品牌真的是五花八门的，不过当你仔细筛选一下的话其实就几个比较靠谱的：

1. GIANT(捷安特)
2. 美利达
3. 喜德盛

欧美不考虑（太贵），永久/凤凰不考虑（太老）

最后在这三个品牌的里面筛选。

大概查了一下，现在自行车主要分： 山地车，公路车，旅行车等

山地车 -- 轮胎比较宽抓地力比较长，带减震（前叉锁死）。适合混合路面/山地路面
公路车 -- 适合路况较好的公路行驶。
旅行车 -- 一定程度考虑长途骑行的舒适度。

然后 车子还分车架成分，烧钱的碳纤维和普通的铝合金

考虑到自己平时比较作，然后又要骑路面情况比较复杂的川藏线，资金还有限。所以果断定位在了 山地车 -- 铝合金车架。

## 网上筛选

大概定位好车子后我就开始疯狂的筛选备选款式了。这些自行车厂商的网站一般都会有所有车子的详细资料有些还可以在线对比。

最后初步赛选出来了两款比较合理的车：

喜德盛的传奇系列：

![逐日600](chasing600.png)

捷安特的 ATX 系列：
![ATX860](atx860.jpeg)

## 实地选车

实地选车大概经理了一周左右吧，刚开始就一直想去看喜德盛的车但是喜德盛的专卖店 9 点就关门了，然后我从公司带专卖店还得有一个多小时的车程（我还想着共享单车去），直接到时我又一次去了过后只能眼巴巴的盯着玻璃后面的自行车。后面选择了先去看捷安特的，我选择了一个离我住的地方没有多远的专卖店。到店后店主正在组装一台自行车，看着挺忙的，等了一会。师傅很热情的给我介绍了基本所有的车型，但我当时没有问我网上选好的，所以我第二天又过来了，直接问了 ATX777 然后他给我说 ATX860 是一样的听他详细给我介绍了一帆过后都打算买了，但是这个专卖店没有 M 号只有 S 号，很尴尬，本来想让店主去定的，但是他直接给我来了一句你骑 S 号也行。。。怎么能随便，所以果断换店了。

## 后续

后面果断买了捷安特的 XTC，估计是后面没有时间来更新这篇文章了。


pick_first_cycle.md


# Two Sum

## Descrption

[original description](https://leetcode.com/problems/two-sum/)

## Solutions

### Brute Force

```javascript
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {       // check every possible case
        return [i, j];
      }
    }
  }
  return [-1, -1] // will never touch
};
```

- Time Complexity: O(n^2)
- Space Complexity: O(1)

### Cache Diff by Map

```javascript
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  const cache = {}
  for (let i = 0; i < nums.length; i++) {
    const cachedIndex = cache[target - nums[i]];
    if (cachedIndex !== undefined) {              // found cached diff, return directly
      return [cachedIndex, i];        
    }

    cache[nums[i]] = i;                           // otherwise cache it for later use
  }

  return [-1, -1];
};
```

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



0001_two_sum.md


# Add Two Numbers

## Description

[original description](https://leetcode.com/problems/add-two-numbers/)

## Solutions

### Clear Version

simulate the calculation

```javascript
function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  const head = new ListNode();
  let current = head;
  let carry = 0;

  while (l1 && l2) {
    const sum = l1.val + l2.val + carry;
    const val = sum % 10;
    carry = Math.floor(sum / 10);

    current.next = new ListNode(val);
    current = current.next;
    l1 = l1.next;
    l2 = l2.next;
  }

  while (l1) {
    const sum = l1.val + carry;
    const val = sum % 10;
    carry = Math.floor(sum / 10);

    current.next = new ListNode(val);
    current = current.next;
    l1 = l1.next;
  }

  while (l2) {
    const sum = l2.val + carry;
    const val = sum % 10;
    carry = Math.floor(sum / 10);

    current.next = new ListNode(val);
    current = current.next;
    l2 = l2.next;
  }

  if (carry) {
    current.next = new ListNode(carry);
  }

  return head.next;
};
```

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

### Merge Calculation

```javascript
function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  const head = new ListNode();
  let current = head;
  let carry = 0;

  while (l1 || l2) {
    const sum = (l1?.val ?? 0) + (l2?.val ?? 0) + carry;    // the new syntax
    const val = sum % 10;
    carry = Math.floor(sum / 10);

    current.next = new ListNode(val);
    current = current.next;
    l1 = l1?.next;
    l2 = l2?.next;
  }

  if (carry) {
    current.next = new ListNode(carry);
  }

  return head.next;
};
```

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


0002_add_two_numbers.md


# Longest Substring Without Repeating Characters

## Description

[original description](https://leetcode.com/problems/longest-substring-without-repeating-characters/)

## Solutions

### First Idea

one scaning

```javascript
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let result = 0;

  let cache = {};
  let lengthCount = 0;
  let start = 0;

  for (let i = 0; i < s.length; i++) {
    const ch = s.charAt(i);
    const index = cache[ch];

    if (index != undefined) {
      for (let j = start; j <= index; j++) {
        delete cache[s.charAt(j)];
      }

      lengthCount = lengthCount - (index - start + 1);
      start = index + 1;
    }

    lengthCount++;
    cache[ch] = i;
    result = result < lengthCount ? lengthCount : result;
  }

  return result;
};
```

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

### Sliding Window

My first solution for this problem is similar to Sliding Window, check [doc](https://www.code-recipe.com/post/longest-substring-without-repeating-characters) for details.

```javascript
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let max = 0;
  let cachedKeys = {};

  let start = 0; // the sliding window
  let end = 0;

  for (; end < s.length; end++) {
    const cachedIndex = cachedKeys[s[end]];

    if (cachedIndex !== undefined) {
      const len = end - start;
      max = max < len ? len : max;

      for (let j = start; j <= cachedIndex; j++) {
        delete cachedKeys[s.charAt(j)];
      }

      start = cachedIndex + 1;
    }

    cachedKeys[s.charAt(end)] = end;
  }

  return max < end - start ? end - start : max;
};
```

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


0003_longest_substring.md


# Median of Two Sorted Arrays

## Descriptions

[original description](https://leetcode.com/problems/median-of-two-sorted-arrays/)

## Solutions

### First Idea

```javascript
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  const len = nums1.length + nums2.length;
  const max = len % 2 ? (len - 1) / 2 : len / 2;
  let prev = null;
  let pprev = null;

  let cur1 = 0;
  let cur2 = 0;

  for (let i = 0; i <= max; i++) {
    pprev = prev;
    prev =
      (nums1[cur1] ?? Number.MAX_VALUE) < (nums2[cur2] ?? Number.MAX_VALUE)
        ? nums1[cur1++]
        : nums2[cur2++];
  }

  return len % 2 ? prev : (pprev + prev) / 2;
};
```

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


0004_median_of_two_sorted_arrays.md


# Longest Palindromic Substring

## Description

[doc](https://github.com/afatcoder/LeetcodeTop/blob/master/bytedance/frontend.md)

## Solutions

### First Idea

```javascript
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  let result = []

  for (let i = 0; i < s.length; i++) {
    let j = i
    while ((j = s.indexOf(s.charAt(i), j + 1)) > 0) {
      let curR = j

      if (j <= i) {
        continue
      }

      let curL = i

      while (curL++ < curR--) {
        if (s.charAt(curL) !== s.charAt(curR)) {
          break
        }
      }

      if (curL >= curR) {
        result.push(s.substring(i, j + 1))
      }
    }
  }

  return result.reduce(
    (maxStr, cur) => (maxStr.length < cur.length ? cur : maxStr),
    s.charAt(0)
  )
}
```

- Time Complexity: O(n^3)
- Space Complexity: O(n \* n)

### Refined Version

```javascript
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  if (s.length < 2) {
    return s[0]
  }

  let start = 0
  let end = 0

  function expendForPalindromic(i, j) {
    while (i >= 0 && j < s.length && s.charAt(i) === s.charAt(j)) {
      i--
      j++
    }

    if (end - start < j - i - 1) {
      start = i + 1
      end = j
    }
  }

  for (let i = 0; i < s.length; i++) {
    expendForPalindromic(i, i)
    expendForPalindromic(i, i + 1)
  }

  return s.substring(start, end)
}
```

- Time Complexity: O(n^2)
- Space Complexity: O(1)


0005_longest_palindromic_substring.md


# Remove Nth Node From End of List

## Description

[doc](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)

## Solutions

### First Idea

```javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  let cur = head
  let count = 0

  while (cur) {
    cur = cur.next
    count++
  }

  let target = count - n
  if (target === 0) {
    return head.next
  }

  cur = head
  for (let i = 1; i < target; i++) {
    cur = cur.next
  }

  cur.next = cur.next.next

  return head
}
```

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


0019_remove_Nth_node_from_end_of_list.md


# Valid Parentheses

## Description

[doc](https://leetcode.com/problems/valid-parentheses/)

## Solutions

### First Idea

```javascript
const validCloses = { ')': '(', '}': '{', ']': '[' }
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  let stack = []

  for (let i = 0; i < s.length; i++) {
    const ch = s.charAt(i)
    const opening = validCloses[ch]

    if (!opening) {
      stack.push(ch)
      continue
    }

    const top = stack.pop()
    if (top !== opening) {
      return false
    }
  }

  return stack.length === 0
}
```

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


0020._valid_parentheses.md


# Merge Two Sorted Lists

## Description

[doc](https://leetcode.com/problems/merge-two-sorted-lists/)

## Solutions

### First Idea

```javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  if (!list1 || !list2) {
    return list1 || list2
  }

  let cur = (head = {})
  while (list1 && list2) {
    if (list1.val < list2.val) {
      cur.next = list1
      list1 = list1.next
    } else {
      cur.next = list2
      list2 = list2.next
    }

    cur = cur.next
  }

  cur.next = list1 ? list1 : list2
  return head.next
}
```

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


0021_merge_two_sorted_lists.md


# Next Permutation

## Description

[doc](https://leetcode.com/problems/next-permutation/)

## Solutions

### First Idea

```javascript
function sortSubArrayInPlace(start, nums) {
  for (let i = start; i < nums.length; i++) {
    let minIdx = i
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[minIdx]) {
        minIdx = j
      }
    }
    if (minIdx !== i) {
      let tmp = nums[minIdx]
      nums[minIdx] = nums[i]
      nums[i] = tmp
    }
  }
}

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function (nums) {
  let idx = nums.length - 1
  while (idx > 0) {
    if (nums[idx - 1] < nums[idx]) {
      break
    }

    idx--
  }

  const prev = idx - 1
  if (prev < 0) {
    return sortSubArrayInPlace(idx, nums)
  }

  sortSubArrayInPlace(idx, nums)
  while (idx < nums.length) {
    if (nums[idx] > nums[prev]) {
      break
    }
    idx++
  }

  const tmp = nums[idx]
  nums[idx] = nums[prev]
  nums[prev] = tmp
  return nums
}
```


0031_next_permutation.md


# Search Insert Position

## Descripition

## Solutions

### First Idea

```javascript
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  let low = 0
  let high = nums.length - 1

  // only ->> [low v high] [low v, v high] ->> [low, high]
  while (low < high) {
    const middle = low + Math.floor((high - low) / 2)
    if (nums[middle] === target) {
      return middle
    }

    nums[middle] < target ? (low = middle + 1) : (high = middle - 1)
  }

  return target > nums[low] ? low + 1 : low
}
```

-- Time Complexity: O(logn)
-- Space Complexity: O(1)


0035_search_insert_position.md


# Permutations

## Description

[doc](https://leetcode.com/problems/permutations/)

## Solutions

### First idea

```javascript
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  if (nums.length === 1) {
    return [nums]
  }

  let result = []
  for (let i = 0; i < nums.length; i++) {
    result = [
      ...result,
      ...permute([...nums.slice(0, i), ...nums.slice(i + 1)]).map((v) => [
        nums[i],
        ...v,
      ]),
    ]
  }

  return result
}
```


0046_permutations.md


# Maximum Subarray

## Description

[doc](https://leetcode.com/problems/maximum-subarray/)

## Solutions

### Dynamic Programing

```javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let sum = (max = nums[0])

  for (let i = 1; i < nums.length; i++) {
    const sumWithCurrent = sum + nums[i]

    sum = sumWithCurrent < nums[i] ? nums[i] : sumWithCurrent
    max = sum > max ? sum : max
  }

  return max
}
```


0053_maximum_subarray.md


# Unique Paths

## Description

[doc](https://leetcode.com/problems/unique-paths/)

## Solutions

### [Time Exceeded] First Idea

```javascript
const DIRS = [
  [1, 0],
  [0, 1],
]

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  const [endX, endY] = [n - 1, m - 1]
  let queue = [[0, 0]]
  let pathCount = 0

  while (queue.length) {
    const [x, y] = queue.shift()

    if (x === endX && y === endY) {
      pathCount++
      continue
    }

    DIRS.forEach(([_x, _y]) => {
      const newX = x + _x
      const newY = y + _y

      if (newX > endX || newY > endY) {
        return
      }

      queue.push([newX, newY])
    })
  }

  return pathCount
}
```

- Time Complexity: O(?)
- Space Complexty: O(1)

### [Time Exceeded] Recursive Version

```javascript
const DIRS = [
  [-1, 0],
  [0, -1],
]

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  if (!(m - 1) && !(n - 1)) {
    return 1
  }

  return DIRS.reduce((acc, [_x, _y]) => {
    const newX = n + _x
    const newY = m + _y

    if (!newX || !newY) {
      return acc
    }

    return acc + uniquePaths(newY, newX)
  }, 0)
}
```

### DP

```javascript
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  let matrics = Array(n)
    .fill(0)
    .map(() => Array(m).fill(0))

  for (let y = 0; y < m; y++) {
    for (let x = 0; x < n; x++) {
      if (!x && !y) {
        matrics[x][y] = 1
        continue
      }

      const left = matrics[x - 1]?.[y] ?? 0
      const top = matrics[x]?.[y - 1] ?? 0
      matrics[x][y] = left + top
    }
  }

  return matrics[n - 1][m - 1]
}
```

- Time Complexity: O(m \* n)
- Space Complexity: O(m \* n)


0062_unique_paths.md


# Climbing Stairs

## Description

[doc](https://leetcode.com/problems/climbing-stairs/)

## Solutions

### Recursive Version

```javascript
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  if (n < 3) {
    return n
  }

  return climbStairs(n - 1) + climbStairs(n - 2)
}
```

### DP

```javascript
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  if (n < 3) {
    return n
  }

  let [prev, cur] = [1, 2]

  for (let i = 3; i <= n; i++) {
    let next = prev + cur
    prev = cur
    cur = next
  }

  return cur
}
```

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


0070_climbing_stairs.md


# Merge Two Sorted Array

## Description

[ref](https://leetcode.com/problems/merge-sorted-array/)

## Solutions

### Recursive Version

```javascript
/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function (nums1, m, nums2, n) {
  let idx = m + n - 1
  let idx1 = m - 1
  let idx2 = n - 1

  while (idx1 >= 0 && idx2 >= 0) {
    nums1[idx--] = nums1[idx1] > nums2[idx2] ? nums1[idx1--] : nums2[idx2--]
  }

  while (idx2 >= 0) {
    nums1[idx--] = nums2[idx2--]
  }
}
```

- Time Complexity: O(m + n)
- Space Complexity: O(m + n)


0088_merge_two_sorted_arrary.md


# Binary Tree Inorder Traversal

## Description

[doc](https://leetcode.com/problems/binary-tree-inorder-traversal/)

## Solutions

### First Idea

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
  if (!root) {
    return []
  }

  if (!root.left && !root.right) {
    return [root.val]
  }

  return [
    ...inorderTraversal(root.left),
    root.val,
    ...inorderTraversal(root.right),
  ]
}
```

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

### Refined one

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
  if (!root) {
    return []
  }

  return [
    ...inorderTraversal(root.left),
    root.val,
    ...inorderTraversal(root.right),
  ]
}
```

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


0094_binary_tree_inorder_traversal.md


# Binary Tree Level Order Traversal

## Description

[doc](https://leetcode.com/problems/binary-tree-level-order-traversal/)

## Solutions

### First Idea

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  if (!root) {
    return []
  }

  let result = []
  let curLevel = []

  let curQueue = [root]
  let nextQueue = []

  while (curQueue.length) {
    const cur = curQueue.shift()

    curLevel.push(cur.val)
    cur.left && nextQueue.push(cur.left)
    cur.right && nextQueue.push(cur.right)

    if (!curQueue.length) {
      curQueue = nextQueue
      nextQueue = []
      result.push(curLevel)
      curLevel = []
    }
  }

  return result
}
```

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


0102_binary_tree_level_order_traversal.md


# Maximum Depth of Binary Tree

## Description

[doc](https://leetcode.com/problems/maximum-depth-of-binary-tree/)

## Solutions

### First Idea

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
  if (root === null) {
    return 0
  }

  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}
```

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


0104_maximum_depth_of_binary_tree.md


# Path Sum

## Description

[doc](https://leetcode.com/problems/path-sum/)

## Solutions

### Recursive Version

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function (root, targetSum) {
  if (!root) {
    return false
  }

  const leftTarget = targetSum - root.val
  if (!leftTarget && !root.left && !root.right) {
    return true
  }

  return hasPathSum(root.left, leftTarget) || hasPathSum(root.right, leftTarget)
}

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

### DFS

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function (root, targetSum) {
  if (!root) {
    return false
  }

  const queue = [root]
  while (queue.length) {
    const cur = queue.shift()

    const left = targetSum - cur.val
    if (!left && !cur.left && !cur.right) {
      return true
    }

    if (cur.left) {
      cur.left.val += cur.val // try to make it immutable in prod
      queue.push(cur.left)
    }

    if (cur.right) {
      cur.right.val += cur.val
      queue.push(cur.right)
    }
  }

  return false
}

- Time Complexity: O(n)
- Space Complexity: O(log(n)) ? maybe
```


0112_path_sum.md


# Path Sum II

## Description

[doc](https://leetcode.com/problems/path-sum-ii/)

## Solutions

### First Idea

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}
 */
var pathSum = function (root, targetSum) {
  if (root === null) {
    return []
  }

  const leftVal = targetSum - root.val
  if (root.left === null && root.right === null) {
    return leftVal ? [] : [[root.val]]
  }

  const left = pathSum(root.left, leftVal)
  const right = pathSum(root.right, leftVal)

  return [...left, ...right].map((v) => [root.val, ...v])
}
```

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

### BFS

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}
 */
var pathSum = function (root, targetSum) {
  if (root === null) {
    return []
  }

  root.vals = [root.val]
  let queue = [root]
  let result = []

  while (queue.length) {
    const cur = queue.shift()

    if (cur.left === null && cur.right === null && cur.val === targetSum) {
      result.push(cur.vals)
      continue
    }

    if (cur.left) {
      cur.left.vals = [...cur.vals, cur.left.val]
      cur.left.val += cur.val
      queue.push(cur.left)
    }

    if (cur.right) {
      cur.right.vals = [...cur.vals, cur.right.val]
      cur.right.val += cur.val
      queue.push(cur.right)
    }
  }

  return result
}
```

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


0113_path_sum_II.md


# Populating Next Right Pointers in Each Node

## Description

[doc](https://leetcode.com/problems/populating-next-right-pointers-in-each-node/)

## Solutions

### First Idea

```javascript
/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function (root) {
  if (!root) {
    return root
  }

  let queue = [root]
  let nextQueue = []
  let prev = null

  while (queue.length) {
    const tail = queue.shift()
    tail.next = prev
    prev = tail

    tail.right && nextQueue.push(tail.right)
    tail.left && nextQueue.push(tail.left)

    if (queue.length === 0) {
      queue = nextQueue
      nextQueue = []
      prev = null
    }
  }

  return root
}
```


0116_populating_next_right_pointers_in_each_node.md


# Best Time to Buy and Sell Stock

## Dscription

[doc](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)

## Solutions

### Fist Idea

```javascript
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let min = 0
  let maxProfit = 0

  for (let i = 1; i < prices.length; i++) {
    let profit = prices[i] - prices[min]
    maxProfit = Math.max(maxProfit, profit)
    min = profit < 0 ? i : min
  }

  return maxProfit
}
```


0121_best_time_to_buy_and_sell_stock.md


# Sum Root to Leaf Numbers

## Description

[ref](https://leetcode.com/problems/sum-root-to-leaf-numbers/)

## Solution

### Recursive Solution

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function (root) {
  function sum(node) {
    if (!node) {
      return []
    }

    if (!node.left && !node.right) {
      return [`${node.val}`]
    }

    return [...sum(node.left), ...sum(node.right)].map((v) => node.val + v)
  }

  return sum(root).reduce((acc, cur) => acc + Number.parseInt(cur), 0)
}
```


0129_sum_root_to_leaf_numbers.md


# LRU Cache

## Description

[doc](https://leetcode.com/problems/lru-cache/)

## Solutions

### First Idea

```javascript
/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity

  this.LRUCache = new Map()
  this.low = 0
  this.high = 0

  this.cache = new Map()
}

LRUCache.prototype.getLRUKey = function () {
  while (!this.LRUCache.has(this.low) && this.low < this.high) {
    this.low++
  }

  return this.LRUCache.get(this.low)
}

LRUCache.prototype.remove = function (key) {
  const cur = this.cache.get(key)
  if (cur) {
    this.cache.delete(key)
    this.LRUCache.delete(cur.cacheKey)
  }

  return cur
}

LRUCache.prototype.add = function (key, value) {
  this.cache.set(key, { cacheKey: this.high, value })
  this.LRUCache.set(this.high++, key)
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (!this.cache.has(key)) {
    return -1
  }

  const prev = this.remove(key)
  this.add(key, prev.value)
  return prev.value
}

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  if (this.cache.has(key)) {
    this.remove(key)
  }

  if (this.cache.size >= this.capacity) {
    const LRUKey = this.getLRUKey()
    this.remove(LRUKey)
  }

  this.add(key, value)
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */
```


0146_LRU_cache.md


# Intersection of Two Linked Lists

## Description

[doc](https://leetcode.com/problems/intersection-of-two-linked-lists/)

## Solutions

### First Idea

```javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
  let curA = headA

  while (curA) {
    let curB = headB

    while (curB) {
      if (Object.is(curA, curB)) {
        return curA
      }

      curB = curB.next
    }

    curA = curA.next
  }

  return null
}
```

- Time Complexity: O(n^2)
- Space Complexity: O(1)

### Hash Version

```javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
  const nodesOfB = new WeakSet()
  let cur = headB

  while (cur) {
    nodesOfB.add(cur)
    cur = cur.next
  }

  cur = headA
  while (cur) {
    if (nodesOfB.has(cur)) {
      return cur
    }

    cur = cur.next
  }

  return null
}
```

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


0160_intersection_of_two_linked_lists.md


# Compare Version Numbers

## Description

[doc](https://leetcode.com/problems/compare-version-numbers/)

## Solutions

### First Idea

```javascript
const trimZero = (acc, cur) => (!acc.length && cur === 0 ? acc : [cur, ...acc])
const toVersions = (v) =>
  v
    .split('.')
    .map((v) => parseInt(v))
    .reduceRight(trimZero, [])

const compare = (a, b) => (a === b ? 0 : a > b ? 1 : -1)

/**
 * @param {string} version1
 * @param {string} version2
 * @return {number}
 */
var compareVersion = function (version1, version2) {
  const vers1 = toVersions(version1)
  const vers2 = toVersions(version2)
  const min = vers1.length < vers2.length ? vers1.length : vers2.length

  for (let i = 0; i < min; i++) {
    const v1 = vers1[i]
    const v2 = vers2[i]

    if (v1 !== v2) {
      return compare(v1, v2)
    }
  }

  return compare(vers1.length, vers2.length)
}
```

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


0165_compare_version_numbers.md


# Two Sum II - Input Array Is Sorted

## Description

[doc](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/)

## Solutions

### First Idea

```javascript
/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (numbers, target) {
  let low = 0
  let high = numbers.length - 1

  while (low < high) {
    const sum = numbers[low] + numbers[high]

    if (sum === target) {
      return [low + 1, high + 1]
    }

    sum < target ? low++ : high--
  }

  return -1
}
```

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


0167_two_sum_II.md


# Rotate Array

## Description

[doc](https://leetcode.com/study-plan/algorithm/?progress=d3ejkfm)

## Solutions

### First Idea

```javascript
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function (nums, k) {
  const rotate = k % nums.length

  const deleted = nums.splice(0, nums.length - rotate)
  nums.push(...deleted)
}
```


0189_rotate_array.md


# Reverse Linked List

## Description

[doc](https://leetcode.com/problems/reverse-linked-list/)

## Solutions

### First Idea

```javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  if (!head) {
    return head
  }

  let prev = null
  let cursor = head

  while (cursor.next) {
    let next = cursor.next
    cursor.next = prev

    prev = cursor
    cursor = next
  }

  cursor.next = prev
  return cursor
}
```

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

### Refined Version

```javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let prev = null
  let cur = head

  while (cur) {
    let next = cur.next
    cur.next = prev

    prev = cur
    cur = next
  }

  return prev
}
```

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


0206_reversed_linked_list.md


# Minimum Size Subarray Sum

## Description

[doc](https://leetcode.com/problems/minimum-size-subarray-sum/)

## Solutions

### First Idea

```javascript
/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
  let [start, end] = [0, 0]
  let sum = 0
  let minLen = Number.MAX_SAFE_INTEGER

  while (end < nums.length) {
    sum += nums[end++]

    while (start < end && sum >= target) {
      minLen = Math.min(minLen, end - start)
      sum -= nums[start++]
    }
  }

  return minLen === Number.MAX_SAFE_INTEGER ? 0 : minLen
}
```

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


0209_minimum_size_subarray_sum.md


# Kth Largest Element in an Array

## Description

[doc](https://leetcode.com/problems/kth-largest-element-in-an-array/)

## Solutions

### First idea

```javascript
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
  // should not use the sort method directly
  // since by default, sort will convert the value to string to compare between each other
  // refer to [compareFunction](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort#description)
  return nums.sort((a, b) => a - b)[nums.length - k]
}
```

- Time Complexity: O(n\*logn) if using quick sort
- Space Complexity: O(1)

### Priority Queue

```javascript
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
  const priorityQueue = []

  for (const num of nums) {
    const last = priorityQueue[k - 1]
    if (last === undefined || num > last) {
      last === undefined
        ? priorityQueue.push(num)
        : (priorityQueue[k - 1] = num)

      priorityQueue.sort((a, b) => b - a)
    }
  }

  return priorityQueue[k - 1]
}
```


TODO: add quick sort one
### Quick Sort


0215_kth_largest_element_in_an_array.md


# Invert Binary Tree

## Description

[doc](https://leetcode.com/problems/invert-binary-tree/)

## Solutions

### Recursive Version

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function (root) {
  if (!root) {
    return root
  }

  let invertedLeft = invertTree(root.right)
  root.right = invertTree(root.left)
  root.left = invertedLeft

  return root
}
```

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

### Queue Version

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function (root) {
  if (!root) {
    return root
  }

  let queue = [root]

  while (queue.length) {
    const cur = queue.shift()

    cur.left && queue.push(cur.left)
    cur.right && queue.push(cur.right)

    let left = cur.left
    cur.left = cur.right
    cur.right = left
  }

  return root
}
```

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


0226_invert_binary_tree.md


# Lowest Common Ancestor of a Binary Tree

## Descrition

[doc](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/)

## Solutions

### First Idea

```javascript
function oneOf(p, q, ref) {
  return ref.val === p.val || ref.val === q.val
}

function identical(p, q, left, right) {
  return (
    (left?.val === p.val && right?.val === q.val) ||
    (left?.val === q.val && right?.val === p.val)
  )
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
  if (!root) {
    return null
  }

  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)

  if (identical(p, q, left, right) || oneOf(p, q, root)) {
    return root
  }

  return left !== null ? left : right
}
```

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


0236_lowest_common_ancestor_of_a_binary_tree.md


# First Bad Version

## Description

[doc](https://leetcode.com/problems/first-bad-version/)

## Solutions

### First Idea

```javascript
/**
 * Definition for isBadVersion()
 *
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function (isBadVersion) {
  /**
   * @param {integer} n Total versions
   * @return {integer} The first bad version
   */
  return function (n) {
    let low = 1
    let high = n

    while (low <= high) {
      const middle = low + Math.floor((high - low) / 2)
      if (low === middle) {
        return isBadVersion(low) ? low : low + 1
      }

      isBadVersion(middle) ? (high = middle) : (low = middle)
    }

    return -1
  }
}
```

- Time Complexity: O(logn)
- Space Complexity: O(1)


0278._first_bad_version.md


# Move Zeroes

## Description

## Solutions

### First Idea

```javascript
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let zeroIdx = -1

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === 0 && zeroIdx < 0) {
      zeroIdx = i
      continue
    }

    if (nums[i] !== 0 && zeroIdx >= 0) {
      nums[zeroIdx++] = nums[i]
      nums[i] = 0
    }
  }
}
```

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

### Refined Version

```javascript
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let zeroIdx = nums.indexOf(0)
  if (zeroIdx < 0) {
    return
  }

  for (let i = zeroIdx + 1; i < nums.length; i++) {
    if (nums[i] !== 0) {
      nums[zeroIdx++] = nums[i]
      nums[i] = 0
    }
  }
}
```

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


0283_move_zeroes.md


# Longest Increasing Subsequence

## Description

[doc](https://leetcode.com/problems/longest-increasing-subsequence/)

## Solutions

### Brute Force

```javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  let maxTails = []
  let max = 0

  for (let i = 0; i < nums.length; i++) {
    let low = 0
    let high = max

    while (low < high) {
      const middle = Math.floor((low + hight) / 2)

      if (maxTails[middle] < nums[i]) {
        low = middle + 1
      } else {
        high = middle
      }
    }
  }

  return max
}
```


0300_longest_increasing_subsequence.md


# Reverse String

## Description

[doc](https://leetcode.com/problems/reverse-string/)

## Solutions

### First Idea

```javascript
/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function (s) {
  let low = 0
  let high = s.length - 1

  while (low < high) {
    const tmp = s[low]
    s[low++] = s[high]
    s[high--] = tmp
  }
}
```

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


0344_reverse_string.md


# Intersection of Two Arrays

## Description

[doc](https://leetcode.com/problems/intersection-of-two-arrays/)

## Solutions

### First Idea

```javascript
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  const nums2Set = new Set(nums2)
  return [...new Set(nums1)].filter((v) => nums2Set.has(v))
}
```

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


0349_intersection_of_two_arrays.md


# Add Strings

## Dscription

[doc](https://leetcode.com/problems/add-strings/)

## Solutions

### First Idea

```javascript
/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function (num1, num2) {
  let k = (curry = 0)

  let nums = []
  let i = num1.length
  let j = num2.length

  while (i > 0 || j > 0) {
    const sum = +(num1[--i] ?? 0) + +(num2[--j] ?? 0) + curry
    curry = Math.floor(sum / 10)
    nums[k++] = sum % 10
  }

  if (curry) {
    nums[k] = curry
  }

  return nums.reverse().join('')
}
```

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


0415_add_strings.md


# N-ary Tree Level Order Traversal

## Description

[doc](https://leetcode.com/problems/n-ary-tree-level-order-traversal/)

## Solutions

### First Idea

```javascript
/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  if (!root) {
    return []
  }

  let result = []
  let curLevel = []

  let curQueue = [root]
  let nextQueue = []

  while (curQueue.length) {
    const cur = curQueue.shift()

    curLevel.push(cur.val)
    cur.children.forEach((v) => v && nextQueue.push(v))

    if (!curQueue.length) {
      curQueue = nextQueue
      result.push(curLevel)
      curLevel = []
      nextQueue = []
    }
  }

  return result
}
```

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


0429_nary_tree_level_order_traversal.md


# Validate IP Address

## Description

[doc](https://leetcode.com/problems/validate-ip-address/)

## Solutions

### First Idea

```javascript
function isIPv4(ip) {
  const digits = ip.split('.')
  if (digits.length !== 4) {
    return false
  }

  if (digits.some((v) => v.length < 1 || (v.length > 1 && v[0] === '0'))) {
    return false
  }

  if (digits.some((v) => !/^[\d]*$/.test(v))) {
    return false
  }

  if (
    digits.map((v) => parseInt(v)).some((v) => isNaN(v) || v < 0 || v > 255)
  ) {
    return false
  }

  return true
}

function isIPv6(ip) {
  const digits = ip.split(':')
  if (digits.length !== 8) {
    return false
  }

  if (digits.some((v) => v.length < 1 || v.length > 4)) {
    return false
  }

  if (digits.some((v) => !/^[\da-fA-F]*$/.test(v))) {
    return false
  }

  if (digits.some((v) => isNaN(parseInt(v, 16)))) {
    return false
  }

  return true
}

/**
 * @param {string} queryIP
 * @return {string}
 */
var validIPAddress = function (queryIP) {
  if (isIPv4(queryIP)) {
    return 'IPv4'
  }

  if (isIPv6(queryIP)) {
    return 'IPv6'
  }

  return 'Neither'
}
```


0468_validate_IP_address.md


# Fibonacci Number

## Description

[doc](https://leetcode.com/problems/fibonacci-number/)

## Solutions

### First Idea

```javascript
/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
  if (n < 2) {
    return n
  }

  let pprev = 0
  let prev = 1
  let cur

  for (let i = 2; i <= n; i++) {
    cur = pprev + prev
    pprev = prev
    prev = cur
  }

  return cur
}
```

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

### Refined for Time

```javascript
const cached = []
/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
  if (n < 2) {
    return n
  }

  let pprev = 0
  let prev = 1

  for (let i = 2; i <= n; i++) {
    cached[i] = pprev + prev
    pprev = prev
    prev = cached[i]
  }

  return cached[n]
}
```

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


0509_fibonacci_number.md


# 01 Matrix

## Description

[doc](https://leetcode.com/problems/01-matrix/)

## Solutions

### First Idea

```javascript
const DIRS = [
  [0, 1],
  [-1, 0],
  [0, -1],
  [1, 0],
]

function searchNearestZero(mat, point) {
  const mark = Array(mat.length)
    .fill()
    .map((_, i) => Array(mat[i].length))

  let queue = [point]
  mark[point[0]][point[1]] = 0

  while (queue.length) {
    const [x, y] = queue.shift()

    if (mat[x][y] === 0) {
      return mark[x][y]
    }

    DIRS.forEach(([_x, _y]) => {
      const newX = x + _x
      const newY = y + _y

      if (mat[newX]?.[newY] == null || mark[newX][newY] != null) {
        return
      }

      mark[newX][newY] = mark[x][y] + 1
      queue.push([newX, newY])
    })
  }
}

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var updateMatrix = function (mat) {
  return mat.map((v, x) => v.map((sv, y) => (sv ? searchNearestZero(mat, [x, y]) : sv)))
}
```


0542_01_matrix.md


# Reverse Words in a String III

## Description

[doc](https://leetcode.com/problems/reverse-words-in-a-string-iii/)

## Solutions

### First Idea

```javascript
/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function (s) {
  return s
    .split(' ')
    .map((word) => word.split('').reverse().join(''))
    .join(' ')
}
```

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

### Manual way

```javascript
/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function (s) {
  let result = []
  let i = 0
  let cur = 0

  while (cur < s.length) {
    while (s.charAt(cur) !== ' ' && cur < s.length) {
      cur++
    }

    let end = s.charAt(cur) === ' ' ? cur - 1 : cur
    let rightCur = end
    while (i <= end) {
      result[i++] = s.charAt(rightCur--)
    }

    if (s.charAt(cur) === ' ') {
      result[i++] = s.charAt(cur)
    }
    cur++
  }

  return result.join('')
}
```

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


0557_reverse_words_in_a_string.md


# Permutation in String

## Description

[doc](https://leetcode.com/problems/permutation-in-string/)

## Solutions

### First Idea

```javascript
/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function (s1, s2) {
  let map = new Map()
  const reset = () => map.forEach(({ count, cur }, k) => map.set(k, { count, cur: 0 }))

  for (let i = 0; i < s1.length; i++) {
    const ch = s1.charAt(i)
    map.has(ch) ? map.set(ch, { count: map.get(ch).count + 1, cur: 0 }) : map.set(ch, { count: 1, cur: 0 })
  }

  for (let i = 0; i <= s2.length - s1.length; i++) {
    reset()
    for (let j = 0; j < s1.length; j++) {
      const ch = s2.charAt(j + i)
      if (!map.has(ch)) {
        break
      }

      const { count, cur } = map.get(ch)
      if (cur >= count) {
        break
      }

      map.set(ch, { count, cur: cur + 1 })

      if (j === s1.length - 1) {
        return true
      }
    }
  }

  return false
}
```

-- Time Complexiy: O(n^2)
-- Space Complexiy: O(n)
### Refine Performance TODO:


0567_permutation_in_string.md


# Merge Two Binary Trees

## Description

[doc](https://leetcode.com/problems/merge-two-binary-trees/)

## Solutions

### DFS

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {TreeNode}
 */
var mergeTrees = function (root1, root2) {
  if (!root1 || !root2) {
    return root1 || root2
  }

  root1.left = mergeTrees(root1.left, root2.left)
  root1.right = mergeTrees(root1.right, root2.right)

  root1.val += root2.val

  return root1
}
```


0617_merge_two_binary_trees.md


# Max Area of Island

## Description

[doc](https://leetcode.com/problems/max-area-of-island/)

## Solutions

### BFS

```javascript
const DIRS = [
  [0, 1],
  [-1, 0],
  [0, -1],
  [1, 0],
] // top, right, bottom, left

const search = (grid, i, j) => {
  let queue = [[i, j]]
  let max = 1
  grid[i][j] = 0

  while (queue.length) {
    const [x, y] = queue.shift()

    DIRS.forEach(([_x, _y]) => {
      let newX = x + _x
      let newY = y + _y
      if (grid[newX] && grid[newX][newY]) {
        grid[newX][newY] = 0
        max += 1
        queue.push([newX, newY])
      }
    })
  }

  return max
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function (grid) {
  let max = 0
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (grid[i][j]) {
        max = Math.max(search(grid, i, j), max)
      }
    }
  }

  return max
}
```

### DFS

```javascript
const DIRS = [
  [0, 1],
  [-1, 0],
  [0, -1],
  [1, 0],
] // top, right, bottom, left

const search = (grid, i, j) => {
  let stack = [[i, j]]
  grid[i][j] = 0

  let count = 1

  while (stack.length) {
    const [x, y] = stack.pop()

    DIRS.forEach(([_x, _y]) => {
      let newX = x + _x
      let newY = y + _y
      if (grid[newX] && grid[newX][newY]) {
        grid[newX][newY] = 0
        count += 1
        stack.push([newX, newY])
      }
    })
  }

  return count
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function (grid) {
  let max = 0
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (grid[i][j]) {
        max = Math.max(search(grid, i, j), max)
      }
    }
  }

  return max
}
```


0695_max_area_of_island.md


# Binary Search

## Description

[doc](https://leetcode.com/problems/binary-search/)

## Solutions

### First Idea

```javascript
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let low = 0
  let high = nums.length - 1

  while (low <= high) {
    const middle = low + Math.floor((high - low) / 2)
    const middleValue = nums[middle]

    if (middleValue === target) {
      return middle
    }

    middleValue < target ? (low = middle + 1) : (high = middle - 1)
  }

  return -1
}
```

- Time Complexity: O(logn)
- Space Complexity: O(1)


0704_binary_search.md


# Maximum Length of Repeated Subarray

## Description

[doc](https://leetcode.com/problems/maximum-length-of-repeated-subarray/)

## Solutions

### First Idea

```javascript
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findLength = function (nums1, nums2) {
  let max = 0

  for (let i = 0; i < nums1.length; i++) {
    const cur = nums1[i]

    for (let j = 0; j < nums2.length; j++) {
      const other = nums2[j]

      if (other === cur) {
        let k = 1
        while (k + i < nums1.length && k + j < nums2.length) {
          if (nums1[i + k] !== nums2[j + k]) {
            break
          }
          k++
        }
        max = Math.max(max, k)
      }
    }
  }

  return max
}
```

- Time Complexity: O(n^3)
- Space Complexity: O(1)

### TODO: we need a better solution for this


0718_maximum_length_of_repeated_subarray.md


# Flood Fill

## Description

[doc](https://leetcode.com/problems/flood-fill/)

## Solutions

### BFS

```javascript
const DIRS = [
  [0, 1],
  [1, 0],
  [0, -1],
  [-1, 0],
]

/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} newColor
 * @return {number[][]}
 */
var floodFill = function (image, sr, sc, newColor) {
  let queue = [[sr, sc]]
  let visited = Array(image.length)
    .fill()
    .map(() => [])
  const color = image[sr][sc]
  visited[sr][sc] = true
  image[sr][sc] = newColor

  while (queue.length) {
    const [x, y] = queue.shift()

    DIRS.forEach(([_x, _y]) => {
      const [newX, newY] = [x + _x, y + _y]

      if (image[newX]?.[newY] === color && !visited[newX]?.[newY]) {
        image[newX][newY] = newColor
        visited[newX][newY] = true
        queue.push([newX, newY])
      }
    })
  }

  return image
}
```

### DFS

```javascript
const DIRS = [
  [0, 1],
  [1, 0],
  [0, -1],
  [-1, 0],
]

/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} newColor
 * @return {number[][]}
 */
var floodFill = function (image, sr, sc, newColor) {
  let stack = [[sr, sc]]
  let visited = Array(image.length)
    .fill()
    .map(() => [])

  const color = image[sr][sc]
  image[sr][sc] = newColor

  while (stack.length) {
    const [x, y] = stack.pop()

    DIRS.forEach(([_x, _y]) => {
      const [newX, newY] = [x + _x, y + _y]

      if (image[newX]?.[newY] === color && !visited[newX]?.[newY]) {
        image[newX][newY] = newColor
        visited[newX][newY] = true
        stack.push([newX, newY])
      }
    })
  }

  return image
}
```


0733_flood_fill.md


# Middle of the Linked List

## Description

[doc](https://leetcode.com/problems/middle-of-the-linked-list/)

## Solutions

### First Idea

```javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function (head) {
  let count = 0
  let cur = head

  while (cur !== null) {
    count++
    cur = cur.next
  }

  let middle = Math.floor(count / 2)
  cur = head
  while (middle > 0) {
    cur = cur.next
    middle--
  }

  return cur
}
```

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

### Two Pointers

```javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function (head) {
  let slow = (fast = head)

  while (fast) {
    fast = fast.next
    if (!fast) {
      break
    }

    fast = fast.next
    slow = slow.next
  }

  return slow
}
```

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


0876_middle_of_the_linked_list.md


# Squares of a Sorted Array

## Description

## Solutions

### First Idea

```javascript
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
  let right = 0
  while (nums[right] < 0) {
    right++
  }

  for (let i = 0; i < nums.length; i++) {
    nums[i] = nums[i] ** 2
  }

  let result = Array(nums.length)
  let cur = 0
  let left = right - 1

  while (left >= 0 && right < nums.length) {
    result[cur++] = nums[left] < nums[right] ? nums[left--] : nums[right++]
  }

  while (left >= 0) {
    result[cur++] = nums[left--]
  }

  while (right < nums.length) {
    result[cur++] = nums[right++]
  }

  return result
}
```

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

## Notes

```javascript
function foo() {
  let nums = [-1, -2]
  let i = 0

  // avoid using i++ in while loop for expression since it will increase unexcepted
  while (nums[i++] < 0) {}
  return i
}
// result to 3

function foo() {
  let nums = [-1, -2]
  let i = 0

  // use this instead
  while (nums[i] < 0) {
    i++
  }
  return i
}
```


0977_squares_of_a_sorted_array.md


# Remove All Adjacent Duplicates In String

## Description

[doc](https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/)

## Solutions

### First Idea

```javascript
function indexOfDuplicated(str) {
  let prev = 0
  for (let i = 1; i < str.length; i++) {
    if (str.charAt(prev) === str.charAt(i)) {
      return prev
    }

    prev = i
  }

  return -1
}

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicates = function (s) {
  let cur = s
  let i = -1

  while ((i = indexOfDuplicated(cur)) >= 0) {
    cur = cur.replace(`${cur.charAt(i)}${cur.charAt(i)}`, '')
  }

  return cur
}
```

-- Time Complexity: O(n^2)
-- Space Complexity: O(n)

### Refined Version

```javascript
function findDuplicatedChars(start, s) {
  let prev = start
  for (let i = start + 1; i < s.length; i++) {
    if (s.charAt(prev) === s.charAt(i)) {
      return prev
    }

    prev = i
  }

  return -1
}

function findRemovalRanges(start, s) {
  let left = start
  let right = start + 1

  while (left >= 0 && right < s.length && s.charAt(left) === s.charAt(right)) {
    left--
    right++
  }

  return [left, right]
}

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicates = function (s) {
  let removals = []
  let index = 0

  while ((index = findDuplicatedChars(index, s)) >= 0) {
    removals.push(findRemovalRanges(index, s))
  }

  let result = []

  for (let i = 0; i < s.length; i++) {
    if (!removals.some(([s, e]) => i >= s && i <= e)) {
      result.push(s.charAt(i))
    }
  }

  return result.join('')
}
```


1047_remove_all_adjacent_duplicates_in_string.md


# Web Animation

Animations are a huge part of making compelling web applications and sites.

## How to implement

- CSS Transition & CSS Animation
- Web Animation API
- requestAnimationFrame

### CSS Transition & CSS Animation

#### CSS Transition

Create gradual transitions between the values of specific CSS properties.

- [Demo Link](../../../src/web/animation/demo/index.html)

- [MDN Documentation](https://developer.mozilla.org/en-US/docs/Web/CSS/CSS_Transitions/Using_CSS_transitions)

##### Concepts

CSS transitions let you decide

- which properties to animate
  by listing them explicitly

- when the animation will start
  by setting a delay (seconds)

- how long the transition will last
  by setting a duration

- how the transition will run
  by defining a timing function

###### Choose properties to animate

Specifies the name or names of the CSS properties to which transitions should be applied.

- Using `transition-property`

```css
.swa-flight {
  transition-property: margin-left, margin-bottom;
}
```

- Using `transition` as shorthand

```css
.swa-flight {
  transition: margin-left, margin-bottom;
}
```

> if just declare the property, changes to the properties occur as usual.

[List of properties can be animated](https://developer.mozilla.org/en-US/docs/Web/CSS/CSS_animated_properties)

Using CSS transform property
The transform CSS property lets you rotate, scale, skew, or translate an element. It modifies the coordinate space of the CSS visual formatting model.
[MDN transform doc](https://www.quackit.com/css/functions/css_matrix_function.cfm)

###### Set the animation duration

Specifies the duration over which transitions should occur.

- Using `transition-duration`

```css
.swa-flight {
  transition-property: mrigin-left, margin-bottom;
  transition-duration: 8s, 4s;
}
```

- Using `transition` as shorthand

```css
.swa-flight {
  transition: width 8s, height 4s;
}
```

###### Set up a timing-function

Specifies a function to define how intermediate values for properties are computed.

- Using `transition-timing-function`

```css
.swa-flight {
  transition-property: margin-left, margin-bottom;
  transition-duration: 8s, 4s;
  transition-timing-function: cubic-bezier(0.51, 0.18, 0.79, 0.53), cubic-bezier(0.7, 0.21, 1, 1);
}
```

- Using `transition` as shorthand

```css
.swa-flight {
  transition: margin-left 8s cubic-bezier(0.51, 0.18, 0.79, 0.53), margin-bottom
      4s cubic-bezier(0.7, 0.21, 1, 1);
}
```

[Easing function list](https://easings.net/)

[cubic-bezier](http://cubic-bezier.com)

###### Set a deply

Defines how long to wait between the time a property is changed and the transition actually begins.

- Using `transition-delay`

```css
.swa-flight {
  transition-property: margin-left, margin-bottom;
  transition-duration: 8s, 4s;
  transition-timing-function: cubic-bezier(0.51, 0.18, 0.79, 0.53), cubic-bezier(0.7, 0.21, 1, 1);
  transition-delay: 0s, 4s;
}
```

- Using `transition` as shorthand

```css
.swa-flight {
  transition: margin-left 8s cubic-bezier(0.51, 0.18, 0.79, 0.53), margin-bottom
      4s cubic-bezier(0.7, 0.21, 1, 1) 4s;
}
```

#### CSS Animation

Animations consist of two components, a style describing the CSS animation and a set of keyframes that indicate the start and end states of the animation’s style, as well as possible intermediate waypoints.

###### Describing the animation

Below properties can be shorted as `animation` property.

- `animation-name`
- `animation-duration`
- `animation-timing-function`
- `animation-delay`
- `animation-iteration-count`
- `animation-direction`
- `animation-fill-mode`
- `animation-play-state`

###### Describing the animation's style

The `@keyframes` CSS at-rule controls the intermediate steps in a CSS animation sequence

[MDN Doc](https://developer.mozilla.org/en-US/docs/Web/CSS/@keyframes)

###### events

`animationiteration`, `animationend`, `animationstart`

[MDN Doc](https://developer.mozilla.org/en-US/docs/Web/CSS/CSS_Animations/Using_CSS_animations)

### Web Animation API

The Web Animations API lets us construct animations and control their playback with JavaScript.

#### Concepts

- Timing
- Animation
- Animation Effect

[MDN Doc](https://developer.mozilla.org/en-US/docs/Web/API/Web_Animations_API/Web_Animations_API_Concepts)

##### Timing options

Including duratiion, fill ... etc

##### Animation Effect

It's a bundle of information including at the bare minimum a set of keys and the duration they need to be animated over.

##### Animation

Use the Animation Object’s methods to play, pause, seek, and control the animation’s playback direction and speed.

```javascript
const drinking = document
  .getElementById('liquid')
  .animate([{ height: '100%' }, { height: '0' }], {
    fill: 'forwards',
    duration: 2000,
  })
drinking.pause()
```

### requestAnimationFrame

tells the browser that you wish to perform an animation and requests that the browser call a specified function to update an animation before the next repaint.

#### Syntax

`window.requestAnimationFrame(callback);`
