Home > Reflections | ⏮️ ⏭️
2024-05-01
🏋 Practice | 13 solutions to Remove Element
⌛ The first solution I wrote took more than an hour to get right.
🤦 That’s way too slow for an interview.
🎻 It’s more efficient than it needs to be and too fiddly.
🏎️ A simpler implementation took less than 10 minutes to write.
⚖️ They have the same worst-case asymptotic run-time complexity (big O).
🧑🏫 Lesson: aim to write the simplest code with the ideal asymptotic worst-case complexity.
🙈 It can be helpful to ignore LeetCode’s statistical benchmarks to avoid micro-optimization.
/*
- remove all occurrences of val in nums
- in place
- order may be changed
- return number of elements in nums which are not equal to val
- change nums such that first k elements are not equal to val
- doesn't matter what's in the rest of the array
- 0 <= val <= 100
- 0 <= nums[i] <= 50
- 0 <= nums.length <= 100
Plan
- k - number of occurrences of val in nums
- swap the last k elements not equal to val with a corresponding occurrence of val
1. scan the array from right to left
2. at the first index != val, pause (we can swap a val here)
3a. increment counter
3. scan the array from left to right
4. at the first occurrence of val, set this to the nonVal found on the right
5. continue until we've traversed the entire array
6. return k
~12 minutes
67 minutes until passing solution
very fiddly solution
maybe I should optimize for simple code with ideal algorithmic performance instead of squeezing every ounce of perf out of the solution
*/
function removeElement1(nums: number[], val: number): number {
let right = nums.length - 1
let left = 0
let count = 0
while (left <= right) {
const x = nums[right]
if (x === val) {
count++
} else {
while (left <= right) {
if (nums[left] === val) {
count++
nums[left] = x
left++
break
}
left++
}
}
right--
}
return nums.length - count
}
/*
1. Count the number of occurrences of val in nums
2. Collect the last count elements from the end of nums
3. replace each occurrence of val with an element from the end
*/
function removeElement2(nums: number[], val: number): number {
// O(N)
const count = nums.filter(x => x === val).length
// O(N)
const replacements = nums.filter(x => x !== val).slice(-count)
// O(N^2)
while (replacements.length) {
// O(N)
const i = nums.indexOf(val)
nums[i] = replacements.pop()
}
// O(1)
return nums.length - count
// O(2N + N^2 + 1) ~ O(N^2)
}
/*
1. Find all indices of val in nums
2. Collect all non-val values
3. replace each occurrence of val with an element from the end of non-val values
Optimize for simple code that meets optimal asymptotic worst-case run-time complexity
*/
function removeElement3(nums: number[], val: number): number {
// O(N)
const keepers = nums.filter(x => x !== val)
// O(1)
const k = keepers.length
nums
// O(N)
.map((x, i) => [x, i])
// O(N)
.filter(([x, i]) => x === val)
// O(N)
.map(([x, i]) => i)
// O(N)
.forEach(i => nums[i] = keepers.pop())
return k
// O(5N + 1) ~ O(N)
}
/*
Sub-optimal (O(n*log(n)) due to sorting)
1. replace every occurrence of val with Infinity (counting each)
2. Sort the array
3. return count
6 minutes to a working solution!
*/
function removeElement4(nums: number[], val: number): number {
let count = 0
// O(N)
for (let i = 0; i < nums.length; i++) {
if (nums[i] === val) {
count++
nums[i] = Infinity
}
}
// O(N*log(N))
nums.sort((a, b) => a - b)
return nums.length - count
// O(N*log(N) + N) ~ O(N*log(N))
}
/*
1. count occurrences of !val
2. sort the array based on whether the value is val or not
3. return length - count
*/
function removeElement5(nums: number[], val: number): number {
// O(N)
const k = nums.filter(x => x !== val).length
// O(N*log(N))
nums.sort((a, b) => a === val ? 1 : -1)
return k
// O(N + N*log(N)) ~ O(N*log(N))
}
/*
1. filter nums to only !val
2. k = length array
3. copy filtered values into nums
*/
function removeElement6(nums: number[], val: number): number {
// O(N)
const keepers = nums.filter(x => x !== val)
// O(N)
keepers.forEach((x, i) => nums[i] = x)
// O(1)
return keepers.length
// O(2N + 1) ~ O(N)
}
/*
1. initialize k = nums.length
2. initialize a right cursor to nums.length -1
3. scan nums left to right
4. for each element = val, replace it with the first non-val from the right cursor
5. decrement k for each occurrence of val
*/
function removeElement7(nums: number[], val: number): number {
// O(1)
let k = nums.length
// O(N)
for (let left = 0, right = k; left < right; left++) {
if (nums[left] === val) {
k--
right--
while (left < right && nums[right] === val) {
k--
right--
}
nums[left] = nums[right]
}
}
return k
// O(1 + N) ~ O(N)
}
/*
same as above, but use a single variable for right & k
*/
function removeElement8(nums: number[], val: number): number {
let right = nums.length
for (let left = 0; left < right; left++) {
if (nums[left] === val) {
right--
while (left < right && nums[right] === val) {
right--
}
nums[left] = nums[right]
}
}
return right
}
/*
same as above, but simplify with reduce & do-while
note: reduce will not exit early like the for loop will
*/
function removeElement9(nums: number[], val: number): number {
return nums.reduce((right, n, left) => {
if (n === val && left < right) {
do { right-- } while (nums[right] === val && left < right)
nums[left] = nums[right]
}
return right
}, nums.length)
}
/*
1. Scan nums from left to right splicing out any elements equal to val
2. return the length of the modified array
*/
function removeElement10(nums: number[], val: number): number {
// O(N)
for (let i = 0; i < nums.length; i++) nums[i] === val && nums.splice(i--, 1)
// O(1)
return nums.length
// O(N + 1) ~ O(N)
}
/*
- 0 <= nums[i] <= 50
This constraint allows us to sort in linear time because we don't need comparisons
There are exactly 51 discrete values, so we can just count them
*/
function removeElement11(nums: number[], val: number): number {
const counts = []
// O(N)
nums
.filter(num => num !== val)
.forEach(num => counts[num] = (counts[num] || 0) + 1)
nums.length = 0
// O(51N)
counts.forEach((count, num) => {
while (count--) nums.push(num)
})
// O(1)
return nums.length
// O(52N + 1) ~ O(N)
}
/*
Slight variation of the above
- 0 <= nums[i] <= 50
This constraint allows us to sort in linear time because we don't need comparisons
There are exactly 51 discrete values, so we can just concatenate each value onto
one of 51 lists, then flatten that list
*/
function removeElement12(nums: number[], val: number): number {
const sorted = []
nums
// O(N)
.filter(num => num !== val)
// O(N)
.forEach(num => sorted[num] = (sorted[num] || []).concat(num))
// O(1)
nums.length = 0
sorted
// O(51)
.filter(x => x)
// O(51)
.flat()
// O(N)
.forEach(x => nums.push(x))
// O(1)
return nums.length
// O(2N + 1 + 2*51 + N + 1) ~ O(N)
}
/*
🤔 Oh yeah... there's no need to sort anything... I guess I got carried away
1. filter all values not equal to val
2. k = the length of this array
3. set the first k values of nums to the filtered values
4. return k
*/
function removeElement(nums: number[], val: number): number {
const nonVals = nums.filter(x => x !== val)
nums.length = 0
nums.push(...nonVals)
return nums.length
}