# Posts published in “Easy”

You are climbing a staircase. It takes `n` steps to reach the top.

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

Example 1:

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

Example 2:

```Input: n = 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
```

Constraints:

• `1 <= n <= 45`

Idea:

Dynamic programing

``````dp[i] represents how many distinct ways climb i stairs to the top
dp[1] = 1;
dp[2] = 2;
dp[3] = dp[2] + d[1];
dp[4] = dp[3] + d[2];
...
dp[i] = dp[i - 1] + dp[i - 2];``````

Solution:

``````/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
let dp = Array.from(new Array(n + 1));
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};``````

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example 1:

```Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
```

Example 2:

```Input: nums = [1]
Output: 1
```

Example 3:

```Input: nums = [5,4,-1,7,8]
Output: 23
```

Constraints:

• `1 <= nums.length <= 3 * 104`
• `-105 <= nums[i] <= 105`

Idea:

Dynamic Programing

• Base case: dp[0] = nums[0];
• dp[i] = Math.max(dp[i – 1] + nums[i], nums[i]);

Solution:

``````/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
// dp[i] the largest sum of subarray in nums[0...i]
let dp = new Array(nums.length);
// basic case:
dp[0] = nums[0];
for (let i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
}
return Math.max(...dp);
};``````

Given the `root` of a binary tree, invert the tree, and return its root.

Example 1:

```Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
```

Example 2:

```Input: root = [2,1,3]
Output: [2,3,1]
```

Example 3:

```Input: root = []
Output: []
```

Constraints:

• The number of nodes in the tree is in the range `[0, 100]`.
• `-100 <= Node.val <= 100`

Solution:

``````/**
* 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 === null) return root;

let temp = new TreeNode();
temp = root.right;
root.right = root.left;
root.left = tmp;

root.left = invertTree(root.left);
root.right = invertTree(root.right);
return root;
};``````

Given the `root` of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

```Input: root = [3,9,20,null,null,15,7]
Output: 3
```

Example 2:

```Input: root = [1,null,2]
Output: 2
```

Example 3:

```Input: root = []
Output: 0
```

Example 4:

```Input: root = [0]
Output: 1
```

Constraints:

• The number of nodes in the tree is in the range `[0, 104]`.
• `-100 <= Node.val <= 100`

Solution:

``````/**
* 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 1 + Math.max(maxDepth(root.left) , maxDepth(root.right));
};``````

Given the `root` of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

```Input: root = [1,2,2,3,4,4,3]
Output: true
```

Example 2:

```Input: root = [1,2,2,null,3,null,3]
Output: false
```

Constraints:

• The number of nodes in the tree is in the range `[1, 1000]`.
• `-100 <= Node.val <= 100`

Solution:

``````/**
* 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 {boolean}
*/
var isSymmetric = function(root) {
return isSameTree(root, root);
};

function isSameTree(t1, t2) {
if (t1 === null && t2 === null) return true;
if (t1 === null || t2 === null) return false;
return t1.val === t2.val && isSameTree(t1.left, t2.right) && isSameTree(t1.right, t2.left);
}``````

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example 1:

```Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
```

Example 2:

```Input: l1 = [], l2 = []
Output: []
```

Example 3:

```Input: l1 = [], l2 = [0]
Output: [0]
```

Constraints:

• The number of nodes in both lists is in the range `[0, 50]`.
• `-100 <= Node.val <= 100`
• Both `l1` and `l2` are sorted in non-decreasing order.

Solution: (Recursion)

``````/**
* 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 mergeTwoLists = function(l1, l2) {
// If one of the list is emptry, return the other one.
if (!l1 || !l2) return l1 ? l1 : l2;

// The smaller one becomes the head.
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
};``````

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the `MinStack` class:

• `MinStack()` initializes the stack object.
• `void push(val)` pushes the element `val` onto the stack.
• `void pop()` removes the element on the top of the stack.
• `int top()` gets the top element of the stack.
• `int getMin()` retrieves the minimum element in the stack.

Example 1:

```Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]```

Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

Constraints:

• `-231 <= val <= 231 - 1`
• Methods `pop``top` and `getMin` operations will always be called on non-empty stacks.
• At most `3 * 104` calls will be made to `push``pop``top`, and `getMin`.

Idea:

Use two stacks to solve this problem

Solution:

``````/**
* initialize your data structure here.
*/
var MinStack = function() {
this.min = [];
this.stack = [];
};

