Categories
Uncategorized

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
Uncategorized

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
Uncategorized

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
Uncategorized

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
Uncategorized

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
Uncategorized

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

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