2

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

Improve this question
5
  • 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? Commented Jan 25, 2022 at 7:01
  • 1
    @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 Commented Jan 25, 2022 at 7: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. Commented Jan 25, 2022 at 7:07
  • 1
    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. Commented Jan 25, 2022 at 7:19
  • @PaulHankin As I said, the first and last elements should be excluded Commented Jan 25, 2022 at 7:24

4 Answers 4

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

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
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
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.
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.
My mistake, I see how you avoid that now.
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.

Improve this answer

3 Comments

@muka But it's still 0(n log(n)) because of the sort right?
@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)
Yeah for sure it's better than my solution
1

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;
}
Improve this answer

Comments

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?

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.