Two Sum (Leetcode #1)
Question:
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
.
Constraints:
Each input would have exactly one solution.
The same element cannot be used twice.
Examples:
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, 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]
Answer:
Brute Force Approach:
One way to solve this problem is by using a brute force approach. We can find the target and the index of the pair by trying every combination of numbers in nums
. However, this approach results in a time complexity of O(N^2) because we have to go through every combination and a space complexity of O(1).
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
Improvement: Using Hashmap
Time Complexity of using Hashmap:
Insertion (put):
Average Case: O(1)
Worst Case: O(n)
Lookup (get):
Average Case: O(1)
Worst Case: O(n)
Algorithm:
Initialize an empty dictionary
seen
to store numbers and their indices.Iterate through the list
nums
using indicesi
.Check if
target - nums[i]
exists inseen
.If found, return the indices of the two numbers that add up to
target
.If not found, store
nums[i]
inseen
with its index.
If no such pair is found, it means there's no solution,
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
seen = {}
for i in range(len(nums)):
if target - nums[i] in seen:
return [seen[target - nums[i]], i]
else:
seen[nums[i]] = i
Time Complexity
O(N) because we go through the list ounce
Space Complexity
O(N) because we create a hashmap of size N
Subscribe to my newsletter
Read articles from Nawat Sunthornyanakit directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
Nawat Sunthornyanakit
Nawat Sunthornyanakit
I am a beginner coder who wants to keep track of my coding progress. I will post my LeetCode solutions here. Please feel free to give me advice or suggestions on my code. Also, in the future, I will be posing my data science-related project here as well