Two Sum

LeetCode

Commonly asked at:Amazon Google Apple Adobe Microsoft

Two Sum

Given an array of integers nums and an integer target, return the 0-indexed positions of the two numbers that add up to target. Each input has exactly one solution.

Example

Input: nums = 2 7 11 15, target = 9 Output: 0 1

Approach

Single pass with a hash map of value → index. For each number, check whether target - number was already seen — if so, you have your pair, in O(n) instead of O(n²).

Walkthrough

python

1for i, num in enumerate(nums):
2    complement = target - num
3    if complement in seen:
4        return seen[complement], i
5    seen[num] = i

Step 1 / 2

target - 2 = 7. 7 isn't in the map yet, so just record that 2 lives at index 0.

Input format

Line 1: the array, space-separated Line 2: target

Not solved yet

Ctrl+Enter

Editor

nums = list(map(int, input().split()))
target = int(input())
# TODO: single pass with a value->index map
seen = {}

nums = list(map(int, input().split()))
target = int(input())
# TODO: single pass with a value->index map
seen = {}

Input (stdin)

Output

Run your code to see output here.

Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.

Editor

nums = list(map(int, input().split()))
target = int(input())
# TODO: single pass with a value->index map
seen = {}

nums = list(map(int, input().split()))
target = int(input())
# TODO: single pass with a value->index map
seen = {}

Input (stdin)

Output

Run your code to see output here.

Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.

Community Discussions

No discussions yet

Be the first to start a conversation.