Categories

## 56. Merge Intervals Leetcode Javascript Solution

The Problem:

Given an array of `intervals` where `intervals[i] = [starti, endi]`, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

```Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
```

Example 2:

```Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
```

Constraints:

• `1 <= intervals.length <= 104`
• `intervals[i].length == 2`
• `0 <= starti <= endi <= 104`

The Problem:

```var merge = function(intervals) {
if(intervals.length == 1 || intervals.length == 0){ return intervals}
intervals.sort((a,b) => a[0] !== b[0] ? a[0]-b[0] : a[1]-b[1])
// console.log(intervals)
let ans = [], prev = intervals[0]
ans.push(prev)
for(let interval of intervals){
// console.log(prev)
if(interval[0] <= prev[1]){
prev[1] = Math.max(interval[1], prev[1])
//prev = interval (remember not to update prev in this if
} else {
ans.push(interval)
prev = interval
}
// console.log(ans)
}
return ans
};```
Categories

## 438. Find All Anagrams in a String Leetcode Javascript Solution

The Problem:

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

```Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
```

Example 2:

```Input:
s: "abab" p: "ab"
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".```

The Solution:

```var findAnagrams = function(s, p) {
let set = new Map()
for(let i = 0; i < p.length; i++){
if(!set.has(p[i])){
set.set(p[i],1)
} else{
set.set(p[i],set.get(p[i]) + 1)
}
}
// console.log(set)
let ans = []
let left = 0, right = 0, count = set.size
while (right < s.length){
if(set.has(s[right])){
set.set(s[right],set.get(s[right]) - 1)
if(set.get(s[right])== 0){
count--
}
}
while(count == 0){
if(set.has(s[left])){
set.set(s[left],set.get(s[left]) + 1)
if(set.get(s[left]) > 0){
count++
}
}
if(right - left +1 == p.length){
ans.push(left)
}
left++
}
right++
}
return ans
};```
Categories

## 236. Lowest Common Ancestor of a Binary Tree Leetcode Javascript Solution

The Problem:

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

```Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
```

Example 2:

```Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
```

Example 3:

```Input: root = [1,2], p = 1, q = 2
Output: 1
```

Constraints:

• The number of nodes in the tree is in the range `[2, 105]`.
• `-109 <= Node.val <= 109`
• All `Node.val` are unique.
• `p != q`
• `p` and `q` will exist in the tree.

The Solution:

```var lowestCommonAncestor = function(root, p, q) {
if(!root || root== p || root == q) return root
let left = lowestCommonAncestor(root.left,p,q)
let right = lowestCommonAncestor(root.right,p,q)
return (left && right) ? root : (left || right)
};```
Categories

## 47. Permutations II Leetcode Javascript Solution

The Problem:

Given a collection of numbers, `nums`, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

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

Example 2:

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

Constraints:

• `1 <= nums.length <= 8`
• `-10 <= nums[i] <= 10`

The Solution:

For this kind of problem, we’ll need to use backtracking. We also implement a boolean array with the same length as that of the number array to keep track of visited elements (because the number array contains duplicates):

```var permuteUnique = function(nums) {
let results = []
nums.sort((a,b) => a-b)
function backtrack(nums,results, temp,used){
if(temp.length == nums.length){
results.push([…temp])
}
for(let i = 0; i < nums.length; i++){
// console.log(used + “ “+ i + “ “ + temp)
if(used[i] || (i > 0 && nums[i] == nums[i-1] && used[i — 1]) ){continue}
used[i] = true
temp.push(nums[i])
backtrack(nums,results, temp, used)
used[i] = false
temp.pop()
}
}
backtrack(nums,results, new Array(), new Array(nums.length).fill(false))
return results
};```
Categories

## 46. Permutations Leetcode Javascript Solution

The Problem:

Given an array `nums` of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• `1 <= nums.length <= 6`
• `-10 <= nums[i] <= 10`
• All the integers of `nums` are unique.

The Solution:

We use backtracking:

```var permute = function(nums) {
let results = []
function backtrack(nums, results, temp){
if(temp.length == nums.length){
results.push([...temp])
}
for(let i = 0 ; i < nums.length; i++){
if(temp.includes(nums[i])){continue}
temp.push(nums[i])
backtrack(nums,results,temp)
temp.pop()
}
}
backtrack(nums,results, new Array())
return results
};```
Categories

## 90. Subsets II Leetcode Javascript Solution

The Problem:

Given an integer array `nums` that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

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

Constraints:

• `1 <= nums.length <= 10`
• `-10 <= nums[i] <= 10`

The Solution:

```var subsetsWithDup = function(nums) {
let results = [],temp = []
nums.sort((a,b) => a-b)
console.log(nums)
function backtrack(nums,start,results, temp){
results.push([...temp])
/* console.log("results " )
for( rest of results){
console.log(rest)
}
*/
for(let i = start; i < nums.length; i++){
//console.log("i " + i)
if(i == start || nums[i] != nums[i-1]){
//                 console.log("i after if" + i)
temp.push(nums[i])
//   console.log(temp)
backtrack(nums,i+1,results,temp)
temp.pop()
//                console.log("temp after pop " + temp)
}
}
}
backtrack(nums,0,results,temp)
return results
};```
Categories

