Two Sum

Two Sum is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Hashing - Frequency Map / Counting subpattern.

Problem statement

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

Constraints:

- 2 <= nums.length <= 104

- -109 <= nums[i] <= 109

- -109 <= target <= 109

- Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Topics and companies

Topics: Array, Hash Table.

Reported in interviews at Amazon, Google, Apple, Adobe, Microsoft, Bloomberg, Facebook, Oracle, Uber, Expedia, Twitter, Nagarro and others.

How to practise Two Sum on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.

Open Two Sum in the code editor, or read the Two Sum editorial for a worked solution with its approach and complexity analysis.

Where Two Sum sits in the DSA pattern sheet

• Array/Matrix Manipulation Patterns pattern guide
• Hashing - Frequency Map / Counting subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Two Sum

Other problems that use the same Hashing - Frequency Map / Counting and Array/Matrix Manipulation Patterns techniques:

• Group Anagrams — Medium, same subpattern
• Valid Anagram — Easy, same subpattern
• Add Binary — Easy, same pattern
• Add to Array-Form of Integer — Easy, same pattern
• Diagonal Traverse — Medium, same pattern
• Find All Duplicates in an Array — Medium, same pattern