# [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.

## 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.