Categories
Uncategorized

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) {
    if(head == null) return head
let fast = head, slow = 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)
    console.log(head)
    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
    }
    return head
};
Categories
Uncategorized

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)
    dummy.next = head
    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
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

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

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