Start learning free

LESSON 218 OF 415 · BRUTE FORCE

Two Sum in Swift: 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 4
    Ctrl + Enter to check

    SWIFT · BRUTE FORCE

    Two Sum in Swift, explained

    Problem overview

    The method twoSum(_ nums: [Int], _ target: Int) receives an array of integers and a target. It must return the indices of two numbers that add up to target, as an array [i, j]. The input has at most one solution, and the same index cannot be used twice. When no pair works, the method returns [-1, -1].

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

    Two equal values are fine as long as they sit at different indices: [3, 3] with target 6 gives [0, 1]. The answer is indices, not values.

    Approach: check every pair of indices

    The statement allows O(n^2) time and O(1) extra space, which fits the most direct idea: try every pair of positions and stop at the first pair whose values sum to the target.

    To avoid wasted work, each pair should be tried once. The pair at positions 2 and 5 is the same pair as the one at 5 and 2. So the outer index i takes every position, and the inner index j starts right after it. That gives all pairs with i < j. It also makes using one index twice impossible, since j is never equal to i.

    Faster solutions exist. A hash table of the values seen so far finds the partner of each number in constant time and brings the total to O(n). This lesson stays with brute force, which is the baseline to compare those against.

    Step by step

    1. Loop over the first index. for i in 0..<nums.count uses a half-open range, which stops before nums.count, so i takes every valid index.
    2. Loop over the second index. Inside it, for j in (i + 1)..<nums.count starts after i. The parentheses make the range's start clear.
    3. Test the pair. If nums[i] + nums[j] == target, return [i, j]. Returning inside the loops ends the search at the first match.
    4. Return the failure value. After both loops, write return [-1, -1]. This line is reached only when every pair has been tried without a match.

    The solution in Swift

    class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        for i in 0..<nums.count {
            for j in (i + 1)..<nums.count {
                if nums[i] + nums[j] == target {
                    return [i, j]
                }
            }
        }
        return [-1, -1]
    }
}

    The Swift details worth knowing:

    • Empty ranges are legal, backwards ranges are not. When i is the last index, the inner range is nums.count..<nums.count, which is empty, so the inner loop simply does nothing. That is why the outer loop can run to the end. A range whose start is above its end, such as 4..<3, crashes the program at run time. Here the start never exceeds nums.count, so that cannot happen.
    • Empty input. For an empty array, 0..<0 gives no iterations and the method returns [-1, -1].
    • Array literals. [i, j] is inferred as [Int] from the return type.
    • Overflow traps. Int is 64 bits. Adding two values whose sum doesn't fit, such as Int.max + 1, stops the program with a run-time error instead of wrapping around. Ordinary test values never get near that.

    Complexity

    Time: O(n^2). The inner loop runs n - 1 times for i = 0, n - 2 times for i = 1, and so on, giving n(n - 1)/2 pair checks in the worst case, which is when no pair matches or the match is at the end. That is proportional to n^2.

    Space: O(1). The method uses only the two loop variables. The returned two-element array has a fixed size.

    Edge cases and common mistakes

    • Using one element twice. [3, 4] with target 6 must return [-1, -1]. An inner loop starting at i would pair the 3 with itself and return [0, 0].
    • Fewer than two elements. [] and [5] with any target both return [-1, -1].
    • No solution. [1, 2, 3] with target 100 returns [-1, -1], and only after all three pairs have been checked.
    • Index order. The smaller index comes first. For [7, 2] and target 9 the answer is [0, 1], never [1, 0].
    • More than one match. The problem promises at most one pair. If there were several, the method would return the first pair found in loop order. For [1, 5, 5, 1] with target 6 it returns [0, 1].
    • Returning values. The method returns positions. For [2, 7, 11, 15] the answer is [0, 1], not [2, 7].
    • Negative numbers. The comparison is on sums, so negatives work without special handling: [3, 9, -2, 5] with target 3 gives [2, 3].

    Testing

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