Start learning free

LESSON 295 OF 671 · BRUTE FORCE

Two Sum

Practice O(n2)

You get an array of integers nums and a number target.

Return the indices of two numbers that add up to target.

The two indices must be different. You can return them in either order.

If no pair adds up to target, return [-1, -1].

Example 1:

Input: nums = [5, 12, 3, 8], target = 15
Output: [1, 2]
Explanation: nums[1] + nums[2] = 12 + 3 = 15

Example 2:

Input: nums = [6, 1, 6], target = 12
Output: [0, 2]
Explanation: nums[0] + nums[2] = 6 + 6 = 12
The two 6s are at different indices.

Example 3:

Input: nums = [5, 1, 3], target = 10
Output: [-1, -1]
Explanation: No pair adds up to 10.
5 + 5 would use index 0 twice.

Constraints:

  • 2 to 1,000,000 numbers.
  • Each number fits in a 32-bit signed integer.
  • The target fits in a 32-bit signed integer too.
  • At most one pair adds up to the target.

Note:

For this lesson, your algorithm should run in O(n^2) time and use O(1) extra space.
(There exist faster solutions which we will discuss in future lessons)


Hints:

Let's come up with a brute force approach. Brute force tries each and every candidate to our solution. For this problem, the candidates are all the pairs of elements (nums[i], nums[j]). We should go through each pair of indices (i, j) such that 0 <= i < j < n. How can we achieve this?

Using two nested for loops! The first loop will try out each possible i between 0 and n - 2. The second loop will be written inside the first one and will try out each possible j between i + 1 and n - 1. 
for each i : 0 -> n - 2:
	for each j : i + 1 -> n - 1:
What should be written inside these loops?

Inside the loops we should check if the pair (nums[i], nums[j]) is a solution, e.g. if nums[i] + nums[j] == target. If so, we should return the pair of indices (i, j): 
for each i : 0 -> n - 2:
	for each j : i + 1 -> n - 1:
		if nums[i] + nums[j] == target:
			return [i, j]
What if there's no solution, when should we return [-1, -1]?

If the two loops terminate and we haven't returned anything, we can conclude there is no solution as we have tried all possible candidates and none was good. So, below the loops, we should return [-1, -1]: 
for each i : 0 -> n - 2:
	for each j : i + 1 -> n - 1:
		if nums[i] + nums[j] == target:
			return [i, j]
return [-1, -1]

STEP 1 OF 4
    Ctrl + Enter to check