Find the minimum cost combination algorithm-CodePudding

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

CodePudding user response：

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.

CodePudding user response：

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.

CodePudding user response：

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

CodePudding user response：

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?