Home > Reflections | ⏮️ ⏭️
2024-04-29
🏋🏻 Practice
// assumes that inputs are sorted
const valid = (nums1: number[], nums2: number[], x: number): boolean => {
for (let i = 0, extra = 0; i < nums2.length; i++) {
while (nums2[i] !== nums1[i + extra] + x) {
if (++extra > 2) return false
}
}
return true
}
function minimumAddedInteger(nums1: number[], nums2: number[]): number {
// optimization: all deletion choices are valid when nums2 contains 1 element
// so no need to sort or check for validity explicitly
// note: this optimization offers a tiny savings for the easiest inputs, so the cost if maintaining this code is probably greater than the value of keeping it
if (nums2.length === 1) return nums2[0] - Math.max(...nums1)
// we could do better by selecting the 3 smallest instead of doing a full sort
// sorting is O(N*log(N))
// selecting is O(N)
// but we need them fully sorted to test for valid results efficiently
nums1.sort((a, b) => a - b)
nums2.sort((a, b) => a - b)
// key insight: at least 1 of the 1st 3 elements of nums1 will be its minimum after deleting 2 elements
// if we pick an element that must have been deleted, our solution may be invalid, so we test for validity
// it's possible that more than 1 solution works, so return the best valid solution
return [0, 1, 2].reduce((best, firstIndex) => {
const x = nums2[0] - nums1[firstIndex]
// optimization: if a candidate solution is bigger than our currently best valid solution, we won't use it, so don't waste time checking if it's valid
return best > x && valid(nums1, nums2, x) ? x : best
}, Infinity)
}