Start learning free

LESSON 213 OF 410 · BRUTE FORCE

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

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

    PYTHON · BRUTE FORCE

    Two Sum in Python, explained

    Problem overview

    The method twoSum receives a list of integers, nums, and an integer target. It must find two numbers in the list that add up to target and return their indices, not the numbers themselves. There is at most one solution, and the same index cannot be used twice. If no pair works, the method returns (-1, -1).

    With nums = [2, 7, 11, 15] and target = 9, the values at indices 0 and 1 are 2 and 7, and 2 + 7 = 9. The answer is the pair of indices 0 and 1. In this lesson's solution the pair comes back as a tuple, so it prints as (0, 1).

    The lesson sets a budget of O(n^2) time and O(1) extra space. That is the budget of the brute force solution: try every pair.

    Approach: check every pair of indices

    Brute force means trying every candidate answer. Here a candidate is a pair of positions (i, j), and testing it is a single comparison, nums[i] + nums[j] == target.

    The loops should not generate the same pair twice or pair a position with itself. If i runs over every index and j only over the indices after i, each unordered pair is visited exactly once. For four numbers the visited pairs are (0, 1), (0, 2), (0, 3), (1, 2), (1, 3) and (2, 3), six in total. For n numbers that is n * (n - 1) / 2 pairs, which is where O(n^2) comes from.

    The first pair that works is returned immediately. Since the problem has at most one solution, there is no reason to keep searching. If both loops finish without a return, every pair has been tried and none matched.

    Step by step

    1. Loop over the first index. for i in range(len(nums)) lets every position be the first element of the pair.
    2. Loop over the second index. for j in range(i + 1, len(nums)) starts right after i, so a pair is not tried twice and an element is not paired with itself.
    3. Test the pair. If nums[i] + nums[j] == target, return (i, j). Returning from inside the loops ends the whole search at once.
    4. Return the failure value after the loops. return (-1, -1) runs only when the outer loop has finished without finding anything.

    The solution in Python

    class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return (i, j)
        return (-1, -1)

    Some details a Python learner should know:

    • The result is a tuple. The annotation says List[int], but Python does not enforce annotations, and the method returns tuples. A tuple unpacks like a list: i, j = Solution().twoSum([2, 7, 11, 15], 9) gives i = 0 and j = 1. A tuple and a list are not equal, though: (0, 1) == [0, 1] is False, so compare like with like.
    • range(i + 1, len(nums)) is empty when i is the last index, so the inner loop simply does nothing there.
    • No overflow. Python integers grow as needed, so adding two large numbers is always safe.

    Complexity

    The nested loops test up to n * (n - 1) / 2 pairs, each in constant time, so the time is O(n^2). The method stores only the two loop indices, so the extra space is O(1).

    Brute force is fine for a few thousand numbers and slow beyond that. The faster version uses a dictionary. For each number x, the partner it needs is target - x. If that value was already seen, the answer is its stored index and the current one. If not, remember x and its index:

    def two_sum_fast(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return [-1, -1]

    This runs in O(n) time with O(n) extra space, a trade of memory for speed. The lesson stays with the nested loops, and later lessons cover the faster versions.

    Edge cases and common mistakes

    • Using the same element twice. For [3] with target = 6 the answer must be (-1, -1), because 3 + 3 would need the same index twice. Starting j at i would wrongly return (0, 0).
    • Equal values at different indices are fine. For [3, 3] and target = 6 the answer is (0, 1).
    • No solution. [1, 2, 3] with target = 7 returns (-1, -1). An empty list does too.
    • Negative numbers. Nothing special is needed: [-1, -2, -3, -4, -5] with target = -8 returns (2, 4), since -3 + -5 = -8. Do not skip values just because they are negative or larger than the target.
    • Returning the values instead of the indices. The answer for the example is (0, 1), not (2, 7).
    • Returning inside the wrong place. Putting return (-1, -1) inside the outer loop would give up after the first element. It belongs after both loops.

    Testing

    • [2, 7, 11, 15] with target 9 returns (0, 1).
    • [3, 2, 4] with target 6 returns (1, 2), not (0, 0).
    • [3, 3] with target 6 returns (0, 1).
    • [5] with target 10 returns (-1, -1).
    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free