Data Structures In JavaScript

Leetcode Problems

2. Add Two Numbers

Problem:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution:

Mind the last carry.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
let addTwoNumbers = function(l1, l2) {
  const prehead = new ListNode()
  let p = prehead
  let carry = 0
  
  for (let p1 = l1, p2 = l2: p1 || p2 || carry > 0; p = p.next) {
    let sum = carry
    if (p1) {
      sum += p1.val
      p1 = p1.next
    }
    if (p2) {
      sum += p2.val
      p2 = p2.next
    }
    carry = sum / 10 | 0
    p.next = new ListNode(sum % 10)
  }
  
  return prehead.next
};

Template generated via Leetmark.

4. Median of Two Sorted Arrays

Problem:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution:

O(log (m+n)) means half of the sequence is ruled out on each loop. So obviously we need binary search.

To do it on two sorted arrays, we need a formula to guide division.

Let nums3 be the sorted array combining all the items in nums1 and nums2.

If nums2[j-1] <= nums1[i] <= nums2[j], then we know nums1[i] is at num3[i+j]. Same goes nums1[i-1] <= nums2[j] <= nums1[i].

Let k be ⌊(m+n-1)/2⌋. We need to find nums3[k] (and also nums3[k+1] if m+n is even).

Let i + j = k, if we find nums2[j-1] <= nums1[i] <= nums2[j] or nums1[i-1] <= nums2[j] <= nums1[i], then we got k.

Otherwise, if nums1[i] <= nums2[j] then we know nums1[i] < nums2[j-1] (because we did not find k).

There are i items before nums1[i], and j-1 items brefor nums2[j-1], which means nums1[0...i] are before nums3[i+j-1]. So we now know nums1[0...i] < nums3[k]. They can be safely discarded.
We Also have nums1[i] < nums2[j], which means nums2[j...n) are after nums3[i+j]. So nums2[j...n) > nums3[k].

Same goes nums1[i-1] <= nums2[j] <= nums1[i].

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
let findMedianSortedArrays = function (nums1, nums2) {
  const mid = (nums1.length + nums2.length - 1) / 2 | 0

  if ((nums1.length + nums2.length) % 2 === 0) {
    return (_find(nums1, nums2, mid) + _find(nums1, nums2, mid + 1)) / 2
  }

  return _find(nums1, nums2, mid)
}


function _find (nums1, nums2, k) {
  if (nums1.length > nums2.length) {
    // So that the `i` below is always smalller than k,
    // which makes `j` always non-negative
    [nums1, nums2] = [nums2, nums1]
  }
  let s1 = 0
  let s2 = 0
  let e1 = nums1.length
  let e2 = nums2.length

  while (s1 < e1 || s2 < e2) {
    const i = s1 + ((e1 - s1) / 2 | 0)
    const j = k - i
    const ni = i >= e1 ? Infinity : nums1[i]
    const nj = j >= e2 ? Infinity : nums2[j]
    const ni_1 = i <= 0 ? -Infinity : nums1[i-1]
    const nj_1 = j <= 0 ? -Infinity : nums2[j-1]

    if (nj_1 <= ni && ni <= nj) {
      return ni
    }

    if (ni_1 <= nj && nj <= ni) {
      return nj
    }

    if (ni <= nj) {
      s1 = i + 1
      e2 = j
    } else {
      s2 = j + 1
      e1 = i
    }
  }
};

Template generated via Leetmark.

6. ZigZag Conversion

Problem:

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

Solution:

Squeeze the zigzag pattern horizontally to form a matrix. Now deal with the odd and even columns respectively.

For example let numRows be 5, if we list out the indecies:

row
 1    00    08    16
 2    01 07 09 15 17
 3    02 06 10 14 18
 4    03 05 11 13 19
 5    04    12    20

First calculate the matrix width:

pairs = floor( len(s) / (numRows + numRows - 2) )
width = pairs * 2 + ceil( (len(s) - pairs * (numRows + numRows - 2)) / numRows )

We can easily make a observation that the direction of odd and even columns and different.

Let the first column be index 0 and let i be the current position at column col.

We need to count the items between matrix[row][col] and matrix[row][col+1], exclusive.

next_i = i + (numRows - row) + (numRows - row), if col is even && 1 < row < numRows
next_i = i + row - 2 + row, if col is odd && 1 < row < numRows

