# Posts published in “Easy”

Given an integer array `nums` sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

```Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
```

Example 2:

```Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
```

Constraints:

• `1 <= nums.length <= 104`
• `-104 <= nums[i] <= 104`
• `nums` is sorted in non-decreasing order.

Solution 1: (Quick Sort)

``````/**
* @param {number[]} nums
* @return {number[]}
*/
var sortedSquares = function(nums) {
nums = nums.map(num => num * num);
quickSort(nums, 0, nums.length - 1);
return nums;
};

function quickSort(nums, left, right) {
let index;
if (nums.length > 1) {
// index returned from partition
index = partition(nums, left, right);
// more elements on the left side of the pivot
if (left < index - 1)
quickSort(nums, left, index - 1);
// more elements on the right side of the pivot
if (index < right)
quickSort(nums, index, right);
}
// you can return or not return,
// since we change nums, no need to return
// return nums;
}

function partition(nums, start, end) {
let l = start, r = end;
let mid = Math.floor((start + end) / 2);
let pivot = nums[mid];
// Important: l <= r not l < r
while (l <= r) {
while(nums[l] < pivot)
l++;
while(nums[r] > pivot)
r--;
if (l <= r) {
// swap
[nums[l], nums[r]] = [nums[r], nums[l]];
l++;
r--;
}
}
return l;
}``````

Solution 2: (Merge Sort)

``````/**
* @param {number[]} nums
* @return {number[]}
*/
var sortedSquares = function(nums) {
nums = nums.map(num => num * num);
let temp = [];
mergeSort(nums, 0, nums.length - 1, temp);
return nums;
};

function mergeSort(nums, start, end, temp) {
if (start >= end) return;
let mid =  Math.floor((start + end) / 2);
mergeSort(nums, start, mid, temp);
mergeSort(nums, mid + 1, end, temp);
merge(nums, start, end, temp);
}

function merge(nums, start, end, temp) {
let mid =  Math.floor((start + end) / 2);
let l_index = start;
let r_index = mid + 1;
let index = start;
while (l_index <= mid && r_index <= end) {
if (nums[l_index] < nums[r_index]) {
temp[index++] = nums[l_index++];
} else {
temp[index++] = nums[r_index++];
}
}
while (l_index <= mid) {
temp[index++] = nums[l_index++];
}
while (r_index <= end) {
temp[index++] = nums[r_index++];
}
for (let i = 0; i <= end; i++)
nums[i] = temp[i];
}``````

Given an integer array `nums` where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:

```Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

```

Example 2:

```Input: nums = [1,3]
Output: [3,1]
Explanation: [1,3] and [3,1] are both a height-balanced BSTs.
```

Constraints:

• `1 <= nums.length <= 104`
• `-104 <= nums[i] <= 104`
• `nums` is sorted in a strictly increasing order.

Idea:

Recursion + Divide and Conquer

