Categories

## 143. Reorder List Leetcode Javascript Solution

The Problem:

You are given the head of a singly linked-list. The list can be represented as:

```L0 → L1 → … → Ln - 1 → Ln
```

Reorder the list to be on the following form:

```L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
```

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Example 1:

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

Example 2:

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

Constraints:

• The number of nodes in the list is in the range `[1, 5 * 104]`.
• `1 <= Node.val <= 1000`

The Solution:

```var reorderList = function(head) {
while(fast.next && fast.next.next){
slow = slow.next
fast = fast.next.next
}
//console.log(fast.val)
p2 = slow.next
//console.log(p2)
slow.next = null
let prev = null
while(p2){
let next = p2.next
p2.next = prev
prev = p2
p2 = next
}
console.log(prev)
let part1 = head, part2 = prev
while(part2){
let p1 = part1.next
let p2 = part2.next
part1.next = part2
part2.next = p1
part1 = p1
part2 = p2
}
};
```
Categories

## 1721. Swapping Nodes in a Linked List Leetcode Javascript Solution

The Problem:

You are given the `head` of a linked list, and an integer `k`.

Return the head of the linked list after swapping the values of the `kth` node from the beginning and the `kth` node from the end (the list is 1-indexed).

Example 1:

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

Example 2:

```Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5
Output: [7,9,6,6,8,7,3,0,9,5]
```

Example 3:

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

Example 4:

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

Example 5:

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

Constraints:

• The number of nodes in the list is `n`.
• `1 <= k <= n <= 105`
• `0 <= Node.val <= 100`

The Solution:

I got stuck at trying a new element swapping method with ES6 and wasted a good amount of time. In the end, I printed out variables line by line and used the old swapping method.

```var swapNodes = function(head, k) {
let dummy = new ListNode(0)
let fast = dummy, slow = dummy
for(let i = 1; i <= k; i++){
fast = fast.next
}
//  console.log(fast.val)
let first = fast
while(fast.next != null){
slow = slow.next
fast = fast.next
}
let second = slow.next
//console.log("first: " + first.val + " second: " + second.val)
// first.val, second.val = second.val, first.val
//let a = 2, b = 4
let temp = first.val
first.val = second.val
second.val = temp
// console.log( "a: " + a + " b: " + b)
// console.log("first: " + first.val + " second: " + second.val)
return dummy.next
};```
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

## 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

## 78. Subsets Leetcode Javascript Solution

The Problem:

Given an integer array `nums` of unique elements, 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,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
```

Example 2:

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

Constraints:

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

The Solution:

We use backtracking for this problem.

```var subsets = function(nums) {
let results = []
nums.sort()
backtrack(nums,0,results,new Array())
function backtrack(nums, start, results, temp){
results.push([...temp])
for(let i = start; i < nums.length; i++){
temp.push(nums[i])
backtrack(nums,i+1,results,temp)
temp.pop()
}
}
return results
};```
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

## 84. Largest Rectangle in Histogram Leetcode Javascript Solution

The Problem:

Given an array of integers `heights` representing the histogram’s bar height where the width of each bar is `1`, return the area of the largest rectangle in the histogram.

Example 1:

```Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.
```

Example 2:

```Input: heights = [2,4]
Output: 4```

The Solution:

```var largestRectangleArea = function(heights) {
let stack = [], left = [], right = [], area = []
for(let i = 0; i < heights.length; i++){
if(stack.length == 0){
stack.push(i)
left[i] = 0
} else {
//console.log(heights[stack[stack.length-1]]  + " heights[i] " + heights[i])
while(stack.length != 0 && heights[stack[stack.length-1]] >= heights[i]){
stack.pop()
}
// console.log("stack after pop " + stack)
left[i] = stack.length ==0 ? 0 : stack[stack.length-1] + 1
stack.push(i)
}
}
// console.log(left)
stack.length = 0
let n = heights.length-1
for(let i = n; i >= 0; i--){
if(stack.length == 0){
stack.push(i)
right[i] = n
} else {
// console.log(heights[stack[stack.length-1]]  + " heights[i] " + heights[i])
while(stack.length != 0 && heights[stack[stack.length-1]] >= heights[i]){
stack.pop()
}
// console.log("stack after pop " + stack)
right[i] = stack.length ==0 ? n : stack[stack.length-1] - 1
stack.push(i)
}
}
//console.log(right)
let maxArea = 0
for(let i = 0; i <= n; i++){
area[i] = heights[i]*(right[i] - left[i] + 1)
maxArea = Math.max(area[i],maxArea)
}
return maxArea
};```
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]