LeetCode #1: Two Sum

https://leetcode.com/problems/two-sum/

To solve this problem in Python 3, you can follow these steps:

1. Create a function called “two_sum” that takes an array of integers and a target value as its arguments.
2. Create an empty dictionary called “complements”. This dictionary will be used to store the complements of each number in the array. A complement is the value that, when added to a given number, results in the target value.
3. Iterate through the array using a for loop. For each number in the array, calculate its complement by subtracting it from the target value. If the complement is already in the dictionary, return the indices of the two numbers.
4. If the complement is not in the dictionary, add the current number and its index to the dictionary.
5. If no two numbers in the array add up to the target value, return an empty list.

Here’s the complete solution:

class Solution:
    def twoSum(self, nums, target):
        complements = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in complements:
                return [complements[complement], i]
            complements[nums[i]] = i
        return []

Space Complexity

We use a dictionary to store the complements of each number in the array. The space complexity of this approach is O(n), where n is the number of elements in the array.

The reason for this is that in the worst case scenario, we may need to store all n elements of the array in the dictionary. Each element takes up a constant amount of space, so the total space required is proportional to the size of the array.

Runtime Complexity

We use a dictionary to store the complements of each number in the array. The runtime complexity of this approach is O(n), where n is the number of elements in the array.

The reason for this is that we need to iterate through the array once to check each element. For each element, we can calculate its complement by subtracting it from the target value. Then, we can check if the complement is already in the dictionary. If it is, we can return the indices of the two numbers. If it’s not, we can add the current number and its index to the dictionary.

The time complexity of adding an element to a dictionary is O(1) on average, so the total time complexity of this approach is O(n). This means that as the size of the array increases, the time required to solve the problem will increase linearly.