[SOLVED] Find the minimum cost combination algorithm

Issue

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

Solution

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.

Answered By – user1984

Answer Checked By – Marilyn (BugsFixing Volunteer)