Categories
Uncategorized

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
Uncategorized

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
Uncategorized

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
Uncategorized

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()
    let charsS = 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){
        if(!charsS.get(s[right])){
                    charsS.set(s[right],1)
                } else {
                    charsS.set(s[right],charsS.get(s[right])+1)
                }
        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)
            }
            //console.log(charsS)
                let c = s[left]
                if(charsS.get(c)){
                   charsS.set(c,charsS.get(c)-1)
               //  console.log("eliminated start char: ")
                 // console.log(charsS)
                   }
                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
Uncategorized

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
Uncategorized

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
Uncategorized

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.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  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
    }
     return head.next
};
Categories
Uncategorized

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
Uncategorized

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
Uncategorized

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