Problem Solving: LeetCode #1 Two Sum

Problem Statement

The problem is simple: 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 can assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Let's look at an example to understand the problem better.

Input:

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

Output:

[0, 1]

In this example, nums[0] + nums[1] equals 9 (2 + 7 = 9), so we return the indices [0, 1].

Approach to Solution

Brute Force Method

The brute force method involves checking each pair of numbers to see if they add up to the target. This is simple but inefficient for large arrays because it has a time complexity of O(n²).

function twoSum($nums, $target) {
    $n = count($nums);

    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            if ($nums[$i] + $nums[$j] == $target) {
                return [$i, $j];
            }
        }
    }

    return [];
}

Using a HashMap

A more efficient solution uses a HashMap to store the numbers we have seen so far and their indices. This way, we can check if the complement of the current number (i.e., target - nums[i]) exists in the HashMap.

Here’s how we can implement this in PHP:

1. Initialize an empty HashMap to store numbers and their indices.
2. Loop through the array, checking if the complement of the current number exists in the HashMap.
3. If it does, return the indices of the current number and the complement.
4. If it doesn’t, add the current number and its index to the HashMap.

Let’s write the code for this approach.

function twoSum($nums, $target) {
    $numMap = [];

    foreach ($nums as $i => $num) {
        $complement = $target - $num;

        if (array_key_exists($complement, $numMap)) {
            return [$numMap[$complement], $i];
        }

        $numMap[$num] = $i;
    }

    return [];
}

Explanation

• Creating a map: We use a map called numMap to keep track of each number and its index as we iterate through the list.
• Looping through nums: For each number, we calculate its complement (i.e., target - num).
• Checking the map: We check if this complement is already in numMap. If it is, we have found our pair, and we return their indices.
• Storing in the map: If the complement is not found, we store the current number and its index in numMap.

Conclusion

The HashMap approach significantly improves the efficiency of the solution to O(n), making it suitable for large input arrays. This method is a standard technique for problems involving pairs or complements, so it's worth getting comfortable with it.

By solving problems like Two Sum using PHP, you not only prepare for coding interviews but also sharpen your problem-solving and programming skills. Happy coding!