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.
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
}
}
};
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:
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
};
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.
/**
* @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
};
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]
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
};
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
};
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 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
};
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
};
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).
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]
]
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
};
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
};
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:
// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);
// 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 order does not matter. So just take the last number to fill the vacancy.
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
let removeElement = function(nums, val) {
let len = nums.length
for (let i = 0; i < len; i++) {
if (nums[i] === val) {
nums[i--] = nums[--len]
}
}
return len
};
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero.
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Note:
Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
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 231 − 1 when the division result overflows.
Solution:
Every decimal number can be represented as a0*2^0 + a1*2^1 + a2*2^2 + ... + an*2^n.
Replace multiplication and division with binary shifting.
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1
Solution:
Observe a few longer examples and the pattern is self-evident.
Divide the list into two parts. The first half must be incremental and the second half must be decremental.
Reverse the second half and find the smallest number in it that is greater the last number of the first half.
Swap the two.
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
let nextPermutation = function(nums) {
const len = nums.length
if (len <= 1) { return }
for (let i = len - 1; i > 0; i--) {
if (nums[i] > nums[i-1]) {
let t
for (let s = i, e = len-1; s < e; s++, e--) {
t = nums[s]
nums[s] = nums[e]
nums[e] = t
}
let j = len - 1
while (nums[j] <= nums[i-1]) {
j--
}
t = nums[j]
nums[j] = nums[i-1]
nums[i-1] = t
break
}
}
if (i === 0) {
nums.reverse()
}
};
The core idea of binary search is to pick the middle item and then decide to keep which half.
The precondition of it is the array must be sorted.
But take a closer look and we realize that only one of the two halves needs to be sorted. This is sufficient for us to know if the target is in that half. If not, then it must be in the other.
Whenever we choose a pivot, it must be in one of the two sorted parts of the rotated array.
If the pivot is in the left part. We know that the begin of the left part to the pivot are sorted.
Otherwise the pivot is in the right part. We know that the end of the right part to the pivot are sorted.
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
let search = function(nums, target) {
let s = 0
let e = nums.length - 1
while (s <= e) {
const p = (e + s) / 2 | 0
const pivot = nums[p]
if (pivot === target) {
return p
}
if (pivot < nums[e]) {
// right half is sorted
if (target > pivot && target <= nums[e]) {
// target is inside the right half
s = p + 1
} else {
e = p - 1
}
} else {
// left half is sorted
if (target < pivot && target >= nums[s]) {
// target is inside the left half
e = p - 1
} else {
s = p + 1
}
}
}
return -1
};
Implement two variations of binary search to get the first and last matching positions.
They are basically the same as simple binary search except when we got the match, we mark the index and keep moving forward.
If we want to get the first, we dump the right half. Vice versa.
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
let searchRange = function(nums, target) {
let s = 0
let e = nums.length - 1
const first = searchFirst(nums, target, 0, nums.length - 1)
if (first === -1) {
return [-1, -1]
}
return [first, searchLast(nums, target, first, nums.length - 1)]
};
function searchFirst (nums, target, s, e) {
let result = -1
while (s <= e) {
const p = (s + e) / 2 | 0
const diff = nums[p] - target
if (diff === 0) {
result = p
e = p - 1
} else if (diff > 0) {
e = p - 1
} else {
s = s + 1
}
}
return result
};
function searchLast (nums, target, s, e) {
let result = -1
while (s <= e) {
const p = (s + e) / 2 | 0
const diff = nums[p] - target
if (diff === 0) {
result = p
s = p + 1
} else if (diff > 0) {
e = p - 1
} else {
s = s + 1
}
}
return result
};
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
Example 4:
Input: [1,3,5,6], 0
Output: 0
Solution:
Same as simple binary search except it returns the start index when does not find a match.
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
let searchInsert = function(nums, target) {
let s = 0
let e = nums.length - 1
while (s <= e) {
const p = (s + e) / 2 | 0
const diff = nums[p] - target
if (diff === 0) {
return p
} else if (diff < 0) {
s = p + 1
} else {
e = p - 1
}
}
return s
};
Input:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being
modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
The given board contain only digits 1-9 and the character '.'.
The given board size is always 9x9.
Solution:
Scan the board once.
/**
* @param {character[][]} board
* @return {boolean}
*/
let isValidSudoku = function(board) {
if (!board || board.length !== 9) { return false }
const newArray = () => []
const col = board.map(newArray)
const row = board.map(newArray)
const sub = board.map(newArray)
for (let r = 0; r < 9; r++) {
if (board[r].length !== 9) { return false }
for (let c = 0; c < 9; c++) {
const num = board[r][c]
const subOffset = 3 * (r / 3 | 0) + (c / 3 | 0)
if (num !== '.') {
if (!(num >= 1 && num <= 9) ||
row[r][num] ||
col[c][num] ||
sub[subOffset][num]
) {
return false
}
row[r][num] = true
col[c][num] = true
sub[subOffset][num] = true
}
}
}
return true
};
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character '.'.
Note:
The given board contain only digits 1-9 and the character '.'.
You may assume that the given Sudoku puzzle will have a single unique solution.
The given board size is always 9x9.
Solution:
DFS + backtracking.
Just like 36. Valid Sudoku but instead of validating the board with three tables, we use these three tables to get all the valid numbers at a position. This is super fast as it skips a lot of redundant comparisons.
Every time we reach a position, we pick a possible solution and move on to the next position, which is an identical problem.
If the next position fails, we come back and try the next possible solution of the current position.
If all possible solutions fail, we just dump the current position and go back to the last position.
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
let solveSudoku = function(board) {
const newArray = () => []
const col = board.map(newArray)
const row = board.map(newArray)
const sub = board.map(newArray)
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
const num = +board[r][c]
if (num) {
const subOffset = 3 * (r / 3 | 0) + (c / 3 | 0)
row[r][num] = true
col[c][num] = true
sub[subOffset][num] = true
}
}
}
dfs(board, col, row, sub, 0)
};
function dfs (board, col, row, sub, pos) {
if (pos >= 81) { return true }
const r = pos / 9 | 0
const c = pos % 9
if (board[r][c] !== '.') {
return dfs(board, col, row, sub, pos + 1)
}
const subOffset = 3 * (r / 3 | 0) + (c / 3 | 0)
for (let num = 1; num <= 9; num++) {
if (!(row[r][num] || col[c][num] || sub[subOffset][num])) {
row[r][num] = true
col[c][num] = true
sub[subOffset][num] = true
if (dfs(board, col, row, sub, pos + 1)) {
board[r][c] = num + ''
return true
} else {
row[r][num] = false
col[c][num] = false
sub[subOffset][num] = false
}
}
}
return false
};
The count-and-say sequence is the sequence of integers with the first five terms as following:
1. 1
2. 11
3. 21
4. 1211
5. 111221
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth term of the count-and-say sequence.
Note: Each term of the sequence of integers will be represented as a string.
Example 1:
Input: 1
Output: "1"
Example 2:
Input: 4
Output: "1211"
Solution:
Just loop and grow the sequence.
ONE
JavaScript specific.
/**
* @param {number} n
* @return {string}
*/
let countAndSay = function(n) {
let num = '1'
while (--n > 0) {
num = num.match(/(\d)\1*/g).map(x => x.length + x[0]).join('')
}
return num
};
TWO
General solution.
/**
* @param {number} n
* @return {string}
*/
let countAndSay = function(n) {
let num = '1'
while (--n > 0) {
let newNum = ''
for (let i = 0, accu = 1; i < num.length; i++, accu++) {
if (num[i] !== num[i+1]) {
newNum += accu + num[i]
accu = 0
}
}
num = newNum
}
return num
};
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
Solution:
DFS + Backtracking.
To prevent duplications, only loop the right side of the candidates.
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
let combinationSum = function(candidates, target) {
return dfs(candidates, target, [], [], 0)
};
function dfs (candidates, target, result, path, start) {
for (let i = start; i < candidates.length; i++) {
const cand = candidates[i]
if (cand > target) {
continue
}
path.push(cand)
if (cand === target) {
result.push(path.slice())
} else {
dfs(candidates, target - cand, result, path, i)
}
path.pop(cand)
}
return result
};
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
/**
* @param {number[]} height
* @return {number}
*/
let trap = function(height) {
let i = 0
let j = height.length - 1
let lMax = 0
let rMax = 0
let result = 0
while (i < j) {
const left = height[i]
const right = height[j]
if (left < right) {
if (left < lMax) {
result += lMax - left
} else {
lMax = left
}
i++
} else {
if (right < rMax) {
result += rMax - right
} else {
rMax = right
}
j--
}
}
return result
};
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.
Solution:
Greedy. Always pick the one that would allow to jump to the rightest.
/**
* @param {number[]} nums
* @return {number}
*/
let jump = function(nums) {
const len = nums.length
let jump = 0
for (let l = 0, r = 1; r < len; jump++) {
let rNext = r
for (let i = l; i < r; i++) {
const rNextAtmp = i + nums[i] + 1
if (rNextAtmp > rNext) {
rNext = rNextAtmp
}
}
l = r
r = rNext
}
return jump
};
Same as 46. Permutations. To avoid duplication, when picking a number for a position, only pick the unused. Either sort the nums or use a set to mark.
/**
* @param {number[]} nums
* @return {number[][]}
*/
let permuteUnique = function(nums) {
const result = []
_permuteUnique(nums, 0, result)
return result
};
function _permuteUnique (nums, start, result) {
if (start === nums.length) {
result.push(nums.slice())
}
const used = new Set()
const begin = nums[start]
for (let i = start; i < nums.length; i++) {
const next = nums[i]
if (used.has(next)) {
continue
}
used.add(next)
nums[start] = next
nums[i] = begin
_permuteUnique(nums, start + 1, result)
nums[start] = begin
nums[i] = next
}
};
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Example 2:
Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
n is a 32-bit signed integer, within the range [−231, 231 − 1]
Solution:
x^n = x^(n/2) * x^(n/2), if n is even
x^n = x^((n-1)/2) * x^((n-1)/2) * x, if n is odd
Corner cases:
n == 0
n < 0
Note here we can not use any bitwise operator, n = -2^31 might overflow.
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
let myPow = function(x, n) {
if (n === 0) { return 1 }
if (n === 1) { return x }
if (n === -1) { return 1 / x }
if (n % 2 === 0) {
const res = myPow(x, n / 2)
return res * res
}
const res = myPow(x, (n - 1) / 2)
return x * res * res
};
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
Example:
Input: 4
Output: [
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
Solution:
Allocate a n-length array queens. Each item represents a queen coordinate on the borad. Let index i be the row index, and queens[i] be the column index (or vice versa).
Now use the permutation algorithm from 46. Permutations to generate all possible queen positions, then test for diagonal.
ONE
/**
* @param {number} n
* @return {string[][]}
*/
let solveNQueens = function(n) {
const result = []
const queens = [...new Array(n)].map((_, i) => i)
_solveNQueens(queens, 0, result)
return result
};
function _solveNQueens (queens, iStart, result) {
if (iStart === queens.length) {
for (let i = 0; i < queens.length; i += 1) {
for (let j = i + 1; j < queens.length; j += 1) {
if (Math.abs(i - j) === Math.abs(queens[i] - queens[j])) {
return
}
}
}
return result.push(_genBoard(queens))
}
const start = queens[iStart]
for (let i = iStart; i < queens.length; i++) {
const next = queens[i]
queens[iStart] = next
queens[i] = start
_solveNQueens(queens, iStart + 1, result)
queens[iStart] = start
queens[i] = next
}
};
function _genBoard (queens) {
const board = []
for (let i = 0; i < queens.length; i++) {
let row = ''
for (let j = 0; j < queens.length; j++) {
row += queens[i] === j ? 'Q' : '.'
}
board.push(row)
}
return board
};
This is slow because we test diagonal in the end. We can do a tree pruning by moving it right before diving into the next recursion.
TWO
/**
* @param {number} n
* @return {string[][]}
*/
let solveNQueens = function(n) {
const result = []
const queens = [...new Array(n)].map((_, i) => i)
_solveNQueens(queens, 0, result)
return result
};
function _solveNQueens (queens, iStart, result) {
if (iStart === queens.length) {
return result.push(_genBoard(queens))
}
const start = queens[iStart]
for (let i = iStart; i < queens.length; i++) {
const next = queens[i]
queens[iStart] = next
queens[i] = start
if (_testDiagonal(queens, iStart)) {
_solveNQueens(queens, iStart + 1, result)
}
queens[iStart] = start
queens[i] = next
}
};
function _testDiagonal(queens, iStart) {
for (let i = 0; i < iStart; i++) {
if (Math.abs(queens[iStart] - queens[i]) === iStart - i) {
return false
}
}
return true
};
function _genBoard (queens) {
const board = []
for (let i = 0; i < queens.length; i++) {
let row = ''
for (let j = 0; j < queens.length; j++) {
row += queens[i] === j ? 'Q' : '.'
}
board.push(row)
}
return board
};
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.
Solution:
ONE
See 45. Jump Game II. If the range does not expand at some point, we know it is stuck.
/**
* @param {number[]} nums
* @return {boolean}
*/
let canJump = function(nums) {
for (let l = 0, r = 1; r < nums.length;) {
let rNext = r
for (let i = l; i < r; i++) {
const rNextAtmp = i + nums[i] + 1
if (rNextAtmp > rNext) {
rNext = rNextAtmp
}
}
if (rNext <= r) { return false }
l = r
r = rNext
}
return true
};
TWO
If we view it backward, and if the range of nums[n-2] covers nums[n-1], then we can safely make n-2 the new destination point, and so on.
If nums[0] can cover the last destination point, it is good.
/**
* @param {number[]} nums
* @return {boolean}
*/
let canJump = function(nums) {
let des = nums.length - 1
for (let i = des - 1; i > 0; i--) {
if (nums[i] + i >= des) {
des = i
}
}
return nums[0] >= des
};
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
Solution:
The logic of the solution is pretty straight forward. Just need to carefully think through all the edge cases. It is better to choose readability over performance.
/**
* Definition for an interval.
* function Interval(start, end) {
* this.start = start;
* this.end = end;
* }
*/
/**
* @param {Interval[]} intervals
* @param {Interval} newInterval
* @return {Interval[]}
*/
let insert = function(intervals, newInterval) {
const result = []
const p = new Interval(newInterval.start, newInterval.end)
for (let i = 0; i < intervals.length; i++) {
const { start, end } = intervals[i]
if (start > p.end) {
break
}
if (end < p.start) {
result.push(intervals[i])
continue
}
if (start < p.start) {
p.start = start
}
if (end > p.end) {
p.end = end
}
}
return [...result, p, ...intervals.slice(i)]
};
The set [1,2,3,...,*n*] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Note:
Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
Solution:
The order of the sequence is fixed hence can be calculated. We can view the process as picking digits from a sorted set [1...n].
Each digit appears (n-1)! times in result[0]. And for a fixed result[0] each digit appears (n-2)! times in result[1]. So on.
We also need k-- to convert k into index so that k <= (n-1)! maps 0 (and get 1 from the set).
/**
* @param {number} n
* @param {number} k
* @return {string}
*/
let getPermutation = function(n, k) {
const digits = []
let factorial = 1
for (let i = 1; i <= n; i++) {
digits.push(i)
factorial *= i
}
k--
let result = ''
while (n > 0) {
factorial /= n
result += digits.splice(k / factorial | 0, 1)[0]
k %= factorial
n--
}
return result
};
Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example 1:
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
Example 2:
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
Solution:
Classic two-pointers chasing except the k could be larger than the length of this list.
We first attempt to locate the right pointer while also recording the length of the list.
If we hit the end of list and still do not have the right pointer, we know k is larger than the length.
Locate the right pointer again with k % len.
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
let rotateRight = function(head, k) {
if (head === null || k <= 0) { return head }
let right = head
let len = 0
let kk = k
while (right !== null && kk > 0) {
right = right.next
kk--
len++
}
if (kk > 0) {
right = head
kk = k % len
while (kk--) {
right = right.next
}
}
if (right !== null) {
let left = head
while (right.next !== null) {
left = left.next
right = right.next
}
right.next = head
head = left.next
left.next = null
}
return head
};
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Above is a 7 x 3 grid. How many possible unique paths are there?
Note:m and n will be at most 100.
Example 1:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
Example 2:
Input: m = 7, n = 3
Output: 28
Solution:
DP.
Define f(i, j) to be the number of total unique paths from (0, 0) to (i, j).
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.
Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.
Solution:
JavaScript specific solutions:
ONE
Math.abs will first convert the argument to number.
Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
Note:
A word is defined as a character sequence consisting of non-space characters only.
Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.
The input array words contains at least one word.
Example 1:
Input:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
Output:
[
"This is an",
"example of text",
"justification. "
]
Example 2:
Input:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]
Explanation: Note that the last line is "shall be " instead of "shall be",
because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified becase it contains only one word.
Example 3:
Input:
words = ["Science","is","what","we","understand","well","enough","to","explain",
"to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
Output:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]
Solution:
Count the current line width (plus 1 space between each two words).
When a line is full:
If there is only one word, pad spaces at the end.
Otherwise calculate the gap length using Math.ceil.
Handle the last line.
/**
* @param {string[]} words
* @param {number} maxWidth
* @return {string[]}
*/
let fullJustify = function(words, maxWidth) {
let start = 0
let end = 1
let lineLen = words[start].length
const result = []
while (end < words.length) {
const newLen = words[end].length + 1 + lineLen
if (newLen <= maxWidth) {
lineLen = newLen
} else {
let line = ''
let nWords = end - start
if (nWords === 1) {
line = words[start].padEnd(maxWidth)
} else {
let nSpaces = maxWidth - (lineLen - (nWords - 1))
for (let i = start; i < end; i++) {
const gap = Math.ceil(nSpaces / (end - i - 1))
line += words[i] + ' '.repeat(gap)
nSpaces -= gap
}
}
result.push(line)
start = end
lineLen = words[start].length
}
end++
}
let lastline = words[start]
for (let i = start + 1; i < end; i++) {
lastline += ' ' + words[i]
}
result.push(lastline.padEnd(maxWidth))
return result
};
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"path = "/a/./b/../../c/", => "/c"
Corner Cases:
Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".
/**
* @param {string} path
* @return {string}
*/
let simplifyPath = function(path) {
const len = path.length
const stack = []
let e = 0
while (e < len) {
while (e < len && path[e] === '/') {
e++
}
const s = e
while (e < len && path[e] !== '/') {
e++
}
if (s < e) {
const p = path.slice(s, e)
if (p === '..') {
stack.pop()
} else if (p !== '.') {
stack.push(p)
}
}
}
return '/' + stack.join('/')
};
Given an array with n objects colored red, white or blue, sort them in-placeso that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library's sort function for this problem.
Example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with a one-pass algorithm using only constant space?
Solution:
One-pass algorithm.
Take the idea of the partition algorithm from quick sort. Use 1 as pivot.
Count the number of sorted 0s and 2s so that we know where to swap.
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
let sortColors = function(nums) {
const len = nums.length
let zeroEnd = 0
let twoStart = len - 1
let i = 0
while (i <= twoStart) {
if (nums[i] === 0 && i !== zeroEnd) {
const t = nums[i]
nums[i] = nums[zeroEnd]
nums[zeroEnd] = t
zeroEnd++
} else if (nums[i] === 2 && i !== twoStart) {
const t = nums[i]
nums[i] = nums[twoStart]
nums[twoStart] = t
twoStart--
} else {
i++
}
}
};
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
Solution:
DFS + Backtracking. Replace the cell with NaN before proceeding to the next level and restore when backtracking.
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
let exist = function(board, word) {
const height = board.length
if (height <= 0) { return false }
const width = board[0].length
if (width <= 0) { return false }
for (let row = 0; row < height; row++) {
for (let col = 0; col < width; col++) {
if (board[row][col] === word[0] &&
_exist(board, word, 0, [[-1, 0], [1, 0], [0, -1], [0, 1]], row, col)
) {
return true
}
}
}
return false
};
function _exist (board, word, iWord, directions, row, col) {
if (iWord === word.length) {
return true
}
if (!board[row] || word[iWord] !== board[row][col]) {
return false
}
const cell = board[row][col]
board[row][col] = NaN
for (let i = directions.length - 1; i >= 0; i--) {
if (_exist(board, word, iWord+1, directions, row+directions[i][0], col+directions[i][1])) {
return true
}
}
board[row][col] = cell
return false
}
Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice 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,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,0,1,1,1,1,2,3,3],
Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 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]);
}
Would this affect the run-time complexity? How and why?
Solution:
See 33. Search in Rotated Sorted Array. The code is basically the same. Except with duplicates we can not tell which way to jump when pivot == nums[e]. The only thing we can do is to ditch nums[e]. SO worst case O(*n*).
/**
* @param {number[]} nums
* @param {number} target
* @return {boolean}
*/
let search = function(nums, target) {
let s = 0
let e = nums.length - 1
while (s <= e) {
const p = (e + s) / 2 | 0
const pivot = nums[p]
if (target === pivot) {
return true
}
if (pivot < nums[e]) {
if (target > nums[p] && target <= nums[e]) {
s = p + 1
} else {
e = p - 1
}
} else if (pivot > nums[e]) {
if (target < nums[p] && target >= nums[s]) {
e = p - 1
} else {
s = p + 1
}
} else {
e--
}
}
return false
};
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
Example:
Input: [2,1,5,6,2,3]
Output: 10
Solution:
The height of a rectangle is determined by the lowest bar inside of it. So the core idea is, for each bar, assume it is the lowest bar and see how far it can expand. Then we have len(heights) rectangles. Return the max area.
For a bar b whose height is h, find the closest bar b1 on the left that is lower than h, and b2 on the right. The area of the rectangle is h * (i2 - i1 - 1).
Notice that if we just loop the bars from left to right, b1 and b2 of each bar may overlap.
index
height
width
area
i
heights[i]
i2 - i1 - 1
height * width
0
2
1 - -1 - 1
2
1
1
6 - -1 - 1
6
2
5
4 - 1 - 1
10
3
6
4 - 2 - 1
6
4
2
6 - 1 - 1
8
5
3
6 - 4 - 1
3
Observe how i1 and i2 changes depending on the height.
To reduce O(n^2) to O(n), we use a stack to store incremental bs. Because b1 and b2 are both lower than b, whenever we reach a bar that is lower than the top of the stack, we know it's a b2. So stack top is a b. Second top is a b1. Keep popping the b to calculate areas until b2 is no longer lower than stack top.
/**
* @param {number[]} heights
* @return {number}
*/
let largestRectangleArea = function(heights) {
const stack = [-1]
let max = 0
for (let i2 = 0; i2 <= heights.length; i2++) {
while ((heights[i2] || 0) < heights[stack[stack.length-1]]) {
const i = stack.pop()
const i1 = stack[stack.length-1]
max = Math.max(max, heights[i] * (i2 - i1 - 1))
}
stack.push(i2)
}
return max
};
/**
* @param {character[][]} matrix
* @return {number}
*/
let maximalRectangle = function(matrix) {
const height = matrix.length
if (height <= 0) { return 0 }
const width = matrix[0].length
if (width <= 0) { return 0 }
const heights = []
let max = 0
for (let row = 0; row < height; row++) {
for (let col = 0; col < width; col++) {
heights[col] = ((heights[col] || 0) + 1) * matrix[row][col]
}
max = Math.max(max, largestRectangleArea(heights))
}
return max
};
/**
* @param {number[]} heights
* @return {number}
*/
function largestRectangleArea (heights) {
const stack = [-1]
let max = 0
for (let i2 = 0; i2 <= heights.length; i2++) {
while ((heights[i2] || 0) < heights[stack[stack.length-1]]) {
const i = stack.pop()
const i1 = stack[stack.length-1]
max = Math.max(max, heights[i] * (i2 - i1 - 1))
}
stack.push(i2)
}
return max
};
TWO
Same idea as above. Use DP to cache accumulated states.
Pick a pivot point (row, col) and assume it is on the base line. The adjoining 1s above (row, col) makes up the height of the rectangle. The width of the rectangle is determined by how many ajoining bars are taller than the pivot bar.
So for the rectangle whose bottom pivot is (row, col):
Define area(row, col) to be the area.
Define height(row, col) to be the height.
Define left(row, col) to be the col value of the bottom-left corner.
Define right(row, col) to be the col value of the bottom-right corner.
Also:
Define conLeft(row, col) to be the col value of the leftmost cell of the consecutive 1s on the left of (row, col).
Define conRight(row, col) to be the col value of the rightmost cell of the consecutive 1s on the right of (row, col).
With conLeft and conRight we can know if the rectangle on (row, col) shrinks comparing to (row-1, col).
if matrix[row][col] == 1
height(row, col) = height(row-1, col) + 1
// see how long this horizontal line can get
conLeft(row, col) = conLeft(row, col-1)
conRight(row, col) = conRight(row, col+1)
// width can only be shorter
left(row, col) = max( left(row-1, col), conLeft(row, col) )
right(row, col) = min( right(row-1, col), conRight(row, col) )
if matrix[row][col] == 0
height(row, col) = 0
conLeft(row, col) = col + 1
conRight(row, col) = col - 1
left(row, col) = 0 // back to leftmost position
right(row, col) = matrix.width // back to rightmost position
area(row, col) = (right(row, col) - left(row, col) + 1) * height(row, col)
We only need to keep the last state. Use dynamic arrays to reduce space complexity.
/**
* @param {character[][]} matrix
* @return {number}
*/
let maximalRectangle = function(matrix) {
const height = matrix.length
if (height <= 0) { return 0 }
const width = matrix[0].length
if (width <= 0) { return 0 }
const heights = new Array(width).fill(0)
const lefts = new Array(width).fill(0)
const rights = new Array(width).fill(width)
let max = 0
for (let row = 0; row < height; row++) {
let conLeft = 0
let conRight = width - 1
for (let col = 0; col < width; col++) {
if (matrix[row][col] === '1') {
heights[col] = heights[col] + 1
lefts[col] = Math.max(lefts[col], conLeft)
} else {
heights[col] = 0
lefts[col] = 0
conLeft = col + 1
}
}
for (let col = width - 1; col >= 0; col--) {
if (matrix[row][col] === '1') {
rights[col] = Math.min(rights[col], conRight)
} else {
rights[col] = width
conRight = col - 1
}
}
for (let col = 0; col < width; col++) {
max = Math.max(max, (rights[col] - lefts[col] + 1) * heights[col])
}
}
return max
};
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
Example 1:
Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2
For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.
00 - 0
10 - 2
11 - 3
01 - 1
Example 2:
Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
Therefore, for n = 0 the gray code sequence is [0].
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
Solution:
Reverse the level when pushing to the reuslt.
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
let zigzagLevelOrder = function(root) {
if (!root) { return [] }
const result = []
const queue = [NaN, root]
let zipzag = false
while (queue.length > 1) {
const node = queue.shift()
if (node !== node) {
if (zipzag = !zipzag) {
result.push(queue.map(n => n.val))
} else {
result.push(queue.map(n => n.val).reverse())
}
queue.push(NaN)
} else {
if (node.left) { queue.push(node.left) }
if (node.right) { queue.push(node.right) }
}
}
return result
};
Given a string S and a string T, count the number of distinct subsequences of S which equals T.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Example 1:
Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
Example 2:
Input: S = "babgbag", T = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^
Solution:
Define f(i, j) to be the number of ways that generate T[0...j) from S[0...i).
For f(i, j) you can always skip S[i-1], but can only take it when S[i-1] === T[j-1].
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Solution:
Only care about positive profits. Take the frist item as base and scan to the right. If we encounter an item j whose price price[j] is lower than the base (which means if we sell now the profit would be negative), we sell j-1 instead and make j the new base.
Because price[j] is lower that the base, using j as new base is guaranteed to gain more profit comparing to the old one.
/**
* @param {number[]} prices
* @return {number}
*/
let maxProfit = function(prices) {
let max = 0
let base = prices[0]
for (let i = 1; i < prices.length; i++) {
const profit = prices[i] - base
if (profit > max) {
max = profit
} else if (profit < 0) {
base = prices[i]
}
}
return max
};
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Solution:
Sell immediately after the price drops. Or in other perspective, it is the sum of all the incremental pairs (buy in then immediately sell out).
/**
* @param {number[]} prices
* @return {number}
*/
let maxProfit = function(prices) {
let max = 0
for (let i = 1; i < prices.length; i++) {
if (prices[i] > prices[i-1]) {
max += prices[i] - prices[i-1]
}
}
return max
};
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
**Note:**You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Solution:
Multiple transactions may not be engaged in at the same time. That means if we view the days that involed in the same transaction as a group, there won't be any intersection. We may complete at most two transactions, so divide the days into two groups, [0...k] and [k...n-1]. Notice k exists in both groups because technically we can sell out then immediately buy in at the same day.
Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
For every node, there are six possible ways to get the max path sum:
With node.val
node.val plus the max sum of a path that ends with node.left.
node.val plus the max sum of a path that starts with node.right.
node.val plus the max sum of both paths.
Just node.val (the max sum of both paths are negative).
Withoutnode.val (disconnected)
The max-sum path is somewhere under the node.left subtree.
The max-sum path is somewhere under the node.right subtree.
There are two ways to implement this.
ONE
Define a function that returns two values. The max sum of a path that may or may not end with root node, and the max sum of the path that ends with root node.
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
let maxPathSum = function(root) {
return Math.max(..._maxPathSum(root))
};
/**
* @param {TreeNode} root
* @return {number[]}
*/
function _maxPathSum (root) {
if (!root) { return [-Infinity, -Infinity] }
const left = _maxPathSum(root.left)
const right = _maxPathSum(root.right)
return [
Math.max(left[0], right[0], root.val + Math.max(0, left[1], right[1], left[1] + right[1])),
Math.max(left[1], right[1], 0) + root.val
]
}
TWO
Just return the later (max sum of a path that ends with root). Maintain a global variable to store the disconnected max sum.
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
let maxPathSum = function(root) {
const global = { max: -Infinity }
_maxPathSum(root, global)
return global.max
};
/**
* @param {TreeNode} root
* @param {object} global
* @param {number} global.max
* @return {number[]}
*/
function _maxPathSum (root, global) {
if (!root) { return -Infinity }
const left = _maxPathSum(root.left, global)
const right = _maxPathSum(root.right, global)
const localMax = Math.max(left, right, 0) + root.val
global.max = Math.max(global.max, localMax, root.val + left + right)
return localMax
}
/**
* @param {string} s
* @return {boolean}
*/
let isPalindrome = function(s) {
const clean = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase()
for (let i = 0, j = clean.length - 1; i < j; i++, j--) {
if (clean[i] !== clean[j]) { return false }
}
return true
};
THREE
Compare the char codes.
/**
* @param {string} s
* @return {boolean}
*/
let isPalindrome = function(s) {
for (let i = 0, j = s.length - 1; i < j; i++, j--) {
let left = s.charCodeAt(i)
while (i < j && (left < 48 || left > 57 && left < 65 || left > 90 && left < 97 || left > 122)) {
left = s.charCodeAt(++i)
}
if (i >= j) { return true }
if (left >= 65 && left <= 90) {
left += 32
}
let right = s.charCodeAt(j)
while (i < j && (right < 48 || right > 57 && right < 65 || right > 90 && right < 97 || right > 122)) {
right = s.charCodeAt(--j)
}
if (i >= j) { return true }
if (right >= 65 && right <= 90) {
right += 32
}
if (left !== right) { return false }
}
return true
};
Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
Return an empty list if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
The constrain still works, but instead of deleting the words right away, collect them and delete them all when a level ends, so that we can reuse the words (matching different parents in the same level).
The items in the queue are not just words now. Parent nodes are also kept so that we can backtrack the path from the end.
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {string[][]}
*/
function findLadders (beginWord, endWord, wordList) {
wordList = new Set(wordList)
if (!wordList.has(endWord)) { return [] }
const ALPHABET = 'abcdefghijklmnopqrstuvwxyz'
const result = []
let isEndWordFound = false
const levelWords = new Set()
const queue = [[beginWord, null], null]
while (queue.length > 1) {
const node = queue.shift()
if (node === null) {
if (isEndWordFound) {
break
}
levelWords.forEach(word => wordList.delete(word))
levelWords.clear()
queue.push(null)
continue
}
const word = node[0]
for (let i = word.length - 1; i >= 0; i--) {
const head = word.slice(0, i)
const tail = word.slice(i+1)
for (let c = 0; c < 26; c++) {
if (ALPHABET[c] !== word[i]) {
const w = head + ALPHABET[c] + tail
if (w === endWord) {
const path = [endWord]
for (let n = node; n !== null; n = n[1]) {
path.unshift(n[0])
}
result.push(path)
isEndWordFound = true
}
if (wordList.has(w)) {
levelWords.add(w)
queue.push([w, node])
}
}
}
}
}
return result
};
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
Example 1:
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
Solution:
Think of it as building a tree, with begineWord as root and endWord as leaves.
The best way control the depth (length of the shortest transformations) while building the tree is level-order traversal (BFS).
We do not actually build the tree because it is expensive (astronomical if the list is huge). In fact, we only need one shortest path. So just like Dijkstra's algorithm, we say that the first time (level i) we encounter a word that turns out to be in a shortest path, then level i is the lowest level this word could ever get. We can safely remove it from the wordList.
To find all the next words, instead of filtering the wordList, enumerate all 25 possible words and check if in wordList.
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
let ladderLength = function(beginWord, endWord, wordList) {
wordList = new Set(wordList)
if (!wordList.has(endWord)) { return 0 }
const ALPHABET = 'abcdefghijklmnopqrstuvwxyz'
let level = 1
const queue = [beginWord, null]
while (queue.length > 1) {
const word = queue.shift()
if (word === null) {
level++
queue.push(null)
continue
}
for (let i = word.length - 1; i >= 0; i--) {
const head = word.slice(0, i)
const tail = word.slice(i+1)
for (let c = 0; c < 26; c++) {
if (ALPHABET[c] !== word[i]) {
const word = head + ALPHABET[c] + tail
if (word === endWord) {
return level + 1
}
if (wordList.delete(word)) {
queue.push(word)
}
}
}
}
}
return 0
};
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Solution:
Build a Set from the list. Pick a number, find all it's adjacent numbers that are also in the Set. Count them and remove them all from the Set. Repeat until the Set is empty. Time complexity O(n + n) = O(n).
/**
* @param {number[]} nums
* @return {number}
*/
let longestConsecutive = function(nums) {
const numSet = new Set(nums)
let maxCount = 0
while (numSet.size > 0) {
const num = numSet.values().next().value
numSet.delete(num)
let count = 1
for (let n = num + 1; numSet.delete(n); n++) {
count++
}
for (let n = num - 1; numSet.delete(n); n--) {
count++
}
if (count > maxCount) {
maxCount = count
}
}
return maxCount
};
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
Note: A leaf is a node with no children.
Example:
Input: [1,2,3]
1
/ \
2 3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.
Example 2:
Input: [4,9,0,5,1]
4
/ \
9 0
/ \
5 1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.
Solution:
To write a clean solution for this promblem, use 0 as indicator of leaf node. If all the children get 0, it is a leaf node, return the sum of current level.
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
let sumNumbers = function(root, sum = 0) {
if (!root) { return 0 }
sum = sum * 10 + root.val
return sumNumbers(root.left, sum) + sumNumbers(root.right, sum) || sum
};
Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
Example:
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
Explanation:
Surrounded regions shouldn't be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.
Solution:
Find all the Os that are connected to the Os on the border, change them to #. Then scan the board, change O to X and # back to O.
The process of finding the connected Os is just like tree traversal. Os on the border are the same level. Their children are the second level. And so on.
So both BFS and DFS are good. I prefer BFS when pruning is not needed in favor of its readability.
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
let solve = function(board) {
const height = board.length
if (height <= 1) { return }
const width = board[0].length
if (width <= 1) { return }
const rowend = height - 1
const colend = width - 1
const queue = []
for (let row = 0; row < height; row++) {
if (board[row][0] === 'O') {
board[row][0] = '#'
queue.push(row, 0)
}
if (board[row][colend] === 'O') {
board[row][colend] = '#'
queue.push(row, colend)
}
}
for (let col = 0; col < width; col++) {
if (board[0][col] === 'O') {
board[0][col] = '#'
queue.push(0, col)
}
if (board[rowend][col] === 'O') {
board[rowend][col] = '#'
queue.push(rowend, col)
}
}
while (queue.length > 0) {
const row = queue.shift()
const col = queue.shift()
if (row < rowend && board[row + 1][col] === 'O') {
board[row + 1][col] = '#'
queue.push(row + 1, col)
}
if (row > 0 && board[row - 1][col] === 'O') {
board[row - 1][col] = '#'
queue.push(row - 1, col)
}
if (board[row][col + 1] === 'O') {
board[row][col + 1] = '#'
queue.push(row, col + 1)
}
if (board[row][col - 1] === 'O') {
board[row][col - 1] = '#'
queue.push(row, col - 1)
}
}
for (let row = 0; row < height; row++) {
for (let col = 0; col < width; col++) {
if (board[row][col] === '#') {
board[row][col] = 'O'
} else if (board[row][col] === 'O') {
board[row][col] = 'X'
}
}
}
};
Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a label (int) and a list (List[UndirectedGraphNode]) of its neighbors. There is an edge between the given node and each of the nodes in its neighbors.
OJ's undirected graph serialization (so you can understand error output):
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ \
/ \
0 --- 2
/ \
\_/
Note: The information about the tree serialization is only meant so that you can understand error output if you get a wrong answer. You don't need to understand the serialization to solve the problem.
Solution:
DFS. Cache the visited node before entering the next recursion.
/**
* Definition for undirected graph.
* function UndirectedGraphNode(label) {
* this.label = label;
* this.neighbors = []; // Array of UndirectedGraphNode
* }
*/
/**
* @param {UndirectedGraphNode} graph
* @return {UndirectedGraphNode}
*/
let cloneGraph = function(graph) {
const cache = {}
return _clone(graph)
function _clone (graph) {
if (!graph) { return graph }
const label = graph.label
if (!cache[label]) {
cache[label] = new UndirectedGraphNode(label)
cache[label].neighbors = graph.neighbors.map(_clone)
}
return cache[label]
}
};
The number of nodes in the tree is in the range [0, 5000].
-104 <= Node.val <= 104
Source# Convert Sorted Array to Binary Search Tree
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted array:-10,-3,0,5,9−10,−3,0,5,9,
One possible answer is:0,-3,9,-10,null,50,−3,9,−10,null,5, which represents the following height balanced BST:
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
Search for a node to remove.
If the node is found, delete the node.
Follow up: Can you solve it with time complexity O(height of tree)?
Example 1:
Example 2:
Input: root =5,3,6,2,4,null,75,3,6,2,4,null,7, key = 0
Output:5,3,6,2,4,null,75,3,6,2,4,null,7
Explanation: The tree does not contain a node with value = 0.
Example 3:
Input: root = [], key = 0
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 104].
-105 <= Node.val <= 105
Each node has a unique value.
root is a valid binary search tree.
-105 <= key <= 105
/**
* @param {number[][]} intervals
* @return {number}
*/
const minMeetingRooms = function(intervals) {
const len = intervals.length
const starts = new Array(len)
const ends = new Array(len)
for (let i = 0; i < len; i++) {
starts[i] = intervals[i][0]
ends[i] = intervals[i][1]
}
starts.sort((a, b) => a - b)
ends.sort((a, b) => a - b)
let rooms = 0
let endsIdx = 0
for (let i = 0; i < len; i++) {
if (starts[i] < ends[endsIdx]) rooms++
else endsIdx++
}
return rooms
}
≡
200px-Telephone-keypad2
250px-Sudoku-by-L2G-20050714.svg.png
A sudoku puzzle...
...and its solution numbers marked in red.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
8-queens.png
8-queens.png
robot_maze.png
histogram.png
histogram_area.png
PascalTriangleAnimated2.gif
PascalTriangleAnimated2.gif
alt text
alt text
Input: root =5,3,6,2,4,null,75,3,6,2,4,null,7, key = 3
Output:5,4,6,2,null,null,75,4,6,2,null,null,7
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is5,4,6,2,null,null,75,4,6,2,null,null,7, shown in the above BST.
Please notice that another valid answer is5,2,6,null,4,null,75,2,6,null,4,null,7and it's also accepted.
