Start learning free

LESSON 220 OF 414 · BRUTE FORCE

Two Sum in Rust: O(n^2) Brute Force with Nested Loops

Practice O(n2) Read the full explanation

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
    Ctrl + Enter to check

    RUST · BRUTE FORCE

    Two Sum in Rust, explained

    Problem overview

    The function two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> receives a vector of integers and a target. It must return the indices of two numbers that add up to the target, or [-1, -1] if there are none. At most one solution exists, and the same index can't be used twice, although two equal values at different indices are fine.

    For nums = [2, 7, 11, 15] and target = 9, the values at indices 0 and 1 are 2 and 7, which add up to 9. The answer is [0, 1].

    This lesson asks for O(n^2) time and O(1) extra space, which points to the simplest idea: check every pair.

    Approach: try every pair of indices

    Brute force examines each candidate answer. A candidate here is a pair of positions (i, j). To avoid testing the same pair twice, and to avoid pairing an element with itself, only pairs with i < j are used. The outer loop picks i from the first position onward, and the inner loop picks j from i + 1 to the end.

    The first pair whose values add up to target is the answer, and the function returns at once. If both loops finish without a match, no pair works, and the function returns [-1, -1].

    On [2, 7, 11, 15] with target 9, i = 0 pairs 2 with 7 first, and 2 + 7 = 9 matches immediately. On [1, 2, 3] with target 100, all three pairs fail and the answer is [-1, -1].

    Step by step

    1. Store the length. let n = nums.len(); gives the number of elements. len() returns a usize, the type Rust uses for indexing, so n can be used as a loop bound without conversion.
    2. Outer loop. for i in 0..n visits every possible first position. The range excludes n, so it covers exactly the valid indices.
    3. Inner loop. for j in i + 1..n visits every later position. Starting at i + 1 means each pair is tried once and an element is never paired with itself.
    4. Check the pair. if nums[i] + nums[j] == target needs no parentheses around the condition, but the braces are required.
    5. Return the indices. Inside the if, build the answer with vec![i as i32, j as i32]. The indices are usize but the function returns Vec<i32>, and Rust never converts between integer types implicitly, so as i32 does it explicitly. An explicit return is needed because the exit is from inside the loops.
    6. Fall back. If nothing matched, the loops end and the last expression, vec![-1, -1], becomes the result.

    The solution in Rust

    impl Solution {
    fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let n = nums.len();
        for i in 0..n {
            for j in i + 1..n {
                if nums[i] + nums[j] == target {
                    return vec![i as i32, j as i32];
                }
            }
        }
        vec![-1, -1]
    }
}

    Rust details worth a closer look:

    • Range precedence. i + 1..n is read as (i + 1)..n, because the arithmetic binds tighter than the range operator.
    • Empty ranges are fine. When i + 1 reaches n, the inner range is empty and the loop body is skipped. No special case is needed for the last element.
    • Indexing. nums[i] needs a usize. Using an i32 variable as an index is a compile error, which is why the loops use usize ranges.
    • Ownership. The function takes the vector by value, but it only reads from it, so nothing is moved or cloned inside the loops.
    • No semicolon on the last line. vec![-1, -1] is the value of the function. Adding a semicolon would make the function return nothing and fail to compile.

    Complexity

    Time: O(n^2). In the worst case, when no pair matches or the match comes last, the inner loop runs n - 1 times for i = 0, n - 2 times for i = 1, and so on. That is n * (n - 1) / 2 checks, which is proportional to n^2. A match found early ends the search sooner, but the worst case is what is quoted.

    Space: O(1). The function stores only n, i and j besides the input and the small result vector. Faster approaches exist that trade extra memory or sorting for speed; this lesson stays with the simple version.

    Edge cases and common mistakes

    • Empty or one-element input. With no elements the outer loop does not run, and with one element the inner range is empty. Both return [-1, -1] without any out-of-bounds access.
    • Equal values. [3, 3] with target 6 returns [0, 1]. Two equal numbers at different indices are allowed.
    • Pairing an element with itself. [3, 4] with target 6 returns [-1, -1]. Starting j at i would answer [0, 0].
    • Negative numbers and zero. Nothing special is needed. [-3, 4, 3, 90] with target 0 returns [0, 2].
    • Order of the result. The smaller index comes first, because i < j. For [7, 2] and target 9, the answer is [0, 1].
    • Overflow. The sum nums[i] + nums[j] is an i32 addition. In a debug build, overflowing it panics. In an optimized build it wraps silently, so with nums = [2000000000, 2000000000] and target = -294967296 the function returns [0, 1], because 4,000,000,000 wraps to -294,967,296. Widening to i64 before adding avoids this, though ordinary inputs never reach it.
    • Forgetting the casts. vec![i, j] has type Vec<usize>, which doesn't match the return type.

    Testing

    • nums = [2, 7, 11, 15], target = 9 gives [0, 1].
    • nums = [3, 3], target = 6 gives [0, 1].
    • nums = [3, 4], target = 6 gives [-1, -1].
    • nums = [7, 2], target = 9 gives [0, 1].
    • nums = [], target = 6 gives [-1, -1].
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free