LeetCode - Two Sum Solution with Code

post-thumb

The Two Sum problem on LeetCode is a popular problem for practising and improving your coding skills. It involves finding two numbers in an array that add up to a specific target number.

Grow Your Tech Career. Meet Expert coaches from top companies

Meet A MAANG Coach

Here is a step-by-step guide on how to solve the Two Sum problem on LeetCode, including complete code examples.

Understand the problem:

The first step to solving any problem is to thoroughly understand the problem statement. In this case, the problem involves finding two numbers in an array that add up to a specific target number. Make sure you understand the input, output, and any constraints or limitations of the problem.

Plan your solution:

Now that you understand the problem, it’s time to come up with a plan to solve it. One approach to solving this problem is to use a brute force method, which involves checking every possible combination of two numbers in the array to see if they add up to the target number. Another approach is to use a more efficient algorithm, such as a hash map, which can greatly reduce the time complexity of the solution.

Implement your solution:

Now that you have a plan, it’s time to start coding. Begin by writing a function that takes in the array and target number as input and returns the indices of the two numbers that add up to the target. If you are using a brute force approach, you will need to use a nested loop to iterate through all possible combinations of two numbers in the array. Here is an example of how to implement this solution in Python.

def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

If you are using a hash map, you can iterate through the array and add each element to the hash map, then check if the target number minus the current element is present in the hash map. If it is, you have found the two numbers that add up to the target. Here is an example of how to implement this solution in Python.

def twoSum(nums, target):
    num_map = {}
    for i, num in enumerate(nums):
        if target - num in num_map:
            return [num_map[target - num], i]
        num_map[num] = i
    return []

Test your solution:

It’s important to test your solution to make sure it is correct. LeetCode provides test cases that you can use to verify that your solution is correct. You can also write some test cases of your own to make sure your solution is working as expected.

Variations

Here are a few variations of the Two Sum problem:

  1. Two Sum II - Input array is sorted: In this variation, the input array is already sorted in ascending order. This means that you can use a slightly different approach to solve the problem, such as using two pointers to iterate through the array from the beginning and the end.
  2. Two Sum III - Data structure design: In this variation, you are asked to design a data structure that supports adding and finding numbers that add up to a target in constant time. You can solve this problem by using a hash table to store the numbers and their frequencies.
  3. Two Sum IV - Input is a BST: In this variation, the input is a binary search tree (BST) rather than an array. You can solve this problem by using an in-order traversal of the BST to convert it into a sorted array, and then using a similar approach as the Two Sum II variation to find the two numbers that add up to the target.
  4. Two Sum Less Than K: In this variation, you are asked to find two numbers in the array that add up to a number that is less than a target number (K). You can solve this problem by sorting the array and using two pointers to iterate through the array from the beginning and the end, similar to the Two Sum II variation.

Grow Your Tech Career. Meet Expert coaches from top companies

Meet A MAANG Coach

Related:

comments powered by Disqus