# Posts tagged as “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 an array of integers `numbers` that is already sorted in ascending order, find two numbers such that they add up to a specific `target` number.

Return the indices of the two numbers (1-indexed) as an integer array `answer` of size `2`, where `1 <= answer[0] < answer[1] <= numbers.length`.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Example 1:

```Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
```

Example 2:

```Input: numbers = [2,3,4], target = 6
Output: [1,3]
```

Example 3:

```Input: numbers = [-1,0], target = -1
Output: [1,2]
```

Constraints:

• `2 <= numbers.length <= 3 * 104`
• `-1000 <= numbers[i] <= 1000`
• `numbers` is sorted in increasing order.
• `-1000 <= target <= 1000`
• Only one valid answer exists.

Solution 1: (Two pointer)

``````/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
let l = 0;
let r = numbers.length - 1;
while (l < r) {
let sum = numbers[l] + numbers[r];
if (sum === target) break;
else if (sum > target) r--;
else l++;
}
// this question use 1-indexed
return [l + 1, r + 1];
};``````

Solution 2: (Hash table)

``````var twoSum = function(numbers, target) {
let map = new Map;
for (var i = 0; i < numbers.length; i++) {
var diff = target - numbers[i];
if(map.has(diff)) {
return [map.get(diff), i + 1];
}
map.set(numbers[i], i + 1);
}
};``````

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

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Example 1:

```Input: nums = [1,3,5,6], target = 5
Output: 2
```

Example 2:

```Input: nums = [1,3,5,6], target = 2
Output: 1
```

Example 3:

```Input: nums = [1,3,5,6], target = 7
Output: 4
```

Example 4:

```Input: nums = [1,3,5,6], target = 0
Output: 0
```

Example 5:

```Input: nums = [1], target = 0
Output: 0
```

Constraints:

• `1 <= nums.length <= 104`
• `-104 <= nums[i] <= 104`
• `nums` contains distinct values sorted in ascending order.
• `-104 <= target <= 104`

Idea:

Use Binary Search

• Time complexity: O(logn)
• Space complexity: O(1)

Solution:

``````/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
let l = 0;
let r = nums.length;

while (l < r) {
let mid = l + Math.floor((r - l) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] > target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};``````

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);
};``````

Given an array `nums` of size `n`, return the majority element.

The majority element is the element that appears more than `⌊n / 2⌋` times. You may assume that the majority element always exists in the array.

Example 1:

```Input: nums = [3,2,3]
Output: 3
```

Example 2:

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

Constraints:

• `n == nums.length`
• `1 <= n <= 5 * 104`
• `-231 <= nums[i] <= 231 - 1`

Solution 1: (Hash Table)

• Time Complexity : O(n)
• Space Complexity : O(n)
``````/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
let map = new Map();
for (let num of nums) {
map.set(num, (map.has(num) ? map.get(num) : 0)  + 1);
if (map.get(num) > nums.length / 2) return num;
}
return -1;
};``````

Solution 2: (Sorting)

• Time Complexity : O(n)
• Space Complexity : O(1)
``````var majorityElement = function(nums) {
nums.sort();
return nums[Math.floor(nums.length / 2)];
};``````

Solution 3: (Divide and conquer)

• Time Complexity : O(nlogn)
• Space Complexity : O(logn)
``````var majorityElement = function(nums) {
return majority(nums, 0, nums.length - 1);
};

function majority(nums, l, r) {
if (l === r) return nums[l];
const mid = l + Math.floor((r - l) / 2);
const left = majority(nums, l , mid);
const right = majority(nums, mid + 1, r);
if (left === right) return left;
return nums.slice(l, r + 1).filter(x => x === left).length >
nums.slice(l, r + 1).filter(x => x === right).length
? left : right;
}``````

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]];
}