Leetcode 1 Two Sum

Two Sum – 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. The answer can be returned in any order.

Examples

• Input: nums = [2, 7, 11, 15], target = 9
• Output: [0, 1]
• Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Constraints

• Only one valid answer exists.
• Each input would have exactly one solution.

Brute Force Approach

The brute force approach involves checking every possible pair of elements in the array to see if their sum equals the target. Here’s the code for the brute force solution:

Python:

def two_sum_brute_force(nums, target):
    """
    Brute force method to find two numbers that add up to the target.
    Time complexity: O(n^2)
    Space complexity: O(1)
    """
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return None

Time Complexity:
In the worst case, this solution will run in O(n²) time, where n is the number of elements in the input array. This is because we have nested loops that iterate over all possible pairs.

Space Complexity:
The space complexity of this brute force approach is O(1), as we are not using any additional data structures.

Efficient Approach

A more efficient way to solve the Two Sum problem is by using a hash table (dictionary in Python) to store the elements we have seen so far and their indices. Here’s the code for the efficient solution:

Python:

def two_sum_optimized(nums, target):
    """
    More efficient method using a dictionary to store complements.
    Time complexity: O(n)
    Space complexity: O(n)
    """
    num_dict = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_dict:
            return [num_dict[complement], i]
        num_dict[num] = i
    return None

Time Complexity:
This efficient approach has a time complexity of O(n), where n is the number of elements in the input array. We iterate through the array once and perform constant-time lookups in the dictionary.

Space Complexity:
The space complexity of the efficient approach is O(n) in the worst case because we may need to store all n elements in the dictionary.

Conclusion

When addressing the Two Sum problem, selecting the suitable method hinges on the specific constraints of the problem and the significance of optimizing runtime and space utilization. While the brute force method is straightforward, its efficiency diminishes notably for larger arrays, given its time complexity of O(n²). Conversely, the efficient approach, employing a hash table, offers a vastly improved time complexity of O(n) and is typically favored in practical applications. Whether navigating coding interviews or competitive programming challenges, being well-versed in both techniques is imperative, allowing one to judiciously select the most fitting solution based on the problem’s constraints. Feel free to reach out with any inquiries.