## 494. Target Sum Leetcode Javascript Solution

The Problem:

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols `+` and `-`. For each integer, you should choose one from `+` and `-` as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

```Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.
```

Constraints:

• The length of the given array is positive and will not exceed 20.
• The sum of elements in the given array will not exceed 1000.
• Your output answer is guaranteed to be fitted in a 32-bit integer.

The Solution:

Recursion:

```var findTargetSumWays = function(nums, S) {
let ans = 0
calculate(nums,0,0,S)
return ans
function calculate(nums,i,currentSum, S){
if(i == nums.length){
if(currentSum == S){
ans++
}
}
else{
calculate(nums,i+1, currentSum + nums[i],S)
calculate(nums,i+1, currentSum - nums[i], S)
}
}
};```
Categories

## 221. Maximal Square Leetcode Javascript Solution

The Problem:

Given an `m x n` binary `matrix` filled with `0`‘s and `1`‘s, find the largest square containing only `1`‘s and return its area.

Example 1:

```Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4
```

Example 2:

```Input: matrix = [["0","1"],["1","0"]]
Output: 1
```

Example 3:

```Input: matrix = [["0"]]
Output: 0
```

Constraints:

• `m == matrix.length`
• `n == matrix[i].length`
• `1 <= m, n <= 300`
• `matrix[i][j]` is `'0'` or `'1'`.

The Solution:

We use dynamic programming to solve this problem.

```var maximalSquare = function(matrix) {
if(matrix.length == 0 || matrix[0].length == 0){ return 0}
let dp = new Array(matrix.length + 1).fill(0).map(el => new Array(matrix[0].length+1).fill(0))
let maxSquare = 0
//console.log(dp)
for(let i = 0; i < matrix.length; i++){
for(let j = 0; j < matrix[0].length; j++){
if(matrix[i][j] == '1'){
dp[i+1][j+1]= Math.min(dp[i][j], dp[i+1][j], dp[i][j+1]) +1
maxSquare = Math.max(maxSquare, dp[i+1][j+1])
}
}
}
//console.log(dp)
return maxSquare*maxSquare
};```
Categories

## 76. Minimum Window Substring Leetcode Javascript Solution

The Problem:

Given two strings `s` and `t`, return the minimum window in `s` which will contain all the characters in `t`. If there is no such window in `s` that covers all characters in `t`, return the empty string `""`.

Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in `s`.

Example 1:

```Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
```

Example 2:

```Input: s = "a", t = "a"
Output: "a"
```

Constraints:

• `1 <= s.length, t.length <= 105`
• `s` and `t` consist of English letters.

The Solution:

```var minWindow = function(s, t) {
if( !s || s.length < t.length){ return ""}
let left = 0, right = 0, start,end, index = 0, min = 99999;
let charsT = new Map()
for(let i = 0; i < t.length; i++){
if(!charsT.get(t[i])){
charsT.set(t[i],1)
} else {
charsT.set(t[i],charsT.get(t[i])+1)
}
}
//console.log(charsT)
while(right < s.length){
} else {
}
if(charsT.get(s[right]) && charsS.get(s[right]) == charsT.get(s[right]) ){
index++
}
while(left <= right && index == charsT.size){
//  console.log("left " + left + " right " + right)
if(right - left + 1 < min){
min = right - left + 1
start = left
end = right
//   console.log("start " + start + " end " + end)
}
let c = s[left]
//  console.log("eliminated start char: ")
}
if(charsT.get(c) && charsS.get(c) < charsT.get(c) ){
index -= 1
}
left++
}
right++
}
//   console.log("start " + start + " end " + end)
return s.substring(start,end+1)
};```
Categories

## 41. First Missing Positive Leetcode Javascript Solution

The Problem:

Given an unsorted integer array `nums`, find the smallest missing positive integer.

Example 1:

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

Example 2:

```Input: nums = [3,4,-1,1]
Output: 2
```

Example 3:

```Input: nums = [7,8,9,11,12]
Output: 1
```

Constraints:

• `0 <= nums.length <= 300`
• `-231 <= nums[i] <= 231 - 1`

The Solution:

```var firstMissingPositive = function(nums) {
if(nums.length == 0) return 1
let ans = 999999, changed = false
nums.sort((a,b) => a-b)
if(nums[0] > 1  || nums[nums.length-1] < 0){
return 1
}
//console.log(nums)
for(let i = 0; i < nums.length-1; i++){
if(nums[i] >= 0){
let diff = nums[i+1] - nums[i]
//console.log(diff)
if( diff > 1){
ans = Math.min(ans, nums[i] + 1)
//console.log("max " + ans)
changed =true
}
} else {
if(nums[i +1] > 1 && nums[i] < 0){
return 1
}
}
}
if(changed == false){
ans = nums[nums.length-1] + 1
}
return ans
};```