DEV Community

Cover image for Two Sum Problem’ on LeetCode
Neeraj Kumar
Neeraj Kumar

Posted on

Two Sum Problem’ on LeetCode

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

Go Function Signature:
func twoSum(nums []int, target int) []int
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:

nput: nums = [3,3], target = 6
Output: [0,1]
Solution 1: Brute Force Approach

Solution 1: Brute-Force Approach (Nested Loops)
In this approach, you check each pair of elements to see if they sum up to the target. This involves iterating through the array with two nested loops.

Code

func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] + nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}
Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

Solution 2: Two-Pass Hash Table
This solution improves on the brute-force approach by using a hash map to store each element's value and index in the first pass. In the second pass, you check if the complement (i.e., target - num) exists in the hash map.

Code

func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)
    // First pass: populate the map with each element's index
    for i, num := range nums {
        numMap[num] = i
    }
    // Second pass: check for the complement
    for i, num := range nums {
        if j, ok := numMap[target - num]; ok && i != j {
            return []int{i, j}
        }
    }
    return nil
}
Enter fullscreen mode Exit fullscreen mode

Solution 3: One-Pass Hash Table (Optimal Solution)

  • This approach combines both insertion and lookup in a single pass. As you iterate through the array, you:

  • Check if the complement (i.e., target - num) exists in the hash map.

  • If the complement is found, return the indices.

  • If not, add the current element and its index to the hash map for future lookups.
    Code

func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)
    for i, num := range nums {
        if j, ok := numMap[target - num]; ok {
            return []int{j, i}
        }
        numMap[num] = i
    }
    return nil
}
Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

  • Time Complexity: 𝑂(𝑛)

    • Only one pass through the array is required, making this approach linear in time complexity.
  • Space Complexity:o(n)

    • The hash map stores each element and its index.

Pros and Cons
Pros: The most efficient approach for time complexity, with a clean and compact implementation.
Cons: None, as it achieves optimal time and space complexity for this problem.

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more →

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs