Problem 🤔

Given an array of integers nums and an integer target, return 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.

You can return the answer in any order.

Example 1

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Output: 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]

Real World Applications 🌎

This is the most popular problem on leetcode so it must be really useful right? Not really, but it is nice in the sense that it requires us to use a dict as well as an array so we get a bit more variety here!

The Finer Details 🔎

Let’s start with a simple approach first. For every number x in the list we can check if it’s “target” compliment, y exists in the list. Let’s define y as follows:

y = target - x

Easy! But what’s the complexity here? Let’s look at this line.

This is a search operation in a list! We’d have to iterate through the whole list to confirm this, so this is O(n).

Since this is happening in a for loop the complexity is O(n^2) :(

Optimal Solution 💡

There are tradeoffs in this problem! I think giving up on space here for speed is a good one, so will aim for that. After seeing a number we know that we need x = target - number, so we can go ahead and save that.

Complexity Analysis 🧮

Time complexity

O(n)

One set of constant operations for every node.

Space complexity

O(n)

We allocated a dictionary

Takeaways 🎉🥳

Use of a dictionary. This one here is pretty easy but you can easily make coding mistakes if you’re not very familiar with dicitonary syntax. Be careful!

Resources 📚 💻

Leetcode