1. Two Sum
Two Sum (LeetCode 1) 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.
- Blind 75 · #3 of 75 · Arrays & Hashing
- NeetCode 150 · #3 of 150 · Arrays & Hashing
- NeetCode 250 · #4 of 250 · Arrays & Hashing
How to solve Two Sum
Two Sum is a Hashing Frequency Map and Counting problem, part of Array/Matrix Manipulation Patterns. Master hash map frequency counting for array problems. Count occurrences, find duplicates, and solve majority element problems efficiently.
Work towards the solution in these steps:
- A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it's best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.
- So, if we fix one of the numbers, say <code>x</code>, we have to scan the entire array to find the next number <code>y</code> which is <code>value - x</code> where value is the input parameter. Can we change our array somehow so that this search becomes faster?
- The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?
The reference solution runs in O(n) time and O(n) space.
The Two Sum solution and editorial walks through the full approach with reference code.
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
Problems related to Two Sum
Other problems that use the same Hashing - Frequency Map / Counting and Array/Matrix Manipulation Patterns techniques:
- Find the Town Judge — Easy, same subpattern
- Group Anagrams — Medium, same subpattern
- Majority Element — Easy, same subpattern
- Majority Element II — Medium, same subpattern
- Subarray Sum Equals K — Medium, same subpattern
- Valid Anagram — Easy, same subpattern
Two Sum FAQ
What is the LeetCode number of Two Sum?
Two Sum is LeetCode problem 1, rated Easy.
What pattern is used to solve Two Sum?
Two Sum is a Hashing Frequency Map and Counting problem. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Hashing - Frequency Map / Counting subpattern.
What is the time complexity of Two Sum?
The reference solution runs in O(n) time and O(n) space.
Which companies ask Two Sum?
Two Sum has been reported in interviews at Amazon, Google, Apple, Adobe, Microsoft, Bloomberg, Facebook, Oracle, Uber, Expedia, Twitter, Nagarro and others.