ByteBunny
ByteBunny
leetcode

LeetCode 1. Two Sum

blog.title
0 views
5 min read
#leetcode
Table of Content

LeetCode 1. Two Sum

Difficulty: Easy
Topics: Arrays, HashTable

In the realm of coding challenges, Two Sum is often considered the "Hello World" of LeetCode. Just as "Hello World" is the classic starting point for learning a new programming language, Two Sum serves as a fundamental problem that introduces you to the world of algorithmic thinking and problem-solving on LeetCode.

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 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.

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]

Example 3:

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

Constraints

  • 2 ≤ nums.length ≤ 104
  • -109 ≤ nums[i] ≤ 109
  • -109 ≤ target ≤ 109
  • Only one valid answer exists.

Approaches and Solutions

Brute Force ❌

Approach

The brute force approach involves checking every possible pair of numbers to see if they add up to the target.

Algorithm

  1. Iterate through each element i of the array.
  2. For each element i, iterate through the subsequent elements j.
  3. Check if nums[i] + nums[j] == target.
  4. If they add up to the target, return the indices [i, j].

Code

Java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        return null;
    }
}

Complexity Analysis

  • Time complexity: O(n2)
    → For each element, we try to find its complement by looping through the rest of the array which takes O(n) time. Therefore, the time complexity is O(n2).
  • Space complexity: O(1)
    → The space required does not depend on the size of the input array, so only constant space is used.

One-Pass Hash Table ✅

Approach

The one-pass hash table approach allows us to find the solution in a single iteration through the array. While iterating and inserting elements into the hash table, we simultaneously check if the current element's complement (target - current element) is already present in the hash table. If the complement exists, we have found the solution and can return the indices immediately.

Algorithm

  1. Initialize an empty hash table map.
  2. Iterate through each element i in the array.
  3. Calculate the complement as complement = target - nums[i].
  4. Check if complement exists in the hash table:
    • If it exists, return the indices [map.get(complement), i].
    • If it doesn't exist, store the current element nums[i] in the hash table with its index map.put(nums[i], i).
  5. If no solution is found by the end of the iteration, return null.

Code

Java
import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        return null;
    }
}

Complexity Analysis

  • Time complexity: O(n)
    → We traverse the array containing n elements exactly once. Each lookup in the hash table costs O(1) time, so the overall time complexity is O(n).

  • Space complexity: O(n)
    → The extra space required depends on the number of elements stored in the hash table, which stores at most n elements. Therefore, the space complexity is O(n).

What's Next?