Find the sum of 2 smallest numbers

find-sum-of-2-smallest-numbers.js

function findSmallestSum(arr) {
  const len = arr.length;
  
  if (!len) return 0;
  if (len === 1) return arr[0];
  if (len === 2) return arr[0] + arr[1];
  
  // f - first, s - second
  let [f, s] = arr;
  let sum = f + s;
  
  for (let i = 2; i < len; i += 1) {
    const n = arr[i];
    
    // Continue to next n if n already > current sum
    if (n > sum) continue;
    
    // if n + f already < sum, this basically means that
    // s must be at least n if not greater, ITW, s >= n.
    // To test the claim above,
    // Say [f, s] = [2, 1] (sum = 3) and n = -1,0,1,2
    // when n = -1:
    //   n + f = -1 + 2 = 1 (< sum)
    // when n = 0: 
    //   n + f = 0 + 2 = 2 (< sum)
    // when n = 1:
    //   n + f = 1 + 2 = 3 (== sum)
    // when n = 2:
    //   n + f = 2 + 2 = 4 (> sum)
    // So, the above proves that we can disregard s
    // because n + f can only be < sum when n < s;
    if (n + f < sum) s = n;
    // Same idea applies to s too!
    else if (n + s < sum) f = n;
    
    // Do not forget to compute a new sum with 
    // the new f or s.
    sum = f + s;
  }
  
  return sum;
}

// [input array, expected smallest sum]
[
  [[], 0],
  [[0], 0],
  [[1], 1],
  [[0, 1], 1],
  [[1, 2, 3, 4], 3],
  [[6, 7, 56, 2], 8],
  [[6, 7, 56, 2, 9, 34, 3], 5],
  [[4, 4], 8],
  [[5, 38, 15, 1, 1, -19, 9], -18],
  [[-19, 20, -1, 2, 0], -20],
  [[1, 1, 1, 1], 2],
].map(([a, b]) => {
  const val = findSmallestSum(a);

  if (val === b) return 'ok';

  return `Expecting ${b} from ${JSON.stringify(a)} but get ${val}`;
});

// Time complexity: O(n) where n is the number of elements
// Space complexity: O(1) as only a few variables for f, s, and sum