Introduction:

The "Two Sum" problem is a classic algorithmic puzzle that challenges us to find a pair of numbers within an array that adds up to a target. While it may seem simple, this problem holds significant importance in the world of coding interviews and algorithm design.

Approach:

We'll employ a smart approach using a dictionary (hashmap) that offers an efficient solution with a time complexity of O(n). This technique simplifies the problem into a single pass through the array, making it a valuable tool in your algorithmic toolkit.Create a num_indices dictionary to store values and their indices.

Code:

class Solution:
    def twoSum(self, nums, target):
        num_indices = {}
        for idx, num in enumerate(nums):
            complement = target - num
            if complement in num_indices:
                return [num_indices[complement], idx]
            num_indices[num] = idx

this is a screenshot of my solution from Leet code.

You can access it using the following link

https://leetcode.com/submissions/detail/1076613698/

Explanation:

• Calculate the complement for each number in the nums list: complement = target - num.

• Check if the complement exists in the num_indices dictionary.

• If found, return the indices of the pair that adds up to the target.

• This efficient approach tracks values and their indices as we iterate through the array.

Examples:

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Complexity:

The time complexity is O(n) since we iterate through the list once

The space complexity is O(n) because we use a dictionary to store values.

Conclusion:

In conclusion, the "Two Sum" problem might appear simple, but it serves as a gateway to understanding critical concepts in algorithm design. By employing a dictionary-based approach, we can efficiently find pairs of numbers that sum up to a given target. The ability to devise such efficient solutions is a key skill in software development and technical interviews. Understanding this problem equips us with valuable problem-solving techniques and insights into time and space complexity, all of which are invaluable assets in the world of coding.