Optimizing Combinatorial Logic with TypeScript

Introduction

Hello there! Brace yourself as we dive into a tantalizing problem that involves list manipulation and combinatorial logic . This problem centers around finding combinations in a given list whose sum is equivalent to a specified target value . Are you ready for a thrilling endeavor? Great! Let's jump into the world of number theory and TypeScript .

Task Statement

-10^6

Estimating Program Evaluation Time

O(N^4)

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

To effectively solve this problem using TypeScript, we employ an optimized approach with a time complexity of $O(N^2)$ , leveraging maps for swift lookups.

Conceptual Breakdown:

Store Pair Sums: We initialize a Map to keep track of all possible pairs of numbers and their sums. This map's keys will be these sums, and the values will be the pairs of indices that make up the sums.
Finding Complement Pairs: For each pair of numbers in the array, calculate the difference between the target sum and the current pair’s sum. This difference represents the sum needed from another pair of numbers.
Verify Distinct Indices: Using our map, check if there exists a pair in the array which adds up to this difference and ensure that none of these indices are overlapping with the initial pair. If such pairs exist, we return these four numbers as our result.

Why This Works:

Efficiency: Using a Map allows for constant time complexity on average for insertion and lookup operations, dramatically speeding up our process compared to a brute-force solution.
Scalability: Even with the maximum limit of 1,000 entries, this method ensures prompt execution well within the acceptable limits.

The initial strategic move is to initialize an empty Map. We'll use this Map to store sums of all pairs of numbers in the list as keys, with indices of the number pairs as the corresponding values. This strategy will prove beneficial when we search for pairs that meet our conditions later.

TypeScript

function findQuadSum(targetSum: number, numbers: number[]): number[] {
    const length: number = numbers.length;
    const sumMap: Map<number, [number, number][]> = new Map();
}

function findQuadSum(targetSum: number, numbers: number[]): number[] {
    const length: number = numbers.length;
    const sumMap: Map<number, [number, number][]> = new Map();
}

Now, let's populate the Map. For each pair of integers in the array, we'll calculate their sum and store it as a key in the Map, using the indices of the pair as the values.

TypeScript

function findQuadSum(targetSum: number, numbers: number[]): number[] {
    const length: number = numbers.length;
    const sumMap: Map<number, [number, number][]> = new Map();
    
    for (let i = 0; i < length - 1; ++i) {
        for (let j = i + 1; j < length; ++j) {
            const pairwiseSum: number = numbers[i] + numbers[j];
            if (!sumMap.has(pairwiseSum)) {
                sumMap.set(pairwiseSum, []);
            }
            sumMap.get(pairwiseSum)!.push([i, j]);
        }
    }
}

function findQuadSum(targetSum: number, numbers: number[]): number[] {
    const length: number = numbers.length;
    const sumMap: Map<number, [number, number][]> = new Map();
    
    for (let i = 0; i < length - 1; ++i) {
        for (let j = i + 1; j < length; ++j) {
            const pairwiseSum: number = numbers[i] + numbers[j];
            if (!sumMap.has(pairwiseSum)) {
                sumMap.set(pairwiseSum, []);
            }
            sumMap.get(pairwiseSum)!.push([i, j]);
        }
    }
}

Finding the Quad

On to the last step! We will now scan all pairs, and for each, we will calculate the difference between the target sum and the pair sum, searching for this difference value in the Map. For successful searches, we validate that the elements do not belong to more than one pair. If we find such combinations, we return the four numbers. However, if we traverse all pairs and fail to find a suitable set, we return an empty array.

TypeScript

function findQuadSum(targetSum: number, numbers: number[]): number[] {
    // Step 1: Initialize the Map
    const length: number = numbers.length;
    const sumMap: Map<number, [number, number][]> = new Map();
    
    // Step 2: Populate the Map with the sums of all pairs
    for (let i = 0; i < length - 1; ++i) {
        for (let j = i + 1; j < length; ++j) {
            const pairwiseSum: number = numbers[i] + numbers[j];
            if (!sumMap.has(pairwiseSum)) {
                sumMap.set(pairwiseSum, []);
            }
            sumMap.get(pairwiseSum)!.push([i, j]);
        }
    }

    // Step 3: Iterate over the sums
    for (const sum of sumMap.keys()) {
        const complement: number = targetSum - sum;
        if (sumMap.has(complement)) {
            const pairs1: [number, number][] = sumMap.get(sum)!;
            const pairs2: [number, number][] = sumMap.get(complement)!;

            for (const pair1 of pairs1) {
                for (const pair2 of pairs2) {
                    const [a, b] = pair1;
                    const [c, d] = pair2;

                    // Ensure all indices are distinct
                    if (a !== c && a !== d && b !== c && b !== d) {
                        return [numbers[a], numbers[b], numbers[c], numbers[d]];
                    }
                }
            }
        }
    }

    return [];
}

// Example usage:
const numbers: number[] = [5, 15, 2, 7, 8, 4];
const target: number = 24;
console.log(findQuadSum(target, numbers)); // Output: [ 5, 7, 8, 4 ]

function findQuadSum(targetSum: number, numbers: number[]): number[] {
    // Step 1: Initialize the Map
    const length: number = numbers.length;
    const sumMap: Map<number, [number, number][]> = new Map();
    
    // Step 2: Populate the Map with the sums of all pairs
    for (let i = 0; i < length - 1; ++i) {
        for (let j = i + 1; j < length; ++j) {
            const pairwiseSum: number = numbers[i] + numbers[j];
            if (!sumMap.has(pairwiseSum)) {
                sumMap.set(pairwiseSum, []);
            }
            sumMap.get(pairwiseSum)!.push([i, j]);
        }
    }

    // Step 3: Iterate over the sums
    for (const sum of sumMap.keys()) {
        const complement: number = targetSum - sum;
        if (sumMap.has(complement)) {
            const pairs1: [number, number][] = sumMap.get(sum)!;
            const pairs2: [number, number][] = sumMap.get(complement)!;

            for (const pair1 of pairs1) {
                for (const pair2 of pairs2) {
                    const [a, b] = pair1;
                    const [c, d] = pair2;

                    // Ensure all indices are distinct
                    if (a !== c && a !== d && b !== c && b !== d) {
                        return [numbers[a], numbers[b], numbers[c], numbers[d]];
                    }
                }
            }
        }
    }

    return [];
}

// Example usage:
const numbers: number[] = [5, 15, 2, 7, 8, 4];
const target: number = 24;
console.log(findQuadSum(target, numbers)); // Output: [ 5, 7, 8, 4 ]

Note that since the integers in the list are distinct, the pairs in pairs1 and pairs2 do not share the same indices. Therefore, the nested loop on the 17th line will typically find a valid combination quickly, often within just a few iterations.

Incredible job! The successful completion of this task confirms your understanding of how data structures like Maps can be employed to address the demands of a problem efficiently and effectively in TypeScript. TypeScript’s static typing not only aids in catching errors during development but also clarifies your code's intent, making it more readable and maintainable. Hang on to this skill, as arrays, combinatorial logic, and proficient coding are invaluable tools in a programmer's arsenal.

Why don't you take this newfound knowledge further and put it into practice? Test yourself and aim to master these insights by tackling similar problems. Use this lesson as your guide and don't hesitate to experiment with array and target sum values. Keep learning, keep enriching, and happy coding!

Introduction

Task Statement

Estimating Program Evaluation Time

Join the 1M+ learners on CodeSignal

Solution Explanation

Initializing the Map

Populating the Map

Finding the Quad

Lesson Summary