# [Leetcode] Remove Duplicates from Sorted Array

## Problem

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array nums = `[1,1,2]`,
Your function should return length = `2`, with the first two elements of nums being `1` and `2` respectively. It doesn’t matter what you leave beyond the new length.

## Analysis

• Keep track of the right positive to write the valid number, it is also the length of the valid numbers
• Keep track of current number
• Write it to the array only when it is different from next number
• Time: O(n)
• Extra space: O(1)

# [Leetcode] Minimum Depth of Binary Tree

## Problem

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

## Analysis

• Recursive calculate the depth of the tree
• 1 + Math.min(left-tree, right-tree)
• Need to deal with the case when left-tree or right-tree is null
• If left-tree is null, return right-tree
• If right-tree is null, return left-tree
• Time: O(n)
• As it traverses each node once

# [Leetcode] Happy Number

## Problem

Write an algorithm to determine if a number is “happy”.
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example: 19 is a happy number
• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1

## Analysis

• Since the computation is a recursive process, so that we can recursive check whether a number is a happy number
• We need to maintain a hashset to track whether a number has shown up before
• If yes, then it will not be possible to reach 1 in the future

# [Leetcode] Binary Tree Paths

## Problem

Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
`   1 /   2     3   5`
All root-to-leaf paths are:
`["1->2->5", "1->3"]`

## Analysis

• Recursive constructing the path in bottom up fashion
• For each node, get its left and right paths recursively, denote them as left and right, then the recursion is
•  (node.val + (each path in left))
• (node.val + (each path in right))
• Time: O(N) where N is the number of nodes in the tree

# [Leetcode] 3Sum Cloest

## Problem

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
`    For example, given array S = {-1 2 1 -4}, and target = 1.    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).`

## Analysis

• Brute force approach
• Enumerate the first, second, third number respectively
• Update the distance compared with the target
• Time: O(n^3)
• Space: O(1)

# [Leetcode] Merge Sorted Array

## Problem

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1and nums2 are m and n respectively.

## Analysis

• 题目是把两个sorted的数组合并成一个，这里假设数组1足够大，所以直接合并到数组1
• 记录当前要写入的index，初始值为 m+n-1
• 对两个数组从后往前扫描
• 谁比较大，谁就先写入
• 同时update index
• Time: O(m+n)
• Space: O(1)

## Analysis

• 这道题就是要把相邻两个node的指针指向反一反，反的过程当中要keep track of next node，不然这时候 node.next 变成前一个节点了
• 所以我们采用两个指针，prev 和 curr 来记录相邻的两个节点
• 反之前，先记录 curr.next, 即 tmp = curr.next
• 然后可以反了，curr.next = prev
• 然后把prev 和 curr往右移，继续去处理还没反的nodes
• prev = curr
• curr = tmp
• Time: O(n)
• Space: O(1)

# [Leetcode] Sqrt(x)

## Problem

Implement `int sqrt(int x)`.
Compute and return the square root of x.

## Analysis

• 二分搜索 [0,x]
• 若 mid*mid 等于x，或者 (mid*mid<x && (mid+1)*(mid+1)>x), 则返回mid
• 否则若mid*mid < x，则搜索 [mid+1, right]
• 否则若mid*mid > x, 则搜索 [left, mid-1]
• 注意 mid*mid 可能会溢出，要用long类型
• Time: O(log n)
• Space: O(1)

## Code

Reference
 https://leetcode.com/problems/sqrtx/

# [Leetcode] Unique Path II

## Problem

Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as `1` and `0` respectively in the grid.
For example,
There is one obstacle in the middle of a 3×3 grid as illustrated below.
`[  [0,0,0],  [0,1,0],  [0,0,0]]`
The total number of unique paths is `2`.
Note: m and n will be at most 100.

## Analysis

• Similar to Unique Path except that we need to decide whether a position has obstacle or not
• If yes, the number of ways to it is 0

# [Leetcode] Unique Path

## Problem

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?

## Analysis

• 对于每一格，有两种到达它的方式，即从左边，或者从上边
• 所以 count[i][j] = count[i-1][j] + count[i][j-1]
• Time: O(n^2)
• Space: O(n^2)
• Space可以进行优化为O(n), 因为计算count每一行的值的时候只需要上一行的信息