70. Climbing Stairs

Topic: Dynamic Programming

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

n=1时, 有一种, n=2时, 有两种方法 n=3时, 有3种方法, 等于 n=1 和 n=2的方法数相加. 以此类推

Approach1

DP: As we can see this problem can be broken into subproblems, and it contains the optimal substructure property i.e. its optimal solution can be constructed efficiently from optimal solutions of its subproblems, we can use dynamic programming to solve this problem.

One can reach $i^{th}$step in one of the two ways:

• Taking a single step from $(i-1)^{th}$step.
• Taking a step of 2 from $(i-2)^{th}$step.

So, the total number of ways to reach $i^{th}$ is equal to sum of ways of reaching $(i-1)^{th}$ step and ways of reaching $(i-2)^{th}$step.

Let $dp[i]$ denotes the number of ways to reach on $i^{th}$step:

$dp[i]=dp[i-1]+dp[i-2]$

def climbStairs(self, n: int) -> int:
    temp = []
    temp.append(1)
    temp.append(2)
    for i in range(2,n):
        temp.append(temp[i-2] + temp[i-1])
    
    return temp[n-1]

Complexity Analysis

Time complexity : $O(n)$. Single loop upto n.

Space complexity : $O(n)$. dp array of size n is used.

Approach2

In the above approach we have used dp array where $dp[i]=dp[i-1]+dp[i-2]$. It can be easily analysed that $dp[i]$is nothing but $i^{th}$fibonacci number.

$Fib(n)=Fib(n-1)+Fib(n-2)$

Now we just have to find $n^{th}$number of the fibonacci series having 1 and 2 their first and second term respectively, i.e. $Fib(1)=1$ and $Fib(2)=2$

def climbStairs(self, n):
    a, b = 1, 1
    for i in range(n):
        a, b = b, a + b
    return a

Complexity Analysis

Time complexity : $O(n)$. Single loop upto nn is required to calculate $n^{th}$fibonacci number.

Space complexity : $O(1)$. Constant space is used.

Approach3

Fibonacci Formula:

Algorithm

We can find $n^{th}$fibonacci number using this formula:

$F_n = 1/\sqrt{5}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^{n} - \left(\frac{1-\sqrt{5}}{2}\right)^{n} \right]$

For the given problem, the Fibonacci sequence is defined by $F_0 = 1$, $F_1= 1$, $F_1= 2$, $F_{n+2}= F_{n+1} + F_n$.

A standard method of trying to solve such recursion formulas is assume $F_n$of the form $F_n= a^n$.

Then, of course, $F_{n+1} = a^{n+1}$ and $F_{n+2}= a^{n+2}$ so the equation becomes $a^{n+2}= a^{n+1}+ a^n$.

If we divide the entire equation by an we arrive at $a^2= a + 1$ or the quadratic equation $a^2 - a- 1= 0$

Solving this by the quadratic formula, we get:

$a=1/\sqrt{5}\left(\left(\frac{1\pm \sqrt{5}}{2}\right)\right)$

The general solution, thus takes the form:

$F_n = A\left(\frac{1+\sqrt{5}}{2}\right)^{n} + B\left(\frac{1-\sqrt{5}}{2}\right)^{n}$

For $n=0$, we get $A + B = 1$

For $n=1$, we get $A\left(\frac{1+\sqrt{5}}{2}\right) + B\left(\frac{1-\sqrt{5}}{2}\right) = 1$

Solving the above equations, we get:

$A = \left(\frac{1+\sqrt{5}}{2\sqrt{5}}\right), B = \left(\frac{1-\sqrt{5}}{2\sqrt{5}}\right)$

Putting these values of AA and BB in the above general solution equation, we get:

$F_n = 1/\sqrt{5}\left( \left(\frac{1+\sqrt{5}}{2}\right)^{n+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+1} \right)$

def climbStairs(self, n: int) -> int:
    sqrt5=math.sqrt(5);
    fibn=pow((1+sqrt5)/2,n+1)-pow((1-sqrt5)/2,n+1);
    return int(fibn/sqrt5);

88. Merge Sorted Array

Topic: Array, Two Pointers

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.
• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

Approach1

Use sorted function:

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    """
    Do not return anything, modify nums1 in-place instead.
    """
    nums1[:] = sorted(nums1[:m] + nums2[:n])

Approach2

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    """
    Do not return anything, modify nums1 in-place instead.
    """
    while m>0 and n>0:
        if nums1[m-1] > nums2[n-1]:
            nums1[n+m-1] = nums1[m-1]
            m -= 1
        else:
            nums1[n+m-1] = nums2[n-1]
            n -= 1
    if m-1 < 0:  # nums2 left
        nums1[:n] = nums2[:n]
    ## when n decreases to 0 but m is not yet 0, the loop will stop. The first m elements in num2 should be copied to nums1

101. Symmetric Tree

Topic: Tree, Depth-first Search, Breadth-first Search

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Note: Bonus points if you could solve it both recursively and iteratively.

Approach1

Recursive:

def isSymmetric(self, root: TreeNode) -> bool:
    def isMirror(L,R):
        if L and R:
            # print(L.val,R.val,L,R)
            return L.val == R.val and isMirror(L.left,R.right) and isMirror(L.right,R.left)
        return L == R
    return not root or isMirror(root.left, root.right)

Approach2

Iterative:

def isSymmetric(self, root: TreeNode) -> bool:
    queue = [root]
    # print(queue,len(queue)) # len = 1
    while queue:
        values = [i.val if i else None for i in queue]
        print(values)
        if values != values[::-1]: return False
        queue = [child for i in queue if i for child in (i.left, i.right)]
    return True

# stdout:
# [1]
# [TreeNode{val: 2, left: TreeNode{val: 3, left: None, right: None}, right: TreeNode{val: 4, left: None, right: None}}, TreeNode{val: 2, left: TreeNode{val: 4, left: None, right: None}, right: TreeNode{val: 3, left: None, right: None}}]
# [2, 2]
# [TreeNode{val: 3, left: None, right: None}, TreeNode{val: 4, left: None, right: None}, TreeNode{val: 4, left: None, right: None}, TreeNode{val: 3, left: None, right: None}]
# [3, 4, 4, 3]
# [None, None, None, None, None, None, None, None]
# [None, None, None, None, None, None, None, None]
# []

104. Maximum Depth of Binary Tree

Topic: Tree, Depth-first Search

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its depth = 3.

Approach1

recursive:

def maxDepth(self, root: TreeNode) -> int:
    if not root:
        return 0
    return max(self.maxDepth(root.left), self.maxDepth(root.right))+1

Approach2

Iterative:

def maxDepth(self, root: TreeNode) -> int:
    if root ==None:
        return 0
    
    stack = [root]
    depth = 0
    while stack:
        nextLevel = []
        depth+=1
        for item in stack:
            if item.left:
                nextLevel.append(item.left)
            if item.right:
                nextLevel.append(item.right)
        stack = nextLevel
    return depth

Approach

def maxDepth(root: TreeNode) -> int:
    queue = [root]
    cnt = 0
    while queue:
        cnt += 1
        queue = [child for i in queue if i for child in (i.left,i.right)]
    return cnt -1