LeetCode Problem-1 (Two Sum)

Two sum

The “Two Sum” problem is a classic coding challenge that often appears in technical interviews. The task is to find two numbers in an array that add up to a given target. In this blog post, we’ll explore a simple and efficient solution using Python.

Problem Statement:

Given an array of integers nums and an integer target, the goal is to return the indices of the two numbers such that they add up to the target. It’s important to note that each input has exactly one solution, and the same element cannot be used twice.

Example Scenarios: Let’s walk through a few examples to understand the problem better.

Example 1:

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

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Solution Approach:

class Solution:
    def twoSum(self, nums, target):
        lastmap = {}
        
        for i, n in enumerate(nums):
            diff = target - n
            if diff in lastmap:
                return [lastmap[diff], i]
            lastmap[n] = i

Explanation:

• We iterate through the array using enumerate to keep track of the current index and value.
• For each element, we calculate the difference (diff) between the target and the current number.
• We check if the difference is present in the lastmap (a dictionary where keys are array elements, and values are their indices).
• If the difference is found, we return the indices of the two numbers that add up to the target.
• If not, we update the lastmap with the current element and its index.

Alternative Solution:

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

Analysis:

1. Time Complexity:
   • The original solution has a time complexity of O(n) where n is the length of the input array. It iterates through the array once, making it highly efficient.
   • The alternative solution, however, has a time complexity of O(n^2) due to nested loops. It checks every possible pair in the array, resulting in a less optimized solution.
2. Space Complexity:
   • Both solutions have a space complexity of O(n) since they use a dictionary (lastmap in the original, none in the alternative) to store elements and their indices.