LeetCode Problem 1

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

LeetCode 1, Two Sum

Problem Understanding

The problem gives us an integer array called nums and another integer called target. Our task is to find two different elements in the array whose sum equals target, then return their indices.

The important detail is that the output must contain indices, not the values themselves. For example, if the numbers 2 and 7 add up to 9, we must return [0, 1] because those are the positions of the numbers in the array.

The problem also guarantees that there is exactly one valid solution. This guarantee simplifies the implementation because we do not need to handle situations where no answer exists or where multiple answers are possible.

The constraint 2 <= nums.length <= 10^4 tells us that the array can become fairly large. A quadratic solution with nested loops would still technically run for this input size, but the follow-up question explicitly asks for something better than O(n^2) time complexity. This strongly suggests that we should use a more efficient lookup structure.

The values inside the array and the target can be negative, positive, or zero. Therefore, we cannot rely on sorting assumptions or positivity properties.

Several edge cases are important:

• The same value may appear multiple times, such as [3,3].
• The correct pair may involve negative numbers.
• The answer may appear near the beginning or near the end of the array.
• We are not allowed to use the same element twice, meaning one index cannot be reused.
• Since exactly one solution exists, the algorithm can safely return immediately once the pair is found.

Approaches

Brute Force Approach

The most direct solution is to check every possible pair of numbers.

We can use two nested loops. The outer loop chooses the first number, and the inner loop checks every number that comes after it. For each pair, we compute the sum and compare it with target.

If the sum matches the target, we return the two indices.

This approach is correct because it exhaustively checks all valid pairs. Since every possible combination is considered, the correct answer will eventually be found.

However, this method is inefficient for large arrays. If the array has n elements, then we may need to check approximately n^2 / 2 pairs. That gives a time complexity of O(n^2).

Optimal Hash Map Approach

The key observation is that for every number x, we already know the number we need to complete the target:

$x + y = target$

Rearranging gives:

$y = target - x$$t$$a$$r$$g$

Instead of searching the entire array for y, we can store previously seen numbers in a hash map.

As we iterate through the array:

• We compute the complement target - current_number.
• We check whether that complement already exists in the hash map.
• If it does, we have found the answer immediately.
• Otherwise, we store the current number and its index for future lookups.

A hash map provides average O(1) lookup time, allowing the entire algorithm to run in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Checks every possible pair using nested loops
Optimal	O(n)	O(n)	Uses a hash map for constant-time complement lookup

Algorithm Walkthrough

1. Create an empty hash map called seen_numbers.

The hash map will store numbers as keys and their indices as values. This allows fast lookup to determine whether a needed complement has already appeared earlier in the array. 2. Iterate through the array using both index and value.

At each step, we process one number and determine whether it can form the target sum with a previously seen number. 3. Compute the complement.

For the current number num, calculate:

$complement = target - num$

This is the exact value needed to complete the pair. 4. Check whether the complement exists in the hash map.

If the complement is already stored, then we have previously encountered a number that pairs with the current number to produce the target sum. 5. Return the stored index and the current index.

Since the problem guarantees exactly one valid answer, we can immediately return the pair once found. 6. If the complement is not found, store the current number and index in the hash map.

This prepares the current value to potentially serve as the complement for a future number.

Why it works

The algorithm maintains the invariant that the hash map contains all numbers encountered before the current position, along with their indices.

When processing a number num, we compute the exact value needed to reach the target. If that value already exists in the hash map, then we know a valid pair has been found.

Because every element is processed exactly once, and because the correct solution is guaranteed to exist, the algorithm always returns the correct pair.

Python Solution

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen_numbers = {}

        for index, num in enumerate(nums):
            complement = target - num

            if complement in seen_numbers:
                return [seen_numbers[complement], index]

            seen_numbers[num] = index

        return []

The implementation starts by creating an empty dictionary called seen_numbers. In Python, dictionaries provide average O(1) lookup and insertion time, making them ideal for this problem.

The enumerate() function is used so we can access both the current index and value during iteration.

For each number, the code calculates the complement needed to reach the target. It then checks whether that complement has already been seen.

If the complement exists in the dictionary, the stored index and current index form the answer, so the function immediately returns them.

If the complement does not exist, the current number and index are inserted into the dictionary so future elements can use them.

The final return [] is technically unnecessary because the problem guarantees a valid answer, but including it makes the function syntactically complete and defensive.

Go Solution

func twoSum(nums []int, target int) []int {
    seenNumbers := make(map[int]int)

    for index, num := range nums {
        complement := target - num

        if previousIndex, exists := seenNumbers[complement]; exists {
            return []int{previousIndex, index}
        }

        seenNumbers[num] = index
    }

    return []int{}
}

