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

## 32. Longest Valid Parentheses Leetcode Javascript Solution

The Problem:

Given a string containing just the characters `'('` and `')'`, find the length of the longest valid (well-formed) parentheses substring.

Example 1:

```Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
```

Example 2:

```Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
```

Example 3:

```Input: s = ""
Output: 0
```

Constraints:

• `0 <= s.length <= 3 * 104`
• `s[i]` is `'('`, or `')'`.

The Solution:

```var longestValidParentheses = function(s) {
let max = 0, count = 0
for(let i = 0; i < s.length; i++){
count = 0
for(let j = i; j < s.length; j++){
if(s[j] == "("){
count++
} else {
count--
}
if(count < 0){
break
}
if(count == 0){
// console.log(" i " + i + " j " + j)
max = Math.max(max,j-i + 1)
}
}
}
return max
};```
Categories

## 23. Merge k Sorted Lists Leetcode Javascript Solution

The Problem:

You are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order.

Example 1:

```Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
```

Example 2:

```Input: lists = []
Output: []
```

Example 3:

```Input: lists = [[]]
Output: []
```

Constraints:

• `k == lists.length`
• `0 <= k <= 10^4`
• `0 <= lists[i].length <= 500`
• `-10^4 <= lists[i][j] <= 10^4`
• `lists[i]` is sorted in ascending order.
• The sum of `lists[i].length` won’t exceed `10^4`.

The Solution:

```var mergeKLists = function(lists) {
if(!lists) return []
let nodes = []
for(list of lists){
while(list){
nodes.push(list.val)
list = list.next
}
}
nodes.sort((a,b) => a-b)
// console.log(nodes)
let node = head = new ListNode(0)
for( e in nodes){
node.next = new ListNode(nodes[e])
node = node.next
}
};```
Categories

## 5. Longest Palindromic Substring Leetcode Javascript Solution

The Problem:

Given a string `s`, return the longest palindromic substring in `s`.

Example 1:

```Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.
```

Example 2:

```Input: s = "cbbd"
Output: "bb"
```

Example 3:

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

Example 4:

```Input: s = "ac"
Output: "a"
```

Constraints:

• `1 <= s.length <= 1000`
• `s` consist of only digits and English letters (lower-case and/or upper-case),

The Solution:

```var longestPalindrome = function(s) {
let n = s.length, left = 0, right = 0, maxLen = -56
for(let i = 0 ; i < n; i++){
let len1 = expand(i,i,s)
let len2 = expand(i,i+1,s)
// console.log( "len1 " + len1 + " len2 " + len2)
let len =Math.max(len1,len2)
if(maxLen < len){
maxLen = len
//case when the palindrome has an even no of characters
if(maxLen % 2 == 0){
//we need to add 1 to i to account for the fact that even-palindrome has 2 characters at the middle, we need to add 1 to i to make it similar to the case when the palindrome has an odd no of characters. This way, when we divide maxLen by 2, we get correct distance of the start of the string from the middle
left = i +1 - Math.floor(maxLen/2)
right = i + Math.floor(maxLen/2) + 1
} else {
left = i - Math.floor(maxLen/2)
right = i + Math.floor(maxLen/2) + 1
}
}
}
//console.log(maxLen + " left " + left)
return s.substr(left,right - left )
function expand(left,right,s){
if(s.length == 0){
return 0
}
while(left >=0 && right < s.length && s[left] == s[right]){
left--
right++
}
return right - left -1
}
};```
Categories

## 214. Shortest Palindrome Leetcode Javascript Solution

The Problem:

Given a string s, you can convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

```Input: s = "aacecaaa"
Output: "aaacecaaa"
```

Example 2:

```Input: s = "abcd"
Output: "dcbabcd"
```

Constraints:

• `0 <= s.length <= 5 * 104`
• `s` consists of lowercase English letters only.

The Solution:

We create a reverse string rev of string s. We know that the part of string s from 0,n-i that is equal to the part of string rev from i to the end is a palindrome. We then just need to append the remaining part of string rev and append it to string s to arrive at the answer.

```var shortestPalindrome = function(s) {
let rev = s.split('').reverse().join('')
//console.log(rev)
let n = s.length
for(let i = 0 ; i < n; i++){
if(s.substr(0,n-i) == rev.substr(i)){
return rev.substr(0,i) + s
}
}
return ''
};```
Categories

## 980. Unique Paths III Leetcode Javascript Solution

The Problem:

On a 2-dimensional `grid`, there are 4 types of squares:

• `1` represents the starting square.  There is exactly one starting square.
• `2` represents the ending square.  There is exactly one ending square.
• `0` represents empty squares we can walk over.
• `-1` represents obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

Example 1:

```Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)```

Example 2:

```Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)```

Example 3:

```Input: [[0,1],[2,0]]
Output: 0
Explanation:
There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.
```

Note:

1. `1 <= grid.length * grid[0].length <= 20`

The Solution

We’ll need to rely on backtracking and DFS to solve this problem

```var uniquePathsIII = function(grid) {
let empties = 0, res = 0, start, end
for(let i = 0; i < grid.length; i ++){
for(let j = 0; j < grid[0].length; j++){
if(grid[i][j] == 0){
empties++
} else if (grid[i][j] == 1){
start = i
end = j
}
}
}
function  dfs(i,j,grid,count){
if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == -1 ){
return
}
if(grid[i][j] == 1 && count > 0){
return
}
if(grid[i][j] == 2){
//  console.log(count)
if( empties == count){
res++
}
return
}
if(grid[i][j] == 0){
count++
// let step = grid[i][j]
grid[i][j] = -1
}
dfs(i-1,j,grid,count)
dfs(i,j-1,grid,count)
dfs(i+1,j,grid,count)
dfs(i,j+1,grid,count)
if(grid[i][j] == -1){
count--
grid[i][j] = 0
}
}
dfs(start,end,grid,0)
return res
};```
Categories

## 212. Word Search II Leetcode Javascript Solution

The Problem:

Given an `m x n` `board` of characters and a list of strings `words`, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

```Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
```

Example 2:

```Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
```

Constraints:

• `m == board.length`
• `n == board[i].length`
• `1 <= m, n <= 12`
• `board[i][j]` is a lowercase English letter.
• `1 <= words.length <= 3 * 104`
• `1 <= words[i].length <= 10`
• `words[i]` consists of lowercase English letters.
• All the strings of `words` are unique.

The Solution:

We will use the Trie data structure to store all the words for faster and easier lookup. Then to search for all the words on the board, we’ll use depth-first search and backtracking.

```var findWords = function(board, words) {
let res = []
function buildTrie(words){
let root = {}
for(let word of words){
let node = root
for (let c of word.split('')){
if(!node[c]) node[c] = {}
node = node[c]
}
node.word = word
}
return root
}
let root = buildTrie(words)
//console.log(JSON.stringify(root))
function dfs(board,i,j,root,res){
if(root.word){
console.log(root.word)
res.push(root.word)
root.word = null
}
if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || !root[board[i][j]]){
return false
}
let c = board[i][j]
board[i][j] = ""
let result = dfs(board,i-1, j, root[c],res) || dfs(board,i, j-1, root[c],res) || dfs(board,i+1, j, root[c],res) || dfs(board,i, j+1, root[c],res)
board[i][j] = c
return result
}
for(let i = 0 ; i < board.length; i++){
for(let j = 0 ; j < board[0].length; j++){
dfs(board,i, j, root,res)
}
}
return res
};```
Categories

## 208. Implement Trie (Prefix Tree) Leetcode Javascript Solution

The Problem:

Implement a trie with `insert``search`, and `startsWith` methods.

Example:

```Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app");     // returns true
```

Note:

• You may assume that all inputs are consist of lowercase letters `a-z`.
• All inputs are guaranteed to be non-empty strings.

The Solution:

```/**
* Initialize your data structure here.
*/
var Trie = function() {
this.root = {}
};
/**
* Inserts a word into the trie.
* @param {string} word
* @return {void}
*/
Trie.prototype.insert = function(word) {
let node = this.root;
let chars = word.split('')
for(let char of chars){
if (!node[char]) node[char] = {};
node = node[char];
}
node.isEnd = true
};
/**
* Returns if the word is in the trie.
* @param {string} word
* @return {boolean}
*/
Trie.prototype.search = function(word) {
let node = this.traverse(word)
return  node !== true ? false : true
};
Trie.prototype.traverse =  function(word){
let node = this.root
for(let char of word.split('')){
if(node[char]){
node = node[char]
} else {
return null
}
}
return node.isEnd == true
}
/**
* Returns if there is any word in the trie that starts with the given prefix.
* @param {string} prefix
* @return {boolean}
*/
Trie.prototype.startsWith = function(prefix) {
let node = this.traverse(prefix)
return  node == null ? false : true
};
/**
* Your Trie object will be instantiated and called as such:
* var obj = new Trie()
* obj.insert(word)
* var param_2 = obj.search(word)
var test = new Trie()
test.insert("haha")
test.insert("hihi")
console.log(JSON.stringify(test))
* var param_3 = obj.startsWith(prefix)
*/```
Categories

