EasyNo. 0001

Two Sum — LeetCode 1 Python Solution

Pattern
Hash Map
Topics
Array, Hash Table
Reading time
2 min

The 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.

Example

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

Python solution

PythonSolution
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for i, x in enumerate(nums):
            if (y := target - x) in d:
                return [d[y], i]
            d[x] = i

Complexity

Time
O(n)
Space · auxiliary
O(n)

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1. Two Sum is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0653Two Sum IV - Input is a BSTEasy
0167Two Sum II - Input Array Is SortedMedium
0036Valid SudokuMedium
0037Sudoku SolverHard
0041First Missing PositiveHard
0049Group AnagramsMedium

Frequently asked questions

How hard is LeetCode 1. Two Sum?

LeetCode 1. Two Sum is rated Easy on LeetCode.

What is the time complexity of LeetCode 1. Two Sum?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1. Two Sum?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1. Two Sum cover?

LeetCode 1. Two Sum is tagged Array and Hash Table on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.