FastPrep3Sum
Problems/3Sum

3Sum

Amazon logoAmazon● MediumINTERNPHONE SCREEN
QuestionExamples

Problem statement

Source note: Amazon asked this classic in the second round of a summer intern technical phone screen: find every distinct triple of numbers in an array that adds up to zero. The candidate named the problem only by its well-known title.

The report gave no limits or output order. Practice choices here: the well-known version of the task with its usual limits (3 to 3000 numbers from -10^5 to 10^5), and, so that answers can be compared exactly, each triplet in non-decreasing order with the triplets in increasing lexicographic order.

The judged task matches the report at about 95%.

Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] such that i, j and k are three different indices and nums[i] + nums[j] + nums[k] == 0.

The problem statement continues
Pro

Examples

Example 1

nums = [-1,0,1,2,-1,-4]return = [[-1,-1,2],[-1,0,1]]
  • -1 + 0 + 1 = 0 and -1 + (-1) + 2 = 0.
  • The triplet [-1, 0, 1] can be formed with either -1, but it is listed once. Each triplet is written in non-decreasing order, and [-1, -1, 2] comes before [-1, 0, 1].
02 · Example 2
FastPrep Pro
Reported in 1 Amazon interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

  • Full problem statement and constraints
  • 2 more worked examples, explained
  • Guided hints and editorial
  • Run your code on real test cases
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week
See Amazon hiring insights
CodePython 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq
from collections import defaultdict
 
class Solution:
def solve(self, values, queries):
# Build the adjacency structure
n = len(values)
graph = defaultdict(list)
for u, v in queries:
graph[u].append(v)
 
best = [float("inf")] * n
heap = [(0, 0)]
while heap:
cost, node = heapq.heappop(heap)
if cost > best[node]:
continue
Run and Submit unlock with Pro
FastPrep Pro
Reported in 1 Amazon interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

  • Full problem statement and constraints
  • 2 more worked examples, explained
  • Guided hints and editorial
  • Run your code on real test cases
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week