
# 选自行车

## 计划

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

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

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

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

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

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

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

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

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

## 网上筛选

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

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

喜德盛的传奇系列：

![逐日600](chasing600.png)

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

## 实地选车

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

## 后续

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


pick_first_cycle.md


# RW 实践

## 背景
首先介绍一下我们团队的情况，我司数据中台团队成立于2022年初，最开始聚焦于离线数仓和报表，人员配置在6个人左右的小团队。技术架构比较复杂，组件相对来说比较臃肿，一次报表刷新的时间大概在12小时左右，在我们数据量并不是特别大的情况下效率并不高。2023年年末团队经历一波换血过后，我们就开始着手整个数据中台的架构治理。当然其他细节我就不在这儿过多介绍，比较新颖的是，为了支持风控实时计算的需求，我们引入了比较新的RisingWave作为我们实时计算的补充，同Flink一起支撑整个团队的实时流水线。

## RisingWave
RisingWave 是一个分布式架构的 SQL 流式数据库，能简单、高效、可靠地处理流数据。RisingWave 提供增量更新、一致性的物化视图——这是一种持久的数据结构，承载了流处理的结果。RisingWave 让开发人员能够通过级联物化视图来表达复杂的流处理逻辑，从而大大降低了构建流处理应用的难度。此外，它还允许用户直接在系统内持久化数据，而无需将结果传送到外部数据库进行存储和查询。

## 整体架构
![dp arch](https://sheltonsuen.github.io/dp_arch.jpg) 

## 案例

### 1. 车辆在途打标
我司有一个项目需要对所有平台注册的车辆进行标记，简单来讲就是需要经过计算，然后标记车辆是否在途。这个需求相对来说比较简单，只需要查询平台跟这个车相关的订单，关联最新的位置，如果有就是在途，并且有最新位置，没有则非在途。所以对于这个案例，我们全程都是在RisingWave计算，首先通过 RW CDC 将车辆，打卡等相关表 CDC 到 RW, 然后再通过join关联车辆最新的位置（可以利用窗口函数等计算）并且标记是否在途。join后的是 Materialized View ，为了方便查询，我们又将最终的结果sink 到了 mysql 提供给业务系统查询。

#### 需要注意的是
* RW CDC 以及 最后结果 Sink to mysql 都需要映射，RW 采用psql 而我们业务系统都是mysql， 所以中途的映射算是一个比较繁琐的事情
* Timestamp & Datetime 在映射后的时区问题，需要谨慎处理，必要的时候需要单独转换
* 没有自动化部署！！！ 由于采用SQL方式，所以我们只能手动执行，曾经仓试过集成liquibase等都失败告终，最后不得不统一手动执行
* decouple sink 如果经常遇到跑着跑着 RW 就crash 了，并且整个集群都在 crash 那应该是下游存在瓶颈导致无法checkpoint

### 2. 订单打标
这个需求类似于第一个案例，不同的是这个需求很复杂，设计的场景比较多。如果还是通过SQL来做就不是很合适，也不方便测试。好在RW提供了UDF，并且支持多种方式的UDF部署方式，可以嵌入也可以远程部署，这给与了我们很大的扩展空间。综合考虑，我们采用 java UDF 并且部署为remote service。整个流水线就变了为了 RW CDC 将订单信息通过到RW， RW MV 调用 remote UDF 对每一个订单进行打标，最后将结果sink到mysql 供业务系统查询。

#### 需要注意的是
* remote service 的调用并不是很稳定，1万次总有几次失败，可能是网络抖动，这个时候就需要设置失败重试，否则就会得到NULL值

## 整体使用感受
最开始接触这个还是比较抗拒的，毕竟已经有业界比较成熟的Flink 摆在哪儿，当时我们是从比较早的版本开始试用的，还是经常能遇到一些bug，好在RW团队还是比较敏捷，团队修复发布速度较快。
整体稳定性也有待提高，偶尔因为性能问题会导致整个集群崩溃，etcd也不是很好恢复。


rw_in_practice.md


# SR 实践

## 背景
首先介绍一下我们团队的情况，我司数据中台团队成立于2022年初，最开始聚焦于离线数仓和报表，人员配置在6个人左右的小团队。技术架构比较复杂，组件相对来说比较臃肿，一次报表刷新的时间大概在12小时左右，在我们数据量并不是特别大的情况下效率并不高。2023年年末团队经历一波换血过后，我们就开始着手整个数据中台的架构治理。治理包括基于SR 将 Doris和Hadoop 整合为一个数仓，然后通过Flink CDC 将所有的原表直接load到数仓。 

## StarRocks
StarRocks 是新一代极速全场景 MPP (Massively Parallel Processing) 数据库。StarRocks 的愿景是能够让用户的数据分析变得更加简单和敏捷。用户无需经过复杂的预处理，就可以用 StarRocks 来支持多种数据分析场景的极速分析。StarRocks 架构简洁，采用了全面向量化引擎，并配备全新设计的 CBO (Cost Based Optimizer) 优化器，查询速度（尤其是多表关联查询）远超同类产品。StarRocks 能很好地支持实时数据分析，并能实现对实时更新数据的高效查询。StarRocks 还支持现代化物化视图，进一步加速查询。使用 StarRocks，用户可以灵活构建包括大宽表、星型模型、雪花模型在内的各类模型。

## 整体架构
![dp arch](https://sheltonsuen.github.io/dp_arch.jpg) 

## 案例

### 1. DAU 计算
我们直接通过Flink CDC 3.0 的 Pipeline 将需要的表实时导入到 StarRocks 的 ods 层，然后再通过构建异步物化视图，实时计算各种DAU。

#### 需要注意的是
* StarRocks对于性能的消耗还是显而易见的，我们最初就因为机器性能原因，经常在所有物化视图刷新的时候导致整个集群崩溃。
* 设置监控和告警，以防物化视图失败时没有感知， 包括Flink CDC 3.0 的监控和告警，我们曾经多次遇到上游数据结构改变导致Flink CDC 断掉。

## 整体使用感受
StarRocks 作为一个MPP引擎，在我们的架构治理中起到了关键作用，效果也是显而易见的，优化过后我们的数据刷新时间从原来的12小时缩短为20分钟，由于我们没有增量的必要，
每次直接依赖于StarRocks的计算能力，暴力刷新所有的表。并且新版的StarRocks 支持存算分离，结合云厂商的廉价存储和SSD缓存，稳定性得到进一步提升。


sr_mv_in_practice.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);`
