Day 3 – 100 days of DSA challenge

Challenge: Two Sum

Welcome to Day 3 of our 100 Days DSA Challenge! 🚀 Today, we tackle the “Two Sum” problem, a classic algorithmic challenge that explores the efficiency of finding pairs in an array that add up to a specific target.

The Challenge:

Given an array of integers nums and an integer target, your task is to return the indices of the two numbers in the array such that they add up to the target. Each input has exactly one solution, and the same element cannot be used twice.

Example:

const nums = [2, 7, 11, 15];
const target = 9;
// Output: [0, 1] (because nums[0] + nums[1] == 9)

Challenge Yourself:

Before diving into the solution, challenge yourself to come up with your approach. Can you optimize the code further?

const twoSum = (nums, target) => {
    let obj = {};
    for (let i = 0; i < nums.length; i++) {
        const secondNumber = target - nums[i];
        if (obj.hasOwnProperty(secondNumber)) {
            return [obj[secondNumber], i];
        }
        obj[nums[i]] = i;
    }
    return [];
}

Solution Logic:

1. Initialize an Empty Object (obj):
   • We start by creating an empty object called obj. This object will serve as a “memory” to store the numbers we encounter along with their indices.

let obj = {};

2. Iterate Through the Array:
   • We iterate through the given array (nums) using a for loop.

for (let i = 0; i < nums.length; i++) { // Logic inside the loop comes next... }

3. Calculate the Second Number:
   • For each number in the array, we calculate the second number needed to reach the target by subtracting the current number from the target.

const secondNumber = target - nums[i];

4. Check if the Second Number Exists in the Object (obj):
   • We check if the obj object already contains the second number as a property.

if (obj.hasOwnProperty(secondNumber)) { // If yes, we found our pair! return [obj[secondNumber], i]; }

5. Store the Current Number and Index in the Object (obj):
   • If the second number is not found, we store the current number and its index in the obj object.

obj[nums[i]] = i;

6. Repeat Until Solution is Found:
   • We repeat these steps for each element in the array until we find a pair of numbers that add up to the target.
7. Return Empty Array if No Solution is Found:
   • If the loop completes without finding a solution, we return an empty array.

return [];

Explanation:

• The logic cleverly uses a hash table (implemented as an object in JavaScript) to keep track of numbers and their indices as we iterate through the array.
• By checking for the existence of the second number in the object, we efficiently determine if a pair that adds up to the target has been found.
• This solution has a time complexity of O(n), making it efficient for large arrays.

In essence, it’s a smart and efficient approach that leverages the concept of complement numbers to find the solution in a single pass through the array.

Conclusion:

Congratulations on completing Day 3 of our DSA Challenge! The journey into algorithmic problem-solving continues. Stay tuned for tomorrow’s challenge, and keep the coding spirit alive!

Happy coding! 🌟💻

#100DaysDSAChallenge #DataStructures #Algorithms #ProgrammingCommunity #CodeNewbie