How to find the minimal possible sum of two distinct elements in an array with TypeScript

1 Answer

0 votes
/*
    Goal:
    -----
    Find the minimal value of (a[i] + a[j]) for any two distinct elements in an array.

    Efficient Strategy (O(n)):
    --------------------------
    The smallest possible sum of two distinct elements is obtained by:
        - finding the smallest element
        - finding the second smallest element
    Because any other pair must be >= one of these two.

    We scan the array once, keeping track of:
        - min1  = smallest element seen so far
        - min2  = second smallest element seen so far
*/

// A function that computes the minimal sum of two distinct elements.
function minimal_two_sum(arr: number[]): number {
    // Handle edge case: need at least two elements
    if (arr.length < 2) {
        throw new Error("Array must contain at least two elements.");
    }

    // Initialize min1 and min2 to very large values
    let min1: number = Infinity;
    let min2: number = Infinity;

    // Single pass through the array
    for (const x of arr) {
        const value: number = x;

        if (value < min1) {
            // value becomes the new smallest; old min1 becomes min2
            min2 = min1;
            min1 = value;
        } else if (value < min2) {
            // value is not the smallest, but smaller than the second smallest
            min2 = value;
        }
    }

    // The minimal sum of two distinct elements
    return min1 + min2;
}

const arr: number[] = [7, -3, 10, 1, 5, 2, 4];

try {
    const result: number = minimal_two_sum(arr);
    console.log("Minimal sum of two elements:", result);
} catch (e: any) {
    console.error("Error:", e.message);
}


/*
run:

Minimal sum of two elements: -2

*/

 



answered Jul 21 by avibootz

Related questions

...