If row == 1 or row == numRows, skip the odd columns.

next_i = i + numRows + (numRows - 2), if col is even && (row == 1 || row == numRows)

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
let convert = function(s, numRows) {
  if (numRows <= 1) { return s }

  const pairs = Math.floor(s.length / (numRows + numRows - 2))
  const width = pairs * 2 + Math.ceil((s.length - pairs * (numRows + numRows - 2)) / numRows)

  let result = ''

  for (let row = 1; row <= numRows; row++) {
    let i = row - 1
    result += s[i] || ''
    for (let col = 0; col < width; col++) {
      if (row === 1 || row === numRows) {
        if (col % 2 === 0) {
          i += numRows + (numRows - 2)
        } else {
          continue
        }
      } else {
        if (col % 2 === 0) {
          i += (numRows - row) + (numRows - row)
        } else {
          i += row - 2 + row
        }
      }
      result += s[i] || ''
    }
  }

  return result
};

Template generated via Leetmark.

7. Reverse Integer

Problem:

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

Note: Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Solution:

ONE

This is a JavaScript specific solution. It is esay to write but slow to run because it generates O(n) space. This could end up a huge array.

/**
 * @param {number} x
 * @return {number}
 */
let reverse = function(x) {
  let n = Math.abs(x).toString().split('').reverse().join('')
  if (n > 2147483647) { return 0 }
  return (x < 0? -1: 1) * n
};

TWO

Pure mathamatical solution.

/**
 * @param {number} x
 * @return {number}
 */
let reverse = function(x) {
  let result = 0
  while (x) {
    result = result * 10 + x % 10
    x = x / 10 | 0
  }
  return Math.abs(result) > 2147483647 ? 0 : result
};

Template generated via Leetmark.

8. String to Integer (atoi)

Problem:

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

Only the space character ' ' is considered as whitespace character. Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Example 1:

Input: "42"
Output: 42

Example 2:

Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.

Example 3:

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Example 4:

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

Solution:

ONE

/**
 * @param {string} str
 * @return {number}
 */
let myAtoi = function (str) {
  return Math.min(2147483647, Math.max(-2147483648, parseInt(str))) || 0
};

TWO

Looks like Number() is faster than parseInt().

/**
 * @param {string} str
 * @return {number}
 */
let myAtoi = function (str) {
  return Math.min(2147483647, Math.max(-2147483648, (/^ *[-+]?\d+/.exec(str) || [0])[0]))
};

THREE

General solution.

/**
 * @param {string} str
 * @return {number}
 */
let myAtoi = function (str) {
  let sign = 1
  let i = 0

  while (i < str.length) {
    const cc = str.charCodeAt(i++)
    if (cc === 45) { // -
      sign = -1
      break
    } else if (cc === 43) { // +
      break
    } else if (cc >= 48 && cc <= 57) { // 0-9
      i--
      break
    } else if (cc !== 32) { // space
      return 0
    }
  }

  let result = 0
  while (i < str.length) {
    const digit = str.charCodeAt(i++) - 48
    if (digit < 0 || digit > 9) {
      break
    }
    result = result * 10 + digit
  }

  return Math.min(2147483647, Math.max(-2147483648, result * sign))
};

Template generated via Leetmark.

9. Palindrome Number

Problem:

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

Solution:

ONE

Easy to write but slow since it generates an array.

/**
 * @param {number} x
 * @return {boolean}
 */
let isPalindrome = function(x) {
  return x == String(x).split('').reverse().join('')
};

TWO

A bit faster.

/**
 * @param {number} x
 * @return {boolean}
 */
let isPalindrome = function(x) {
  const s = String(x)
  for (let i = 0, j = s.length -1; i < j; i++, j--) {
    if (s[i] !== s[j]) {
      return false
    }
  }
  return true
};

THREE

General solution. Combining 7. Reverse Integer.

/**
 * @param {number} x
 * @return {boolean}
 */
let isPalindrome = function(x) {
  if (x < 0) { return false }
  return x === reverse(x)
};

/**
 * @param {number} x
 * @return {number}
 */
function reverse (x) {
  let result = 0
  while (x) {
    result = result * 10 + x % 10
    x = x / 10 | 0
  }
  return result
};

Template generated via Leetmark.

10. Regular Expression Matching

Problem:

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

Solution:

ONE

Cheating with real RegExp matching.

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
let isMatch = function(s, p) {
  if (p[0] === '*') { return false }
  return new RegExp(`^${p}$`).test(s)
};

TWO

Let f(i, j) be the matching result of s[0...i) and p[0...j).

f(0, j) =
    j == 0 || // empty
    p[j-1] == '*' && f(i, j-2) // matches 0 time, which matches empty string
    
f(i, 0) = false // pattern must cover the entire input string

f(i, j) = 
    if p[j-1] == '.'
        f(i-1, j-1)
    else if p[j-1] == '*'
        f(i, j-2) || // matches 0 time
        f(i-1, j) && (s[i-1] == p[j-2] || p[j-2] == '.') // matches 1 or multiple times
    else
        f(i-1, j-1) && s[i-1] == p[j-1]

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
let isMatch = function(s, p) {
  if (p[0] === '*') {
    return false
  }

  const dp = [[true]]

  for (let j = 2; j <= p.length; j++) {
    dp[0][j] = p[j-1] === '*' && dp[0][j-2]
  }
    
  for (let i = 1; i <= s.length; i++) {
    dp[i] = []
    for (let j = 1; j <= p.length; j++) {
      switch (p[j-1]) {
        case '.':
          dp[i][j] = dp[i-1][j-1]
          break
        case '*':
          dp[i][j] = dp[i][j-2] ||
            dp[i-1][j] && (p[j-2] === '.' || s[i-1] === p[j-2])
          break
        default:
          dp[i][j] = dp[i-1][j-1] && s[i-1] === p[j-1]
      }
    }
  }

  return !!dp[s.length][p.length]
}

Template generated via Leetmark.

11. Container With Most Water

Problem:

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

Solution:

Greedy Algorithm.

If we look at the simple brute force approach, where we choose one point at a time and calculate all the possible areas with other points on the right, it is easy to make a observation that we are narrowing down the horizontal distance.

Greedy Algorithm can help us skip some of the conditions. It is base on a fact that the area between two columns are determined by the shorter one.

Let's say we have pointer l and r at the begin and end of a distance, and the area is area(l, r), how should we narrow down the distance?

If height[l] < height[r], we know that the height of the area will never be greater than height[l] if we keep l. Now if we get rid of r, the area can only get smaller since the distance is shorter, and the height is at most height[l].

Here we conclude rule NO.1: Get rid of the smaller one.

What if height[l] == height[r]? It is safe to get rid of both. We do not need any of them to constrain the max height of the rest points.

/**
 * @param {number[]} height
 * @return {number}
 */
let maxArea = function (height) {
  let max = 0
  for (let l = 0, r = height.length - 1; l < r; l++, r--) {
    max = Math.max(max, (r - l) * Math.min(height[l], height[r]))
    if (height[l] < height[r]) {
      r++
    } else {
      l--
    }
  }
  return max
};

Template generated via Leetmark.

12. Integer to Roman

Problem:

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: 3
Output: "III"

Example 2:

Input: 4
Output: "IV"

Example 3:

Input: 9
Output: "IX"

Example 4:

Input: 58
Output: "LVIII"
Explanation: C = 100, L = 50, XXX = 30 and III = 3.

Example 5:

Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Solution:

Treat 4, 40, 400 and 9, 90, 900 specially.

/**
 * @param {number} num
 * @return {string}
 */