/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.stack.push(x);
let min = this.getMin();
if (min === undefined || min >= x) {
this.min.push(x);
}
};

/**
* @return {void}
*/
MinStack.prototype.pop = function() {
let val = this.stack.pop();
let min = this.getMin();
if (val === min) this.min.pop();
};

/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.stack[this.stack.length - 1];
};

/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
return this.min[this.min.length - 1];
};

/**
* Your MinStack object will be instantiated and called as such:
* var obj = new MinStack()
* obj.push(x)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/``````

Given a string `s` containing just the characters `'('``')'``'{'``'}'``'['` and `']'`, determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Example 1:

```Input: s = "()"
Output: true
```

Example 2:

```Input: s = "()[]{}"
Output: true
```

Example 3:

```Input: s = "(]"
Output: false
```

Example 4:

```Input: s = "([)]"
Output: false
```

Example 5:

```Input: s = "{[]}"
Output: true
```

Constraints:

• `1 <= s.length <= 104`
• `s` consists of parentheses only `'()[]{}'`.

Idea:

Stack

Solution:

``````/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
let stack = [];
let open = {'(' : ')', '{' : '}', '[' : ']'};
let close = {')':true, '}':true, ']': true};

for (let char of s) {
if (open[char]) {
stack.push(char);
} else if (close[char]) {
if (open[stack.pop()] !== char) return false;
}
}

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

Given an integer `num`, repeatedly add all its digits until the result has only one digit, and return it.

Example 1:

```Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2
Since 2 has only one digit, return it.
```

Example 2:

```Input: num = 0
Output: 0
```

Constraints:

• `0 <= num <= 231 - 1`

Idea 1:

recursive

Solution 1:

``````/**
* @param {number} num
* @return {number}
*/
let nums = num.toString().split("");
let sumOfNums = sum(nums);

// base case:
if (sumOfNums  < 10) return sumOfNums;
};

function sum(arr) {
return arr.reduce((a, b) => parseInt(a) + parseInt(b), 0);
}``````

Idea 2:

mathematics algorithms in O(1) runtime

Solution 2:

``````/**
* @param {number} num
* @return {number}
*/
return num % 9 ? num % 9 : Math.min(num, 9);
};``````

Given an integer `n`, return the number of trailing zeroes in `n!`.

Follow up: Could you write a solution that works in logarithmic time complexity?

Example 1:

```Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.
```

Example 2:

```Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.
```

Example 3:

```Input: n = 0
Output: 0
```

Constraints:

• `0 <= n <= 104`

Idea:

All trailing zeros are come from even_num x 5, we have more even_num than 5, so only count factor 5.

4! = 1x2x3x4 = 24, we haven’t encountered any 5 yet, so we don’t have any trailing zero.

5! = 1x2x3x4x5 = 120, we have one trailing zero. either 2×5, or 4×5 can contribute to that zero.

9! = 362880, we only encountered 5 once, so 1 trailing zero as expected.

10! = 3628800, 2 trailing zeros, since we have two numbers that have factor 5, one is 5 and the other is 10 (2×5)

100/5 = 20, we have 20 numbers have factor 5: 5, 10, 15, 20, 25, …, 95, 100.

Is the number of trailing zero 20? No, it’s 24, why?

Within that 20 numbers, we have 4 of them: 25 (5×5), 50 (2x5x5), 75 (3x5x5), 100 (4x5x5) that have an extra factor of 5.

So, for a given number n, we are looking how many numbers <=n have factor 5, 5×5, 5x5x5, …

Summing those numbers up we got the answer.

e.g. 1000! has 249 trailing zeros:

1000/5 = 200

1000/25 = 40

1000/125 = 8

1000/625 = 1

200 + 40 + 8 + 1 = 249

Solution:

``````/**
* @param {number} n
* @return {number}
*/
var trailingZeroes = function(n) {
return n < 5 ? 0 : parseInt(n / 5) + trailingZeroes(parseInt(n / 5));
};``````