I'm trying to find a solution for this problem, in JavaScript, with O(N) time complexity.
Problem: You are given an array A of N positive integers and an integer k. You want to remove k consecutive elements from A such that the amplitude of remaining element is minimal. Amplitude is the the difference between the minimal and maximal elements.
For eg. A[] = [8,7,4,1] and k=2. Output should be 1 because we will remove 4 and 1.
A brute force solution is simple. Is it possible to do in O(n)? Thanks
Does this help you? I first determine the 3 largest numbers (3 because we remove 2 consecutive numbers and it is possible that those 2 numbers are the 2 largest ones, so we need the next largest), then we do the same for the 3 smallest numbers.
We create an array of the consecutive numbers removed, without altering the original array.
Then we just run some if else statements to determine if the max, min is contained in the consecutive numbers removed
It is not the prettiest though. A lot of if/else
const arr = [8, 7, 4, 1]
const arr2 = [8, 7, 4, 1, 4, 6, 8]
const arr3 = [8, 7, 4, 1, 4, 6, 8, 3, 11, 4, 15]
function slice2Consecutive(arr) {
let newArr = []
for (let i = 0; i < arr.length - 1; i++) {
let s1 = arr[i]
let s2 = arr[i + 1]
newArr.push([arr[i], arr[i + 1]])
}
return newArr
}
function maxThree(arr) {
let one = -Infinity;
let two = -Infinity;
let three = -Infinity;
for (let i = 0; i < arr.length; i += 1) {
let num = arr[i];
if (num > three) {
if (num >= two) {
three = two;
if (num >= one) {
two = one;
one = num;
} else {
two = num;
}
} else {
three = num;
}
}
}
return [one, two, three]
}
function minThree(arr) {
let one = +Infinity;
let two = +Infinity;
let three = +Infinity;
for (let i = 0; i < arr.length; i += 1) {
let num = arr[i];
if (num < three) {
if (num <= two) {
three = two;
if (num <= one) {
two = one;
one = num;
} else {
two = num;
}
} else {
three = num;
}
}
}
return [one, two, three]
}
function minAmplitude(arr) {
const [max, secondMax, thirdMax] = maxThree(arr)
const [min, secondMin, thirdMin] = minThree(arr)
const slicedArr = slice2Consecutive(arr)
const amplitudeArr = []
for (let i = 0; i < slicedArr.length; i++) {
let m = max
let n = min
if (slicedArr[i][0] === max || slicedArr[i][1] === max) {
if (slicedArr[i][0] === secondMax || slicedArr[i][1] === secondMax) {
m = thirdMax
} else {
m = secondMax
}
}
if (slicedArr[i][0] === min || slicedArr[i][1] === min) {
if (slicedArr[i][0] === secondMin || slicedArr[i][1] === secondMin) {
n = thirdMin
} else {
n = secondMin
}
}
amplitudeArr.push(m - n)
}
return Math.min(...amplitudeArr)
}
console.log(minAmplitude(arr))
console.log(minAmplitude(arr2))
console.log(minAmplitude(arr3))