The Go implementation follows the exact same algorithmic logic as the Python version.

Go maps are used instead of Python dictionaries. The syntax:

previousIndex, exists := seenNumbers[complement]

retrieves both the stored value and a boolean indicating whether the key exists.

The solution returns a slice of integers containing the two indices.

Integer overflow is not a concern here because the constraints fit safely within Go's standard integer range on LeetCode platforms.

Worked Examples

Example 1

Input:

nums = [2,7,11,15]
target = 9

Iteration	Current Number	Complement	Hash Map Before	Action
0	2	7	{}	Store 2:0
1	7	2	{2:0}	Complement found, return [0,1]

Output:

[0,1]

Example 2

Input:

nums = [3,2,4]
target = 6

Iteration	Current Number	Complement	Hash Map Before	Action
0	3	3	{}	Store 3:0
1	2	4	{3:0}	Store 2:1
2	4	2	{3:0, 2:1}	Complement found, return [1,2]

Output:

[1,2]

Example 3

Input:

nums = [3,3]
target = 6

Iteration	Current Number	Complement	Hash Map Before	Action
0	3	3	{}	Store 3:0
1	3	3	{3:0}	Complement found, return [0,1]

Output:

[0,1]

This example is important because it demonstrates that duplicate values are handled correctly without reusing the same element.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed once, and hash map operations are average O(1)
Space	O(n)	The hash map may store up to all elements in the array

The algorithm performs a single pass through the array. During each iteration, only constant-time operations are performed, specifically hash map lookup and insertion.

The extra memory usage comes from storing previously seen numbers in the hash map. In the worst case, the map may contain nearly every element before the answer is found.

Test Cases

solution = Solution()

# Provided examples
assert solution.twoSum([2, 7, 11, 15], 9) == [0, 1]  # Basic example
assert solution.twoSum([3, 2, 4], 6) == [1, 2]       # Pair appears later
assert solution.twoSum([3, 3], 6) == [0, 1]          # Duplicate values

# Smallest valid input size
assert solution.twoSum([1, 2], 3) == [0, 1]          # Minimum array length

# Negative numbers
assert solution.twoSum([-1, -2, -3, -4, -5], -8) == [2, 4]  # Negative values

# Zero values
assert solution.twoSum([0, 4, 3, 0], 0) == [0, 3]   # Two zeros

# Target formed by positive and negative number
assert solution.twoSum([-3, 4, 3, 90], 0) == [0, 2]  # Mixed signs

# Large values within constraints
assert solution.twoSum([1000000000, -1000000000], 0) == [0, 1]  # Extreme values

# Pair at the end
assert solution.twoSum([1, 2, 3, 4, 9], 13) == [3, 4]  # Solution near end

# Repeated numbers with distinct indices
assert solution.twoSum([5, 5, 1], 10) == [0, 1]  # Same value twice

Test	Why
[2,7,11,15], 9	Standard example from the problem
[3,2,4], 6	Validates non-adjacent matching pair
[3,3], 6	Ensures duplicates are handled correctly
[1,2], 3	Tests minimum input size
Negative number case	Confirms algorithm works with negatives
[0,4,3,0], 0	Ensures zero values work correctly
Mixed positive and negative	Verifies complement logic across signs
Extreme integer values	Confirms safe handling of constraint limits
Pair at end of array	Ensures full traversal works
Repeated values	Confirms distinct indices are used

Edge Cases

Duplicate Values

An important edge case occurs when the correct answer uses the same numeric value twice, such as [3,3] with target 6.

A buggy implementation might accidentally reuse the same index twice. This solution avoids that problem because it only checks previously seen elements before inserting the current one into the hash map. As a result, the two indices are always distinct.

Negative Numbers

Some solutions incorrectly assume all numbers are positive and attempt optimizations based on sorting or early stopping.

For example:

nums = [-1, -2, -3, -4, -5]
target = -8

The hash map approach works naturally with negative numbers because it relies only on arithmetic subtraction and constant-time lookup.

Multiple Occurrences of the Same Number

Consider:

nums = [5,5,1]
target = 10

The algorithm correctly stores the first 5 in the hash map. When the second 5 is processed, the complement 5 already exists, so the correct pair [0,1] is returned.

This demonstrates why insertion order matters. We must check for the complement before inserting the current value.

Solution Near the End of the Array

Some incorrect implementations stop too early or make assumptions about where the answer appears.

For example:

nums = [1,2,3,4,9]
target = 13

The correct pair is at the end of the array. Since the algorithm processes every element sequentially until a match is found, it correctly handles this scenario.