Skip to content

Instantly share code, notes, and snippets.

@motss
Last active October 22, 2020 05:31
Show Gist options
  • Save motss/2ed36e253c2219d4512658b27da61891 to your computer and use it in GitHub Desktop.
Save motss/2ed36e253c2219d4512658b27da61891 to your computer and use it in GitHub Desktop.
Find the sum of 2 smallest numbers
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment