Looking for two numbers, P and Q, in a given array N with at least 5 items where 0 < P < Q < N - 1.
Consider the following array:
const N = [1, 9, 4, 5, 8];
- If P = 1 , Q = 2 , then the cost is N[P] + N[Q] = N[1] + N[2] = 9 + 4 = 13
- If P = 1, Q = 3 , then the cost is N[P] + N[Q] = N[1] + N[3] = 9 + 5 = 14
- If P = 2, Q = 3 , then the cost is N[P] + N[Q] = N[2] + N[3] = 4 + 5 = 9
The combination with the minimum cost is P = 2 and Q = 3.
Here's a solution that can potentially be improved for better 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, the time complexity is O(n log(n)) due to the sort operation. However, are there ways to improve it to O(n)?
Thank you for your assistance!