1. Two Sum - Detailed Explanation

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the target.

You may assume that each input would have exactly one solution, and you may not use the same element twice. The answer can be returned in any order.

Example Inputs & Outputs

1. Example 1:

   • Input: nums = [2, 7, 11, 15], target = 9
   • Output: [0, 1]
   • Explanation:
     The sum of nums[0] and nums[1] is 2 + 7 = 9.

2. Example 2:

   • Input: nums = [3, 2, 4], target = 6
   • Output: [1, 2]
   • Explanation:
     The sum of nums[1] and nums[2] is 2 + 4 = 6.

3. Example 3:

   • Input: nums = [3, 3], target = 6
   • Output: [0, 1]
   • Explanation:
     The sum of nums[0] and nums[1] is 3 + 3 = 6. Below is the constraints section in a properly formatted Markdown snippet using LaTeX for the mathematical expressions:

Constraints:

Exactly one solution exists.

Hints Before the Full Solution

1. Hint 1:
   Consider the brute-force approach first—try every pair of numbers to see if they add up to the target. This solution is simple but not efficient.

2. Hint 2:
   To improve efficiency, think about using a hash table (or dictionary) to store the numbers you’ve seen so far. As you iterate through the list, calculate the complement ( \text{complement} = \text{target} - \text{num} ) and check if it exists in the hash table.

Approaches to Solve the Problem

1. Brute Force Approach

Idea:

• Use two nested loops to check every possible pair of numbers.
• If the sum of any two numbers equals the target, return their indices.

Pseudo-code:

def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

Drawback:

• Time Complexity: (O(n^2)). This approach is inefficient for large input arrays.

2. Optimal Approach Using a Hash Table

Idea:

• Iterate through the array once.

• For each element, compute its complement:

  \text{complement} = \text{target} - \text{num}

• Check if the complement is already in the hash table:

  • If yes, return the indices.
  • If no, store the current number and its index in the hash table.

Pseudo-code:

def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

Advantages:

• Time Complexity: (O(n)) on average.
• Space Complexity: (O(n)) due to the extra hash table.

Code Implementation