Start learning free

LESSON 194 OF 338 · NESTED LOOPS & BRUTE FORCE

Two Sum in Go: 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:

Your algorithm should run in O(n^2) time and use O(1) space.


Go starter code:

func twoSum(nums []int, target int) []int {
}
STEP 1 OF 5
    Ctrl + Enter to check

    GO · NESTED LOOPS & BRUTE FORCE

    Two Sum in Go, explained

    Problem overview

    The function twoSum(nums []int, target int) []int receives a slice of integers and a target. It must return the indices of two numbers that add up to target. At most one solution exists, the same index may not be used twice, and when nothing matches the function returns []int{-1, -1}.

    For nums = [2, 7, 11, 15] and target = 9, the values at indices 0 and 1 are 2 and 7, and 2 + 7 = 9, so the answer is [0, 1].

    The requested complexity is O(n^2) time and O(1) space, which describes checking every pair of positions.

    Approach: check every pair of indices

    The brute force idea is direct. Pick a first index i, pick a second index j, and test whether nums[i] + nums[j] == target. If it does, return the two indices. If every pair fails, return [-1, -1].

    To avoid wasted work, j only looks at positions after i. A pair of positions (i, j) and the pair (j, i) have the same sum, and the loop reaches the pair once, with the smaller index first. Starting at i + 1 also guarantees that j never equals i, which respects the rule against using one index twice. Two equal values at different indices are still allowed, so [3, 3] with target 6 is a valid input.

    There are about n^2 / 2 pairs, so the time is O(n^2). Nothing is stored apart from two loop counters, so the extra space is O(1). Faster solutions trade memory for time, but this lesson practises the brute force first.

    Step by step

    1. Loop over the first index. i starts at 0 and runs while i < len(nums). len returns the number of elements in a slice.
    2. Loop over the second index inside the first loop, with j starting at i + 1 and running to the end of the slice. This makes each pair tried once.
    3. Compare the sum. An if checks whether nums[i] + nums[j] equals target. Go needs no parentheses around the condition, but the braces are required.
    4. Return the indices as []int{i, j} the moment a match is found. A slice literal is the type followed by the elements in braces. Returning early also means the first matching pair in loop order wins.
    5. Return []int{-1, -1} after both loops. This line is reached only when every pair has been tried without success. A function with a result type must end with a return, so the compiler would reject the function without it.

    The solution in Go

    func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] + nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return []int{-1, -1}
}

    Go details:

    • Slices. []int is a slice, a view of an underlying array. The function only reads it, so no copy is needed.
    • Returning inside the loops. return leaves the whole function at once, not just the inner loop, so no flag or label is required.
    • Integer overflow. int is 64 bits here. A sum of two very large values wraps silently instead of raising an error, which only matters for inputs near 9.2 × 10^18.
    • A nil slice. len of a nil slice is 0, so the loops simply do not run.

    Complexity

    Time: O(n^2). For each i, the inner loop runs n - i - 1 times. The total is (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparisons in the worst case, which is O(n^2).

    Space: O(1). Only i and j are used besides the returned two-element slice.

    Edge cases and common mistakes

    • Using one index twice. Starting j at i would let [3, 4] with target 6 return [0, 0]. The correct answer is [-1, -1].
    • Equal values. [3, 3] with target 6 returns [0, 1].
    • Empty or one-element input. Both fall through the loops and return [-1, -1].
    • Returning values instead of indices. The answer is []int{i, j}, not nums[i] and nums[j].
    • Several valid pairs. The problem promises at most one, but if the input had more, this code returns the first pair found in loop order. For [3, 2, 4] with target 6 it returns [1, 2].
    • Negative numbers. They need no special handling; the sum check works unchanged.

    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 = [], target = 1 gives [-1, -1].
    • nums = [1, 5, 5], target = 10 gives [1, 2].
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free