N88 https://leetcode.com/problems/merge-sorted-array/
var merge = function(nums1, m, nums2, n) {
let lastIdx = m + n - 1;
while (n - 1 >= 0) {
if (nums1[m - 1] > nums2[n - 1]) {
nums1[lastIdx] = nums1[m - 1];
m -= 1;
} else {
nums1[lastIdx] = nums2[n - 1];
n -= 1;
}
lastIdx -= 1;
}
};N26 https://leetcode.com/problems/remove-duplicates-from-sorted-array/
var removeDuplicates = function(nums) {
let k = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== nums[i - 1]) {
nums[k] = nums[i];
k++;
}
}
return k;
};N80 https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
function removeDuplicates(nums: number[]): number {
let indexOfUniq = 0
let startOfDuplication = 0
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== nums[i-1]) {
startOfDuplication = i
}
if (i - startOfDuplication < 2) {
indexOfUniq++
nums[indexOfUniq] = nums[i]
}
}
return indexOfUniq + 1
}https://leetcode.com/problems/rotate-array/
function rotate(nums: number[], k: number): void {
let steps = 0
let start = 0
while (steps < nums.length) {
let index = start
let val = nums[index]
while (true) {
index = (index + k) % nums.length
let nextVal = nums[index]
nums[index] = val
val = nextVal
steps ++
if (index === start) break
}
start++
}
};https://bigfrontend.dev/problem/implement-curry
function curry(fn) {
return function curried(...args) {
if (args.length >= fn.length) {
return fn(...args)
}
return (...args2) => curried(...args, ...args2)
}
}https://bigfrontend.dev/problem/implement-curry-with-placeholder
function curry(fn) {
return function curried(...args) {
if (args.length >= fn.length && !args.slice(0, fn.length).includes(curry.placeholder)) {
return fn(...args)
}
return (...args2) => {
const newArgs = args.map((arg) => {
if (arg === curry.placeholder && args2.length > 0) {
return args2.shift()
}
return arg
})
return curried(...newArgs, ...args2)
}
}
}
curry.placeholder = Symbol()https://bigfrontend.dev/problem/implement-Array-prototype.flat
# recursion
function flat(arr, depth = 1) {
let newArr = []
arr.forEach(el => {
if (Array.isArray(el) && depth > 0) {
newArr.push(...flat(el, depth - 1))
} else {
newArr.push(el)
}
})
return newArr
}
# iterative
function flat(arr, depth = 1) {
const stack = arr.map(el => ({ el, depth }))
const result = []
while (stack.length > 0) {
let obj = stack.pop()
if (obj.depth > 0 && Array.isArray(obj.el)) {
stack.push(
...obj.el.map(el => ({el, depth: depth - 1}))
)
} else {
result.push(obj.el)
}
}
return result.reverse()
}https://bigfrontend.dev/problem/create-a-sum
function sum(num) {
const sum2 = (num2) => sum(num + num2)
sum2.valueOf = () => num
return sum2
}https://leetcode.com/problems/jump-game/
function canJump(nums: number[]): boolean {
let lastIndex = nums.length - 1
for (let i = nums.length - 2; i >= 0; i--) {
if (nums[i] + i >= lastIndex) {
lastIndex = i
}
}
return lastIndex === 0
};https://leetcode.com/problems/jump-game-ii/description/
# TODOhttps://leetcode.com/problems/gas-station/
function canCompleteCircuit(gas: number[], cost: number[]): number {
let start = 0
let tank = 0
let i = 0
while (start < gas.length) {
const index = i % gas.length
const steps = i - start + 1
tank += gas[index] - cost[index]
if (steps === gas.length && tank >=0 ) {
return start
}
if (tank < 0) {
start = i + 1
tank = 0
}
i++
}
return -1
};https://leetcode.com/problems/insert-delete-getrandom-o1
# TODOhttps://bigfrontend.dev/problem/what-is-composition-create-a-pipe
function pipe(funcs) {
return (value) => funcs.reduce((acc, fn) => fn(acc), value)
}https://bigfrontend.dev/problem/create-an-Event-Emitter
class EventEmitter {
constructor() {
this.subscriptions = new Map()
}
subscribe(eventName, callback) {
if (!this.subscriptions.has(eventName)) {
this.subscriptions.set(eventName, [])
}
const wrapper = { callback }
this.subscriptions.get(eventName).push(wrapper)
return {
release: () => {
const subscriptions = this.subscriptions.get(eventName)
const index = subscriptions.indexOf(wrapper)
if (index === -1) return
subscriptions.splice(index, 1)
if (subscriptions.lenght === 0) {
this.subscriptions.delete(eventName)
}
}
}
}
emit(eventName, ...args) {
this.subscriptions.get(eventName)?.forEach(({ callback }) => {
callback(...args)
})
}
}https://bigfrontend.dev/problem/create-your-own-Promise
# TODOhttps://leetcode.com/problems/roman-to-integer/
const map = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
var romanToInt = function(s) {
let sum = 0
for (let i = 0; i < s.length; i++) {
let a = map[s[i]]
let b = i < s.length - 1 ? map[s[i+1]] : 0
if (a >= b) {
sum += a
} else {
sum -= a
}
}
return sum
};https://leetcode.com/problems/integer-to-roman/
let numbers = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
let map = {
'1000': 'M',
'900': 'CM',
'500': 'D',
'400': 'CD',
'100': 'C',
'90': 'XC',
'50': 'L',
'40': 'XL',
'10': 'X',
'9': 'IX',
'5': 'V',
'4': 'IV',
'1': 'I'
}
var intToRoman = function(num) {
let response = ''
let rest = num
let romanIndex = 0
while (rest > 0) {
if (rest >= numbers[romanIndex]) {
let n = Math.floor(rest / numbers[romanIndex])
rest -= n * numbers[romanIndex]
response += new Array(n).fill(map[numbers[romanIndex]]).join('')
}
romanIndex++
}
return response
};https://leetcode.com/problems/zigzag-conversion
var convert = function(s, numRows) {
if (numRows == 1) return s
let rows = new Array(numRows).fill('')
let dir = 1
let rIndex = 0
for (let i = 0; i < s.length; i++) {
rows[rIndex] += s[i]
rIndex += dir
if (rIndex === 0 || rIndex === numRows - 1) {
dir = -dir
}
}
return rows.join('')
};https://leetcode.com/problems/reverse-words-in-a-string
const reverseWords = (s) => s.trim().split(/\s+/).reverse().join(' ')https://bigfrontend.dev/problem/implement-async-helper-sequence
function sequence(funcs){
return (callback, data) => {
funcs.slice().reverse().reduce((currentCallback, fn, index) => {
if (index === funcs.length - 1) {
fn(currentCallback, data)
return
}
return (e1, d1) => {
if (e1) return callback(e1, d1)
fn(currentCallback, d1)
}
}, callback)
}
}https://bigfrontend.dev/problem/implement-async-helper-parallel
function parallel(funcs){
return (finalCallback, initialData) => {
let count = 0
let isDone = false
let resuts = new Array(funcs.length)
funcs.forEach((fn, index) => {
fn((error, data) => {
if (isDone) return
if (error) {
finalCallback(error, undefined)
isDone = true
return
}
count++
resuts[index] = data
if (count === funcs.length) {
finalCallback(undefined, resuts)
}
}, initialData)
})
}
}https://bigfrontend.dev/problem/implement-async-helper-race
function race(funcs){
return (finalCallback, initialData) => {
let isDone = false
funcs.forEach((fn, index) => {
fn((...args) => {
if (isDone) return
isDone = true
finalCallback(...args)
}, initialData)
})
}
}TODO
https://bigfrontend.dev/problem/promisify
function promisify(func) {
return function (...args) {
return new Promise((resolve, reject) => {
func.call(this, ...args, (error, data) => {
if (error) {
reject(error)
} else {
resolve(data)
}
})
})
}
}https://bigfrontend.dev/problem/implement-basic-debounce
function debounce(func, wait) {
let timer
return (...args) => {
clearTimeout(timer)
timer = setTimeout(() => {
func(...args)
}, wait)
}
}https://bigfrontend.dev/problem/implement-basic-throttle
function throttle(func, wait) {
let paused = false
let lastArgs = null
return function(...args) {
if (!paused) {
paused = true
lastArgs = null
func.apply(this, args)
setTimeout(() => {
paused = false
if (lastArgs) {
func.apply(this, lastArgs)
}
}, wait)
} else {
lastArgs = args
}
}
}https://bigfrontend.dev/problem/implement-throttle-with-leading-and-trailing-option
function throttle(func, wait = 0, {leading = true, trailing = true} = {}) {
let lastArgs = null
let timer = null
const startTimer = () => {
timer = setTimeout(() => {
timer = null
if (!lastArgs) return
func.apply(this, lastArgs)
lastArgs = null
// recurrsion
startTimer()
}, wait)
}
return function(...args) {
if (leading && timer === null) {
func.apply(this, args)
lastArgs = null
startTimer()
return
}
if (trailing) {
lastArgs = args
if (timer === null) {
startTimer()
}
}
}
}https://bigfrontend.dev/problem/throttle-Promises
// TODOhttps://leetcode.com/problems/valid-parentheses/
const map = {
'(': ')',
'[': ']',
'{': '}'
}
const openElements = Object.keys(map)
var isValid = function(s) {
const stack = []
for (let i = 0; i < s.length; i++) {
const el = s[i]
if (openElements.includes(el)) {
stack.push(el)
} else {
const top = stack.pop()
if (map[top] !== el) {
return false
}
}
}
return stack.length === 0
};https://leetcode.com/problems/simplify-path/
var simplifyPath = function(path) {
let arr = path.split('/').filter(el => el !== '')
const stack = arr.reduce((stack, el) => {
if (el === '..') {
stack.pop()
} else if (el !== '.') {
stack.push(el)
}
return stack
}, [])
let response = stack.join('/')
if (path[0] === '/') {
response = '/' + response
}
return response
};https://leetcode.com/problems/min-stack/
class MinStack {
elements: number[]
mins: number[]
constructor() {
this.elements = []
this.mins = []
}
push(val: number): void {
let min = this.getMin()
if (val < min || min === null) {
min = val
}
this.elements.push(val)
this.mins.push(min)
}
pop(): void {
this.elements.pop()
this.mins.pop()
}
top(): number {
return this.elements[this.elements.length - 1] ?? null
}
getMin(): number {
return this.mins[this.mins.length - 1] ?? null
}
}https://bigfrontend.dev/problem/create-an-Observable
class Observable {
constructor(setup) {
this.setup = setup
}
subscribe(subscriber) {
let isSubscriber = true
const wrapper = {
next: (value) => {
if (isSubscriber) {
if (subscriber.next) {
subscriber.next?.(value)
} else if (typeof subscriber === 'function') {
subscriber(value)
}
}
},
error: (error) => {
if (isSubscriber) {
subscriber.error?.(error)
isSubscriber = false
}
},
complete: () => {
if (isSubscriber) {
subscriber.complete?.()
isSubscriber = false
}
}
}
this.setup(wrapper)
return {
unsubscribe: () => {
isSubscriber = false
}
}
}
}https://bigfrontend.dev/problem/implement-Observable-from
function from(input) {
if (input instanceof Observable) return input
let callback = null
if (input instanceof Promise) {
callback = (observer) => {
input.then(
value => {
observer.next(value)
observer.complete()
},
error => observer.error(error)
)
}
} else if (Array.isArray(input) || input.length) {
callback = (observer) => {
Array.from(input).forEach(value => observer.next(value))
observer.complete()
}
} else if (Symbol.iterator in input) {
callback = (observer) => {
try {
for (let value of input) {
observer.next(value)
}
observer.complete()
} catch (error) {
observer.error(error)
}
}
}
if (!callback) throw new Error('Invalid input')
return new Observable(callback)
}https://bigfrontend.dev/problem/implement-Observable-Subject
class Subject {
constructor() {
this.subscribers = []
this.next = this.next.bind(this)
}
subscribe(subscriber) {
this.subscribers.push(subscriber)
return {
unsubscribe: () => {
this.subscribers.splice(this.subscribers.indexOf(subscriber), 1)
}
}
}
next(value) {
this.subscribers.forEach(s => s(value))
}
}https://leetcode.com/problems/linked-list-cycle/
var hasCycle = function(head) {
let slow = head
let fast = head
while(fast?.next?.next) {
slow = slow.next
fast = fast.next?.next
if (slow === fast) {
return true
}
}
return false
};https://leetcode.com/problems/add-two-numbers/
function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
let head = new ListNode()
let current = head
let bonus = 0
while (true) {
let value = (l1?.val ?? 0) + (l2?.val ?? 0) + bonus
if (value > 9) {
bonus = 1
value = value - 10
} else {
bonus = 0
}
current.val = value
l1 = l1?.next
l2 = l2?.next
if (l1 || l2 || bonus) {
current.next = new ListNode()
current = current.next
} else {
break
}
}
return head
};https://leetcode.com/problems/remove-nth-node-from-end-of-list/
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
let slow = head
let fast = head
for (let i = 0; i < n; i++) {
fast = fast?.next
}
if (!fast) {
return head.next
}
while (fast?.next) {
slow = slow?.next
fast = fast?.next
}
slow.next = slow.next?.next
return head
};https://leetcode.com/problems/rotate-list/
var rotateRight = function (head, k) {
if (!head) return head
let len = 1
let tail = head
while (tail.next) {
tail = tail.next
len += 1
}
k = k % len
if (k === 0) return head
let steps = len - k - 1
let current = head
while (steps > 0) {
current = current.next
steps -= 1
}
tail.next = head
head = current.next
current.next = null
return head
};https://bigfrontend.dev/problem/undefined-to-null
function undefinedToNull(arg) {
if (Array.isArray(arg)) {
return arg.map(v => undefinedToNull(v))
}
if (typeof arg === 'object' && arg !== null) {
return Object.fromEntries(
Object.entries(arg).map(
([k, v]) => [k, undefinedToNull(v)]
)
)
}
return arg === undefined ? null : arg
}https://bigfrontend.dev/problem/create-lazyman
const sleep = (time) => new Promise(
(resolve) => setTimeout(resolve, time)
)
const pluralizeSecond = (time) => time % 10 > 1 ? 'seconds' : 'second'
function LazyMan(name, logFn) {
const actions = [
() => { logFn(`Hi, I'm ${name}.`) },
]
Promise.resolve().then(async () => {
for (const action of actions) {
await action()
}
})
const obj = {
sleep(time) {
actions.push(() =>
sleep(time * 1000).then(() => { logFn(`Wake up after ${time} ${pluralizeSecond(time)}.`) } )
)
return obj
},
sleepFirst(time) {
actions.unshift(() =>
sleep(time * 1000).then(() => { logFn(`Wake up after ${time} ${pluralizeSecond(time)}.`) } )
)
return obj
},
eat(food) {
actions.push(() => { logFn(`Eat ${food}.`) })
return obj
}
}
return obj
}https://bigfrontend.dev/problem/implement-general-memoization-function
const defaultResolver = (...args) => args.join('_')
function memo(func, resolver = defaultResolver) {
const memorizedFn = function(...args) {
const key = resolver(...args)
if (!memorizedFn.cache.has(key)) {
memorizedFn.cache.set(key, func.call(this, ...args))
}
return memorizedFn.cache.get(key)
}
memorizedFn.cache = new Map()
return memorizedFn
}https://bigfrontend.dev/problem/implement-memoizeOne
const defaultResolver = (a, b) =>
a.length === b.length && a.every((v, i) => v === b[i])
function memoizeOne(func, isEqual = defaultResolver) {
let lastThis
let lastArgs
let lastResult
return function(...args) {
if (
lastResult === undefined ||
lastThis !== this ||
!isEqual(lastArgs, args)
) {
lastThis = this
lastArgs = args
lastResult = func.call(this, ...args)
}
return lastResult
}
}
https://leetcode.com/problems/search-insert-position/
var searchInsert = function(nums, target) {
let l = 0
let r = nums.length
while (l < r) {
let m = Math.floor((l+r)/2)
if (nums[m] < target) {
l = m + 1
} else {
r = m
}
}
return l
};https://leetcode.com/problems/search-a-2d-matrix/
var searchMatrix = function(matrix, target) {
let l = 0
let r = matrix.length
while (l < r) {
let c = Math.floor((l + r) / 2)
if (matrix[c].at(-1) < target) {
l = c + 1
} else {
r = c
}
}
const rowIndex = l
if (rowIndex === matrix.length) return false
l = 0
r = matrix[rowIndex].length
while (l < r) {
let c = Math.floor((l + r) / 2)
if (matrix[rowIndex][c] < target) {
l = c + 1
} else {
r = c
}
}
return matrix[rowIndex][l] === target
};https://leetcode.com/problems/find-peak-element/
var findPeakElement = function(nums) {
let l = 0
let r = nums.length
while (l < r) {
let m = Math.floor((l+r)/2)
if (nums[m] < nums[m + 1]) {
l = m + 1
} else {
r = m
}
}
return l
};https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
TODOhttps://bigfrontend.dev/problem/search-first-index-with-Binary-Search-duplicate-array
function firstIndex(arr, target){
let l = 0
let r = arr.length
while (l < r) {
let m = Math.floor((l + r) / 2)
if (arr[m] >= target) {
r = m
} else {
l = m + 1
}
}
return arr[l] === target ? l : -1
}function elementBefore(arr, target){
let l = 0
let r = arr.length
while (l < r) {
let m = Math.floor((l + r) / 2)
if (arr[m] >= target) {
r = m
} else {
l = m + 1
}
}
return arr[l - 1]
}https://bigfrontend.dev/problem/first-bad-version
function firstBadVersion(isBad) {
return (version) => {
l = 0
r = version
while (l < r) {
let m = Math.floor((l + r) / 2)
if (isBad(m)) {
r = m
} else {
l = m + 1
}
}
return isBad(l) ? l : -1
}
}https://bigfrontend.dev/problem/remove-characters
https://bigfrontend.dev/problem/Count-palindromic-substrings
https://leetcode.com/problems/invert-binary-tree/
var invertTree = function(root) {
if (!root) return null
const left = root.left
root.left = root.right
root.right = left
invertTree(root.left)
invertTree(root.right)
return root
};https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
var flatten = function(root) {
if (!root) return null
let last = new TreeNode()
let ret = last
const go = (parent) => {
if (!parent) return null
last.right = new TreeNode(parent.val)
last.left = null
last = last.right
go(parent.left)
go(parent.right)
}
go(root)
root.left = null
root.right = ret.right?.right
};https://leetcode.com/problems/binary-search-tree-iterator/submissions
https://bigfrontend.dev/problem/serialize-and-deserialize-binary-tree https://bigfrontend.dev/problem/binary-tree-vertical-traversal https://bigfrontend.dev/problem/get-DOM-tree-height https://bigfrontend.dev/problem/find-corresponding-node-in-two-identical-DOM-tree
https://leetcode.com/problems/implement-trie-prefix-tree
const end = 'end'
var Trie = function() {
this.root = {}
};
Trie.prototype.insert = function(word) {
let node = this.root
for (let c of word) {
if (!node[c]) node[c] = {}
node = node[c]
}
node[end] = true
};
Trie.prototype.search = function(word) {
let node = this.root
for (let c of word) {
if (!node[c]) return false
node = node[c]
}
return !!node[end]
};
Trie.prototype.startsWith = function(prefix) {
let node = this.root
for (let c of prefix) {
if (!node[c]) return false
node = node[c]
}
return true
};https://leetcode.com/problems/design-add-and-search-words-data-structure
const terminator = 'end'
var WordDictionary = function() {
this.root = {}
};
WordDictionary.prototype.addWord = function(word) {
let node = this.root
for (let c of word) {
if (!node[c]) node[c] = {}
node = node[c]
}
node[terminator] = true
};
const search = (root, word) => {
let node = root
for (let i = 0; i < word.length; i++) {
const c = word[i]
if (c === '.') {
return Object.keys(node).some(
key => search(node[key], word.slice(i + 1))
)
}
if (!node[c]) return false
node = node[c]
}
return !!node[terminator]
}
WordDictionary.prototype.search = function(word) {
return search(this.root, word)
};// TODO:
https://bigfrontend.dev/problem/implement-Immutability-helper
function update(data, command) {
if (Array.isArray(data)) {
let value = [...data]
Object.keys(command).forEach((key) => {
if (key.startsWith('$')) {
if (key === '$push') {
value.push(...command[key])
}
} else {
value[key] = update(data[key], command[key])
}
})
return value
}
let value = data
Object.keys(command).forEach((key) => {
if (key === '$set') {
value = command[key]
} else if (key === '$merge') {
if (typeof data !== 'object') throw 'Error'
value = {...data, ...command[key]}
} else if (key === '$apply') {
value = command[key](value)
} else {
value[key] = update(data[key], command[key])
}
})
return value
}https://bigfrontend.dev/problem/Virtual-DOM-I
/**
* @param {HTMLElement}
* @return {object} object literal presentation
*/
function virtualize(element) {
if (element.nodeType === 3) { // string
return element.nodeValue
}
const props = element.getAttributeNames().reduce((acc, attr) => {
let reactAttr = attr === 'class' ? 'className' : attr
acc[reactAttr] = element.getAttribute(attr)
return acc
}, {})
props.children = element.childNodes.length === 1
? virtualize(element.childNodes[0])
: Array.from(element.childNodes).map(el => virtualize(el))
return {
type: element.tagName.toLowerCase(),
props
}
}
/**
* @param {object} valid object literal presentation
* @return {HTMLElement}
*/
function render(obj) {
const el = document.createElement(obj.type)
Object.keys(obj.props).forEach(prop => {
if (prop === 'children') {
return
}
if (prop === 'className') {
el.setAttribute('class', obj.props[prop])
} else {
el.setAttribute(prop, obj.props[prop])
}
})
if (obj.props?.children) {
if (Array.isArray(obj.props.children)) {
obj.props.children.forEach(child => {
if (typeof child === 'string') {
el.append(child)
} else {
el.appendChild(
render(child)
)
}
})
} else { // string
el.append(obj.props.children)
}
}
return el
}https://leetcode.com/problems/summary-ranges/
var summaryRanges = function(nums) {
let result = []
let start = nums[0]
nums.push(null)
for (let i = 1; i < nums.length; i++) {
if (nums[i] === nums[i - 1] + 1) continue
if (start !== nums[i - 1]) {
result.push(`${start}->${nums[i - 1]}`)
} else {
result.push(`${start}`)
}
start = nums[i]
}
return result
}https://leetcode.com/problems/summary-ranges/
var merge = function(intervals) {
intervals.sort((a, b) => a[0] - b[0])
let result = [intervals[0]]
for (let i = 1; i < intervals.length; i++) {
let last = result.at(-1)
let current = intervals[i]
if (last[1] >= current[0]) {
last[1] = Math.max(current[1], last[1])
} else {
result.push(current)
}
}
return result
};https://leetcode.com/problems/insert-interval/
TODOhttps://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
var findMinArrowShots = function(points) {
points.sort((a, b) => a[0] - b[0])
let arrows = 1
let arrow = points[0]
for (let i = 1; i < points.length; i++) {
let current = points[i]
if (arrow[1] < current[0]) { // not intersection
arrows++
arrow = [...current]
} else {
arrow = [
Math.max(arrow[0], current[0]),
Math.min(arrow[1], current[1])
]
}
}
return arrows
};