## 1771. Maximize Palindrome Length From Subsequences Leetcode Javascript Solution

The problem:

You are given two strings, `word1` and `word2`. You want to construct a string in the following manner:

• Choose some non-empty subsequence `subsequence1` from `word1`.
• Choose some non-empty subsequence `subsequence2` from `word2`.
• Concatenate the subsequences: `subsequence1 + subsequence2`, to make the string.

Return the length of the longest palindrome that can be constructed in the described manner. If no palindromes can be constructed, return `0`.

subsequence of a string `s` is a string that can be made by deleting some (possibly none) characters from `s` without changing the order of the remaining characters.

palindrome is a string that reads the same forward as well as backward.

Example 1:

```Input: word1 = "cacb", word2 = "cbba"
Output: 5
Explanation: Choose "ab" from word1 and "cba" from word2 to make "abcba", which is a palindrome.```

Example 2:

```Input: word1 = "ab", word2 = "ab"
Output: 3
Explanation: Choose "ab" from word1 and "a" from word2 to make "aba", which is a palindrome.```

Example 3:

```Input: word1 = "aa", word2 = "bb"
Output: 0
Explanation: You cannot construct a palindrome from the described method, so return 0.```

Constraints:

• `1 <= word1.length, word2.length <= 1000`
• `word1` and `word2` consist of lowercase English letters.

## The solution:

Dynamic Programming Approach: (100% time and space)

```var longestPalindrome = function(word1, word2) {
let s = word1 + word2
let ans = 0
// console.log(s)
let dp = new Array(s.length).fill(0).map(el => new Array(s.length).fill(0));
for(let i = 0 ; i < s.length; i++){
dp[i][i] = 1
}
for(let l = 2; l <= s.length; l++){
for(let i = 0; i < s.length - l +1; i++){
let j = i+l-1
if(l==2){
if(s[i]== s[j]){
dp[i][j] = 2
if(i < word1.length && j >= word1.length){
ans = Math.max(ans, dp[i][j])
}
} else {
dp[i][j] = 1
}
} else {
if(s[i]== s[j]){
dp[i][j] = dp[i+1][j-1] + 2
if(i < word1.length && j >= word1.length){
ans = Math.max(ans, dp[i][j])
}
} else {
dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j])
}
}
}
}
return ans
};```
Categories

## 1769. Minimum Number of Operations to Move All Balls to Each Box Leetcode Javascript Solution

The Problem:

You have `n` boxes. You are given a binary string `boxes` of length `n`, where `boxes[i]` is `'0'` if the `ith` box is empty, and `'1'` if it contains one ball.

In one operation, you can move one ball from a box to an adjacent box. Box `i` is adjacent to box `j` if `abs(i - j) == 1`. Note that after doing so, there may be more than one ball in some boxes.

Return an array `answer` of size `n`, where `answer[i]` is the minimum number of operations needed to move all the balls to the `ith` box.

Each `answer[i]` is calculated considering the initial state of the boxes.

Example 1:

```Input: boxes = "110"
Output: [1,1,3]
Explanation: The answer for each box is as follows:
1) First box: you will have to move one ball from the second box to the first box in one operation.
2) Second box: you will have to move one ball from the first box to the second box in one operation.
3) Third box: you will have to move one ball from the first box to the third box in two operations, and move one ball from the second box to the third box in one operation.
```

Example 2:

```Input: boxes = "001011"
Output: [11,8,5,4,3,4]```

Constraints:

• `n == boxes.length`
• `1 <= n <= 2000`
• `boxes[i]` is either `'0'` or `'1'`.

The Solution:

This is a brute-force solution, but surprisingly, it passed all test cases and Leetcode said it’s faster than 100% of all Javascript submissions.

```var minOperations = function(boxes) {
let ans =[]
boxes =  boxes.split('').map(a => Number(a))
// console.log(boxes)
let n = boxes.length-1
for(let i = n; i >= 0; i--){
let count = 0
for(let j = n; j >= 0 ; j--){
if(boxes[j] == 1 && i !== j){
count += Math.abs(i-j)
}
}
ans[i] = count
}
return ans
};```