Time complexity: O(n)
Space complexity: O(logn)

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 {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function(nums) {
return createBST(nums, 0, nums.length - 1);
};

function createBST(nums, l, r) {
// exit recursion condition
if (l > r) return null;

let mid = l + Math.floor((r - l) / 2);
let root = new TreeNode(nums[mid]);
root.left = createBST(nums, l, mid - 1);
root.right = createBST(nums, mid + 1, r);
return root;
}``````

Given the `head` of a singly linked list, reverse the list, and return the reversed list.

Example 1:

```Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
```

Example 2:

```Input: head = [1,2]
Output: [2,1]
```

Example 3:

```Input: head = []
Output: []
```

Constraints:

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

Idea: 背口诀

```reverse LinkedList 口诀: create newHead and next

Solution:

``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @return {ListNode}
*/
// empty or only one node

let next = new ListNode();
// next helper create
// disconnect, and point to newHead.next
// move head to next location
}
};``````

Given the `root` of a binary tree and an integer `targetSum`, return `true` if the tree has a root-to-leaf path such that adding up all the values along the path equals `targetSum`.

leaf is a node with no children.

Example 1:

```Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
```

Example 2:

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

Example 3:

```Input: root = [1,2], targetSum = 0
Output: false
```

Constraints:

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

Solution: (Recursion)

• Time complexity: O(n)
• Space complexity: O(n)
``````/**
* 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 === null) return false;
if (root.val === targetSum && root.left === null && root.right === null) return true;
return hasPathSum(root.left, targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val);
};``````

Given a string `S`, return the “reversed” string where all characters that are not a letter stay in the same place, and all letters reverse their positions.

Example 1:

```Input: "ab-cd"
Output: "dc-ba"
```

Example 2:

```Input: "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"
```

Example 3:

```Input: "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"
```

Note:

1. `S.length <= 100`
2. `33 <= S[i].ASCIIcode <= 122`
3. `S` doesn’t contain `\` or `"`

Idea:

Two pointers

Solution:

``````/**
* @param {string} S
* @return {string}
*/
var reverseOnlyLetters = function(S) {
let l = 0;
let r = S.length - 1;
let arr = S.split('');

while (l < r) {
if (!isAlpha(arr[l])) l++;
if (!isAlpha(arr[r])) r--;
if (isAlpha(arr[l]) && isAlpha(arr[r])) {
// swap
[arr[l], arr[r]] = [arr[r], arr[l]];
l++
r--;
}
}
return arr.join('');
};

var isAlpha = (c) => /[a-zA-Z]/.test(c);``````

You are given the `root` of a binary search tree (BST) and an integer `val`.

Find the node in the BST that the node’s value equals `val` and return the subtree rooted with that node. If such a node does not exist, return `null`.

Example 1:

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

Example 2:

```Input: root = [4,2,7,1,3], val = 5
Output: []
```

Constraints:

• The number of nodes in the tree is in the range `[1, 5000]`.
• `1 <= Node.val <= 107`
• `root` is a binary search tree.
• `1 <= val <= 107`

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
* @param {number} val
* @return {TreeNode}
*/
var searchBST = function(root, val) {
if (root === null) return null
if (root.val === val)
return root;
else if (val < root.val)
return searchBST(root.left, val);
else
return searchBST(root.right, val);
};``````

Roman numerals are represented by seven different symbols: `I``V``X``L``C``D` and `M`.

```Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000```

For example, `2` is written as `II` in Roman numeral, just two one’s added together. `12` is written as `XII`, which is simply `X + II`. The number `27` is written as `XXVII`, which is `XX + V + II`.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not `IIII`. Instead, the number four is written as `IV`. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as `IX`. There are six instances where subtraction is used:

• `I` can be placed before `V` (5) and `X` (10) to make 4 and 9.
• `X` can be placed before `L` (50) and `C` (100) to make 40 and 90.
• `C` can be placed before `D` (500) and `M` (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

```Input: s = "III"
Output: 3
```

Example 2:

```Input: s = "IV"
Output: 4
```

Example 3:

```Input: s = "IX"
Output: 9
```

Example 4:

```Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
```

Example 5:

```Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
```

Constraints:

• `1 <= s.length <= 15`
• `s` contains only the characters `('I', 'V', 'X', 'L', 'C', 'D', 'M')`.
• It is guaranteed that `s` is a valid roman numeral in the range `[1, 3999]`.

Idea:

• Accumulate the value of each symbol.
• If the current symbol is greater than the previous one, substract twice of the previous value. e.g. IX, 1 + 10 – 2 * 1 = 9

Solution:

• Time complexity: O(n)
• Space complexity: O(1)
``````/**
* @param {string} s
* @return {number}
*/
var romanToInt = function(s) {
let conversion = {"I": 1, "V":5,"X":10,"L":50,"C":100,"D":500,"M":1000};
let total = 0;

for (var i = 0; i < s.length; i++) {
// first symbol
total += conversion[s[i]];
// if current symbol is bigger than previous symbol
// subtract 2 times of the previous value
if (i > 0 && conversion[s[i]] > conversion[s[i - 1]])
total -= 2 * conversion[s[i - 1]];
}
};``````

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:

```Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
The maximum number of consecutive 1s is 3.
```

Note:

• The input array will only contain `0` and `1`.
• The length of input array is a positive integer and will not exceed 10,000

Solution 1:

``````/**
* @param {number[]} nums
* @return {number}
*/
var findMaxConsecutiveOnes = function(nums) {
let max = 0;
let count = 0;
for (let num of nums) {
if (num === 1) {
count++;
} else {
max = Math.max(max, count);
count = 0;
}
}
max = Math.max(max, count);
return max;
}``````

Solution 2:

``````var findMaxConsecutiveOnes = function(nums) {
let max = 0;
let res = 0;
for (let num of nums) {
let sign = 1;
if (num === 0) {
sign = 0;
} else {
sign = 1;
}
max = sign * max + num;
// update max result
if (max > res) res = max;
}
return res;
};``````

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

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 isBalanced = function(root) {
if (root === null) return true;
const res = [true];
height(root, res);
return res[0];
};

function height(root, res) {
if (root === null) return 0;
const l = height(root.left, res);
const r = height(root.right, res);
if (Math.abs(l - r) > 1) res[0] = false;
return Math.max(l, r) + 1;
}``````

Given an integer `numRows`, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

```Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
```

Example 2:

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

Constraints:

• `1 <= numRows <= 30`

Solution:

``````/**
* @param {number} numRows
* @return {number[][]}
*/
var generate = function(numRows) {
let res = [[1]];

while(numRows > 1) {
let previous = res[res.length - 1];
// The first row element is always 1.
let cur = [1];
for (let i = 1; i < previous.length; i++) {
// generate: sum of the elements above-and-to-the-left and above-and-to-the-right.
cur.push(previous[i - 1] + previous[i]);
}
// The last row element is always 1.
cur.push(1);
res.push(cur.concat());
numRows--;
}
return res;
};``````