Two Sum | Leetcode 1 | Explained with Images

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Here’s the [Problem Link] to begin with.

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]

Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹

Only one valid answer exists.

BRUTE FORCE SOLUTION

1. Problem Statement

The task is to find two numbers in an array nums such that they add up to a specific target target. The function should return the indices of these two numbers. It’s guaranteed that exactly one solution exists, and you may not use the same element twice.

Input:

• nums: A list of integers.
• target: An integer representing the target sum.

Output:

• A list containing two integers, which are the indices of the two numbers in nums that add up to target.

2. Intuition and Approach

The provided code implements a brute-force approach to solve the problem:

1. Nested Loops: Iterate over each element in nums using two nested loops.
2. Sum Check: For each pair of elements (nums[i], nums[j]), check if their sum equals the target.
3. Return Indices: If a matching pair is found, return their indices [i, j] immediately.

This method checks all possible pairs in the array until it finds the pair that sums up to the target.

3. Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(0, n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]

1. Initialization:
   1. n = len(nums): Stores the length of the input array nums.
2. Outer Loop (for i in range(0, n)):
   1. Iterates over each element in the array starting from the first element.
   2. i represents the index of the first number in the potential pair.
3. Inner Loop (for j in range(i + 1, n)):
   1. For each element nums[i], iterates over the subsequent elements in the array.
   2. j represents the index of the second number in the potential pair.
   3. Starts from i + 1 to avoid using the same element twice and to prevent redundant checks.
4. Sum Check (if nums[i] + nums[j] == target):
   1. Checks if the sum of nums[i] and nums[j] equals the target.
   2. If the condition is true, the pair has been found.
5. Return Statement (return [i, j]):
   1. Returns a list containing the indices [i, j] of the two numbers that add up to the target.
   2. The function exits immediately after finding the first valid pair.

4. Dry Run

Let’s go through the code step by step, using images to illustrate the detailed dry run process.

5. Edge Cases

• No Solution Exists:
  • According to the problem statement, exactly one solution exists, so this case doesn’t need to be handled.
• Negative Numbers:
  • The code works correctly with negative numbers as it simply adds and compares sums.
• Multiple Valid Pairs:
  • If multiple pairs add up to the target, the function returns the first pair found due to the order of iteration.

6. Time and Space Complexity

• Time Complexity:O(n²)
  • The nested loops result in checking every pair once.
  • For an array of size n, there are approximately n(n−1)/2 pairs.
• Space Complexity:O(1)
  • The algorithm uses a constant amount of extra space regardless of the input size.
  • The output list [i, j] has a fixed size of 2.

OPTIMAL SOLUTION

1. Problem Statement

Given an array of integers nums and an integer target, the task is to find indices of two numbers in the array such that they add up to the target. It is guaranteed that exactly one pair of numbers adds up to the target, and each number can be used at most once.

Input:

• nums: A list of integers.
• target: An integer representing the target sum.

Output:

• A list containing two integers, the indices of the two numbers in nums that add up to target.

2. Intuition and Approach

To solve this problem efficiently, a hash map (dictionary) can be used to keep track of the numbers encountered so far and their indices. The idea is to:

1. Iterate through the array:
   • For each element nums[i], calculate the complement remaining = target – nums[i], which is the number needed to reach the target.
2. Check for the complement:
   • If the complement remaining is already in the hash map, it means a previous number can be paired with the current number to reach the target.
3. Return the result:
   • When such a pair is found, return the indices of the complement and the current number.
4. Update the hash map:
   • If the complement is not found, store the current number and its index in the hash map for future reference.

This approach allows finding the required pair in a single pass through the array, resulting in an efficient O(n) time complexity.

3. Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        hash_map = dict()
        for i in range(n):
            remaining = target - nums[i]
            if remaining in hash_map:
                return [hash_map[remaining], i]
            hash_map[nums[i]] = i

• Initialization:
  • n = len(nums): Determine the length of the array.
  • hash_map = dict(): Initialize an empty dictionary to store numbers and their indices.
• Iteration over the array:
  • for i in range(n):: Loop through each index i in the array.
    • Calculate the complement:
      • remaining = target – nums[i]: Compute the number needed to reach the target with the current number.
    • Check if the complement exists:
      • if remaining in hash_map:: If the complement is in the hash map, a valid pair is found.
        • Return the indices:
          • return [hash_map[remaining], i]: Return the indices of the complement and the current number.
    • Update the hash map:
      • hash_map[nums[i]] = i: Add the current number and its index to the hash map for future reference.

4. Dry Run

Let’s go through the code step by step, using images to illustrate the detailed dry run process.

5. Edge Cases

• Negative Numbers:
  • The method works with negative numbers since addition and subtraction are valid for negative values.
• Multiple Valid Pairs:
  • If multiple pairs add up to the target, the function returns the first pair found during iteration.
• Single Element:
  • Since the problem guarantees exactly one solution and that we cannot use the same element twice, arrays with fewer than two elements are not considered.

6. Time and Space Complexity

• Time Complexity:O(n)
  • The array is traversed once, and each lookup or insertion in the hash map is O(1) on average.
• Space Complexity:O(n)
  • In the worst case, all elements are stored in the hash map.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.