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

What you basically need is the sum of two smallest elements in the array? - should be `O(N)`. For your example, shouldn't `P`=0 and `Q`=2 , sum = 5 be the solution instead? — Jay, Jan 25 '22 at 07:01
@Jay no it's the sum of the two smallest elements in a subset(the first and last element should be excluded) of the array — Pety Ialimijoro Rakotoniaina, Jan 25 '22 at 07:04
ok, in that case, it would be sum of two smallest numbers for `N.slice(1, N.length - 1)`. you can iterate through the array once by keeping track of smallest and second smallest no. and their index seen so far, which would be your answer. — Jay, Jan 25 '22 at 07:07
You can find the k smallest elements in an array in O(nlog(k)) time. Since k=2 here, that's O(n) time. Quickselect or using a heap of size k are two possibilities. For k=2, you can just keep two variables and update them as you run through the array. — Paul Hankin, Jan 25 '22 at 07:19
@PaulHankin As I said, the first and last elements should be excluded — Pety Ialimijoro Rakotoniaina, Jan 25 '22 at 07:24

score 1 · Answer 1 · answered Jan 25 '22 at 07:15

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.

answered Jan 25 '22 at 07:15

muka.gergely

8,063
2
17
34

@muka But it's still 0(n log(n)) because of the sort right? – Pety Ialimijoro Rakotoniaina Jan 25 '22 at 07:28
@PetyIalimijoroRakotoniaina I think the **O** was not changed - just the implementation is more concise. (The `spread` in the `arguments` and the `.pop()` just simplifies - but the logic is the same) – muka.gergely Jan 25 '22 at 07:34
Yeah for sure it's better than my solution – Pety Ialimijoro Rakotoniaina Jan 25 '22 at 07:36

score 1 · Accepted Answer · answered Jan 25 '22 at 07:47

1

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 Jan 25 '22 at 07:47

user1984

5,990
2
13
32

Thank you very much, this is clearly O(n) and we just need one loop, but I will need to make some adjustments because the first should be less than the second – Pety Ialimijoro Rakotoniaina Jan 25 '22 at 08:08
1

Oh, right. I thought that `first` should be the one that comes before `second` in the array, meaning the one that has the smaller index. Happy it helped. Wish you a good day :D @PetyIalimijoroRakotoniaina – user1984 Jan 25 '22 at 08:13
I believe this will produce the wrong answer for arrays like `[1,2,2,3,4]`, assuming those are possible. Also, P and Q don't strictly need to be `P < Q`, just `P != Q`, since the solution is their sum. I believe it's just described that way in the problem because it's easier, mathematically, to get the idea across. – Ouroborus Jan 25 '22 at 08:16
Tested `[1,2,2,3,4]` and it gives me `4` which is the right result @Ouroborus . Please explain the bug that you see further. Thanks. – user1984 Jan 25 '22 at 08:19
My mistake, I see how you avoid that now. – Ouroborus Jan 25 '22 at 08:23

score 1 · Answer 3 · answered Jan 25 '22 at 07:57

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

score 0 · Answer 4 · answered Jan 25 '22 at 08:43

0

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?

answered Jan 25 '22 at 08:43

Jean Valj

119
4

Find the minimum cost combination algorithm

4 Answers4