Find the minimum cost combination algorithm

Question

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];

• if P = 1 , Q = 2 , the cost will be N[P] + N[Q] = N[1] + N[2] = 9 + 4 = 13
• if P = 1, Q = 3 , the cost will be N[P] + N[Q] = N[1] + N[3] = 9 + 5 = 14
• if P = 2, Q = 3 , the cost will be N[P] + N[Q] = N[2] + N[3] = 4 + 5 = 9

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

Answer 1

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.

Answer 2

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;
}

Answer 3

Here is the fastest way to find k smallest numbers in a list with Python. The rest is trivial

fastest method of getting k smallest numbers in unsorted list of size N in python?