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

## 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]
//  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
};```
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
};```