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

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
Uncategorized

208. Implement Trie (Prefix Tree) Leetcode Javascript Solution

The Problem:

Implement a trie with insertsearch, 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
Uncategorized

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
Uncategorized

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