let intToRoman = function(num) {
  const e = [1000, 900,  500, 400,  100, 90,   50,  40,   10,  9,    5,   4,    1  ]
  const s = ["M",  "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]

  let result = ''
  for (let i = 0; num; i++) {
    const d = e[i]
    const v = s[i]
    while (num >= d) {
      num -= d
      result += v
    }
  }
  return result
};

Template generated via Leetmark.

13. Roman to Integer

Problem:

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: C = 100, L = 50, XXX = 30 and III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Solution:

Normally we just add up the digits, except when the digit is greater than its left (e.g. IV). In that case we need to fallback and remove the last digit then combine the two as new digit. That is why we subtract the last digit twice.

/**
 * @param {string} s
 * @return {number}
 */
let romanToInt = function (s) {
  const rdigit = {
    I: 1,
    V: 5,
    X: 10,
    L: 50,
    C: 100,
    D: 500,
    M: 1000,
  }

  let result = 0
  for (let i = 0, lastDigit = Infinity; i < s.length; i++) {
    let digit = rdigit[s[i]]
    result += digit <= lastDigit ? digit : digit - lastDigit * 2
    lastDigit = digit
  }
  return result
};

Template generated via Leetmark.

14. Longest Common Prefix

Problem:

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Solution:

ONE

JavaScript specific solution. Get the min len then narrow down the prefix.

/**
 * @param {string[]} strs
 * @return {string}
 */
let longestCommonPrefix = function (strs) {
  if (strs.length > 0) {
    let minLen = Math.min(...strs.map(s => s.length))
    const anyStr = strs[0]
    while (minLen) {
      const prefix = anyStr.slice(0, minLen--)
      if (strs.every(s => s.startsWith(prefix))) {
        return prefix
      }
    }
  }
  return ''
};

TWO

/**
 * @param {string[]} strs
 * @return {string}
 */
let longestCommonPrefix = function(strs) {
  if (strs.length <= 0) { return '' }
  
  let i = 0
  while (strs.every(s => s[i] && s[i] === strs[0][i])) {
    i++
  }
  return strs[0].slice(0, i)
};

THREE

General solution. Build up the prefix.

/**
 * @param {string[]} strs
 * @return {string}
 */
let longestCommonPrefix = function (strs) {
  let prefix = ''
  if (strs.length > 0) {
    for (let i = 0; ; i++) {
      const c = strs[0][i]
      if (!c) { return prefix }
      for (let j = 0; j < strs.length; j++) {
        if (strs[j][i] !== c) {
          return prefix
        }
      }
      prefix += c
    }
  }
  return prefix
};

Template generated via Leetmark.

15. 3Sum

Problem:

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution:

To simplify the problem, sort the nums first.

If sorted[0] > 0 or sorted[last] < 0, return an empty set.

From i = 0 to len(sorted) - 2, pick sorted[i] as the first number of a possible triplet result.

Let l = i + 1, r = len(sorted) - 1, we want to narrow them down to enumerate all possible combinations.

l++ if sorted[i] + sorted[l] + sorted[r] > 0.
r-- if sorted[i] + sorted[l] + sorted[r] < 0.

Skip any duplicate number as we iterate to avoid duplicate triplets.

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
let threeSum = function (nums) {
  const len = nums.length
  const sorted = nums.sort((a, b) => a - b)
  const result = []

  if (sorted[0] > 0 || sorted[len-1] < 0) {
    return result
  }

  for (let i = 0; i < len - 2; i++) {
    if (sorted[i] > 0) {
      break
    }

    if (i > 0 && sorted[i] === sorted[i-1]) {
      continue
    }

    const twoSum = 0 - sorted[i]

    for (let l = i + 1, r = len - 1; l < r;) {
      const diff = twoSum - sorted[l] - sorted[r]
      if (diff > 0) {
        l++
      } else if (diff < 0) {
        r--
      } else {
        result.push([sorted[i], sorted[l], sorted[r]])
        while (++l < r && sorted[l] === sorted[l - 1]);
        while (--r > l && sorted[r] === sorted[r + 1]);
      }
    }
  }

  return result
};

Template generated via Leetmark.

16. 3Sum Closest

Problem:

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Solution:

Simplified version of 15. 3Sum.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
let threeSumClosest = function(nums, target) {
  const len = nums.length
  const sorted = nums.sort((a, b) => a - b)

  let minDiff = Infinity

  for (let i = 0; i < len - 2; i++) {
    if (i > 0 && sorted[i] === sorted[i-1]) {
      continue
    }

    const twoSum = target - sorted[i]

    for (let l = i + 1, r = len - 1; l < r;) {
      const diff = twoSum - sorted[l] - sorted[r]
      if (diff === 0) {
        return target
      } else {
        if (diff > 0) {
          l++
        } else {
          r--
        }

        if (Math.abs(diff) < Math.abs(minDiff)) {
          minDiff = diff
        }
      }
    }
  }

  return target - minDiff
};

Template generated via Leetmark.

17. Letter Combinations of a Phone Number

Problem:

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution:

ONE

JavaScript specific optimization.

Array.prototype.push accepts arbitrary arguments which enables tighter loops.

Also, appending string is faster than prepending.

/**
 * @param {string} digits
 * @return {string[]}
 */
let letterCombinations = function(digits) {
  if (digits.length <= 0) { return [] }

  const letters = [
    ,
    ,
    ['a', 'b', 'c'],
    ['d', 'e', 'f'],
    ['g', 'h', 'i'],
    ['j', 'k', 'l'],
    ['m', 'n', 'o'],
    ['p', 'q', 'r', 's'],
    ['t', 'u', 'v'],
    ['w', 'x', 'y', 'z'],
  ]

  let result = ['']

  for (let i = 0; i < digits.length; i++) {
    const arr = letters[digits[i]]
    let newResult = []
    arr.forEach(c => newResult.push(...result.map(r => r + c)))
    result = newResult
  }

  return result
};

TWO

General recursive DFS solution.

/**
 * @param {string} digits
 * @return {string[]}
 */
let letterCombinations = function(digits) {
  const letters = [,, 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
  const result = []
  if (digits.length > 0) {
    dfs(digits, 0, '', letters, result)
  }
  return result
};

function dfs (digits, idigit, path, letters, result) {
  if (idigit >= digits.length) {
    result.push(path)
    return
  }
  const str = letters[digits[idigit]]
  for (let i = 0; i < str.length; i++) {
    dfs(digits, idigit + 1, path + str[i], letters, result)
  }
};

Template generated via Leetmark.

18. 4Sum

Problem:

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Solution:

Like 15. 3Sum and 16. 3Sum Closest. Wrap one more loop.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
let fourSum = function(nums, target) {
  const len = nums.length
  const sorted = nums.sort((a, b) => a - b)
  const result = []

  for (let k = 0; k < len - 3; k++) {
    if (k > 0 && sorted[k] === sorted[k-1]) {
      continue
    }

    const threeSum = target - sorted[k]

    for (let i = k+1; i < len - 2; i++) {
      if (i > k+1 && sorted[i] === sorted[i-1]) {
        continue
      }

      const twoSum = threeSum - sorted[i]

      for (let l = i + 1, r = len - 1; l < r;) {
        const diff = twoSum - sorted[l] - sorted[r]
        if (diff > 0) {
          l++
        } else if (diff < 0) {
          r--
        } else {
          result.push([sorted[k], sorted[i], sorted[l], sorted[r]])
          while (++l < r && sorted[l] === sorted[l - 1]);
          while (--r > l && sorted[r] === sorted[r + 1]);
        }
      }
    }
  }

  return result
};

Template generated via Leetmark.

19. Remove Nth Node From End of List

Problem:

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Solution:

Set a pointer p1 for iterating, and p2 which is n nodes behind, pointing at the (n+1)-th node from the end of list.

Boundaries that should be awared of:

p2 could be one node before head, which means the head should be removed.
p2 could be larger than the length of the list (Though the description says n will always be valid, we take care of it anyway).
It should be p1.next touches the end rather than p1 because we want p1 pointing at the last node.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
let removeNthFromEnd = function(head, n) {
  let p1 = head
  while (p1 && n--) {
    p1 = p1.next
  }

  if (!p1) { return n ? head : head.next }

  let p2 = head
  while (p1.next) {
    p1 = p1.next
    p2 = p2.next
  }

  p2.next = p2.next.next

  return head
};

Template generated via Leetmark.

20. Valid Parentheses

Problem:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Solution:

Stack 101.

Whenever we meet a close bracket, we want to compare it to the last open bracket.

That is why we use stack to store open brackets: first in, last out.

And since there is only bracket characters, the last open bracket happens to be the last character.

/**
 * @param {string} s
 * @return {boolean}
 */
let isValid = function(s) {
  const stack = []
  const pairs = {
    '}': '{',
    ']': '[',
    ')': '(',
  }
  for (const c of s) {
    const open = pairs[c]
    if (open) {
      if (stack.pop() !== open) {
        return false
      }
    } else {
      stack.push(c)
    }
  }
  return stack.length <= 0
};

Template generated via Leetmark.

21. Merge Two Sorted Lists

Problem:

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Solution:

Keep tracking the head of two lists and keep moving the pointer of smaller one to the next node.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
let mergeTwoLists = function(l1, l2) {
  let prehead = { next: null }
  let p = prehead
  let p1 = l1
  let p2 = l2
  while (p1 && p2) {
    let pSel
    if  (p1.val < p2.val) {
      pSel = p1
      p1 = p1.next
    } else {
      pSel = p2
      p2 = p2.next
    }
    p.next = pSel
    p = pSel
  }

  p.next = p1 || p2

  return prehead.next
};

Template generated via Leetmark.

22. Generate Parentheses

Problem:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution:

ONE

Recursive DFS backtracking.

/**
 * @param {number} n
 * @return {string[]}
 */
let generateParenthesis = function(n) {
  const result = []
  if (n > 0) {
    dfs(n, 0, 0, '', result)
  }
  return result
};

function dfs (n, nopen, nclose, path, result) {
  if (path.length === n * 2) {
    result.push(path)
    return
  }

  if (nopen < n) {
    dfs(n, nopen + 1, nclose, path + '(', result)
  }

  if (nclose < nopen) {
    dfs(n, nopen, nclose + 1, path + ')', result)
  }
};

TWO

BFS.

/**
 * @param {number} n
 * @return {string[]}
 */
let generateParenthesis = function(n) {
  if (n <= 0) { return [] }

  const queue = [{
    path: '(',
    open: 1,
    close: 0,
  }]

  while (true) {
    const { path, open, close } = queue.shift()
    if (open + close === n * 2) {
      queue.unshift({ path, open, close })
      break
    }

    if (open < n) {
      queue.push({
        path: path + '(',
        open: open + 1,
        close,
      })
    }

    if (close < open) {
      queue.push({
        path: path + ')',
        open,
        close: close + 1,
      })
    }
  }

  return queue.map(x => x.path)
};

Template generated via Leetmark.

23. Merge k Sorted Lists

Problem:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solution:

ONE

Extend the idea of 21. Merge Two Sorted Lists and compare N items at a time.

This is slow as it reaches O(N^2).

TWO

Priority Queue. O(N * log(K)).

Since JavaScript does not provide a standard built-in Priority Queue data structure, it is challenging to implement an efficient one barehanded.

THREE

Divide and conquer. Also O(N * log(K)).

Divide N lists into ceil(N/2) pairs and merge your way up.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
let mergeKLists = function(lists) {
  while (lists.length > 1) {
    lists.unshift(mergeTwoLists(lists.pop(), lists.pop()))
  }
  return lists[0] || []
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
function mergeTwoLists (l1, l2) {
  let prehead = { next: null }
  let p = prehead
  let p1 = l1
  let p2 = l2
  while (p1 && p2) {
    let pSel
    if  (p1.val < p2.val) {
      pSel = p1
      p1 = p1.next
    } else {
      pSel = p2
      p2 = p2.next
    }
    p.next = pSel
    p = pSel
  }

  p.next = p1 || p2

  return prehead.next
};

Template generated via Leetmark.

24. Swap Nodes in Pairs

Problem:

Given a linked list, swap every two adjacent nodes and return its head.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

Note:

Your algorithm should use only constant extra space.
You may not modify the values in the list's nodes, only nodes itself may be changed.

Solution:

Draw the nodes down on paper to reason about the relationships.
Pointing to every active node is an easy way to keep on track.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
let swapPairs = function(head) {
  const prehead = { next: head }

  for (let p = prehead; p.next !== null && p.next.next !== null;) {
    const p1 = p.next
    const p2 = p1.next
    p1.next = p2.next
    p2.next = p1
    p.next = p2
    p = p1
  }

  return prehead.next
};

Template generated via Leetmark.

25. Reverse Nodes in k-Group

Problem:

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

Only constant extra memory is allowed.
You may not alter the values in the list's nodes, only nodes itself may be changed.

Solution:

Find the end node of a portion that needs to be reversed.
Get the next node of the end node.
Reverse the portion using the next node as edge(null) pointer.
Connect it back to the main linked list.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
let reverseKGroup = function(head, k) {
  const prehead = { next: head }
  let p = prehead
  while (true) {
    let n = k
    let pEndNext = p.next
    while (pEndNext && n) {
      pEndNext = pEndNext.next
      n--
    }

    if (n !== 0) {
      break
    }

    const nextp = p.next // The first node will be the last after reverse
    p.next = reverseLinkList(p.next, pEndNext)
    p = nextp
  }

  return prehead.next
};

function reverseLinkList (head, nullNode = null) {
  let prev = nullNode
  let curr = head
  while (curr !== nullNode) {
    const next = curr.next
    curr.next = prev
    prev = curr
    curr = next
  }
  return prev
};

Template generated via Leetmark.

26. Remove Duplicates from Sorted Array

Problem:

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Solution:

The result array can only be shorter. That is why we can build the array in-place with the new length.

/**
 * @param {number[]} nums
 * @return {number}
 */
let removeDuplicates = function(nums) {
  let len = 0
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== nums[i-1]) {
      nums[len++] = nums[i]
    }
  }
  return len
};

Template generated via Leetmark.

27. Remove Element

Problem:

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example 1:

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

Problem:

Solution:

Difficulty: Hard Related Topics: "Array": https://leetcode.com/tag/array "Binary Search": https://leetcode.com/tag/binary-search "Divide and Conquer": https://leetcode.com/tag/divide-and-conquer

Problem:

Solution:

Difficulty: Medium Related Topics: "String": https://leetcode.com/tag/string

Problem:

Solution:

Difficulty: Easy Related Topics: "Math": https://leetcode.com/tag/math Similar Questions: "String to Integer (atoi)": https://leetcode.com/problems/string-to-integer-atoi

Problem:

Solution:

Difficulty: Medium Related Topics: "Math": https://leetcode.com/tag/math "String": https://leetcode.com/tag/string Similar Questions: "Reverse Integer": https://leetcode.com/problems/reverse-integer "Valid Number": https://leetcode.com/problems/valid-number

Problem:

Solution:

Difficulty: Easy Related Topics: "Math": https://leetcode.com/tag/math Similar Questions: "Palindrome Linked List": https://leetcode.com/problems/palindrome-linked-list

Problem:

Solution:

Difficulty: Hard Related Topics: "String": https://leetcode.com/tag/string "Dynamic Programming": https://leetcode.com/tag/dynamic-programming "Backtracking": https://leetcode.com/tag/backtracking Similar Questions: "Wildcard Matching": https://leetcode.com/problems/wildcard-matching

Problem:

Solution:

Difficulty: Medium Related Topics: "Array": https://leetcode.com/tag/array "Two Pointers": https://leetcode.com/tag/two-pointers Similar Questions: "Trapping Rain Water": https://leetcode.com/problems/trapping-rain-water

Problem:

Solution:

Difficulty: Medium Related Topics: "Math": https://leetcode.com/tag/math "String": https://leetcode.com/tag/string Similar Questions: "Roman to Integer": https://leetcode.com/problems/roman-to-integer "Integer to English Words": https://leetcode.com/problems/integer-to-english-words

Problem:

Solution:

Difficulty: Easy Related Topics: "Math": https://leetcode.com/tag/math "String": https://leetcode.com/tag/string Similar Questions: "Integer to Roman": https://leetcode.com/problems/integer-to-roman

Problem:

Solution:

Difficulty: Easy Related Topics: "String": https://leetcode.com/tag/string

Problem:

Solution:

Problem:

Solution:

Difficulty: Medium Related Topics: "Array": https://leetcode.com/tag/array "Two Pointers": https://leetcode.com/tag/two-pointers Similar Questions: "3Sum": https://leetcode.com/problems/3sum "3Sum Smaller": https://leetcode.com/problems/3sum-smaller

Problem:

Solution:

Problem:

Solution:

Problem:

Solution:

Difficulty: Medium Related Topics: "Linked List": https://leetcode.com/tag/linked-list "Two Pointers": https://leetcode.com/tag/two-pointers

Problem:

Solution:

Problem:

Solution:

Problem:

Solution:

Problem:

Solution:

Problem:

Solution:

Difficulty: Medium Related Topics: "Linked List": https://leetcode.com/tag/linked-list Similar Questions: "Reverse Nodes in k-Group": https://leetcode.com/problems/reverse-nodes-in-k-group

Problem:

Solution:

Difficulty: Hard Related Topics: "Linked List": https://leetcode.com/tag/linked-list Similar Questions: "Swap Nodes in Pairs": https://leetcode.com/problems/swap-nodes-in-pairs

Problem:

Solution:

Problem:

Solution:

Problem: