Given an array N which contains at least 5 items, I want to find 2 numbers(P and Q) in which 0 < P < Q < N - 1.
Suppose we have the following array:
const N = [1, 9, 4, 5, 8];
From here the combination which gives the minimum cost is P = 2 and Q = 3.
Here is the solution that I found and I am looking for your help if I can improve its time complexity:
function solution(N) {
// since 0 < P < Q < N - 1
const sliced = N.slice(1, N.length - 1);
const sorted = sliced.sort((a, b) => a - b);
// the minimum should be from the start since we have sorted the array
const P = 0;
const Q = 1;
return getCost(P, Q, sorted);
}
function getCost(P, Q, N) {
return N[P] + N[Q];
}
// output should be 9
console.log(solution([1, 9, 4, 5, 8]))
In a best-case scenario it's 0(n log(n)) because of the sort, but I am wondering if we can improve it to O(n) for example.
Thanks for your help
What do you think of this solution?
function solution([_, ...n]) {
n.pop()
n.sort((a, b) => a - b);
return n[0] + n[1];
}
// output should be 9
console.log(solution([1, 9, 4, 5, 8]))The logic is the same that you outlined - only using some other approach that JS offers.
function twoSmallest(arr) {
let [first, second] = [arr[1], arr[2]]
for (let i = 3; i < arr.length - 1; i++) {
const el = arr[i]
if (el < first && el < second) {
[first, second] = [Math.min(first, second), el]
} else if (el < first) {
[first, second] = [second, el]
} else if (el < second) {
second = el
}
}
return first + second
}
This is an O(n) time and O(1) space solution. It also makes sure that the element with the smaller index is kept in first for the case where you need to use the indices and it is of interest for some reason.
The algorithm is clear, IMO, but the JS code is probably not the best implementation. I haven't written JS for some time.
I'm pretty sure this is O(n):
const solution = (arr) => {
// find smallest that's not at either end
let idx = 1;
let P = arr[1];
for(let i = 2; i < arr.length-1; i++) {
if(arr[i] < P) {
idx = i;
P = arr[i];
}
}
// find second smallest that's not at either end
let Q = Infinity;
for(let i = 1; i < arr.length-1; i++) {
if(i == idx) continue;
if(arr[i] < Q) Q = arr[i];
}
return P + Q;
}