LESSON 197 OF 348 · NESTED LOOPS & BRUTE FORCE

Two Sum in Rust

Practice O(n²)

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input will have at most one solution, and you may not use the same index twice.

In case no solution exists, return [-1, -1]

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9

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 5

Guided

Ctrl + Enter to check