Start learning free

LESSON 217 OF 414 · BRUTE FORCE

Two Sum in Scala: 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 Array(-1, -1)

Example:

Input: nums = Array(2, 7, 11, 15), target = 9
Output: Array(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.


STEP 1 OF 4
    Ctrl + Enter to check

    SCALA · BRUTE FORCE

    Two Sum in Scala, explained

    Problem overview

    The method twoSum receives an Array[Int] named nums and an Int named target. It returns an array with the indices of two numbers that add up to target, or Array(-1, -1) if there is no such pair. The input has at most one solution, and the same index can't be used twice, although two equal values at different indices are fine.

    For nums = Array(2, 7, 11, 15) and target = 9, the values at indices 0 and 1 are 2 and 7, which sum to 9. The answer is Array(0, 1). The statement asks for O(n^2) time and O(1) space.

    Approach: check every pair of indices

    The simplest idea is to try every pair. Pick a first index i, then pick a second index j and test whether nums(i) + nums(j) equals target. The first match is the answer.

    The second index only needs to look to the right of i. A pair of positions has a left member and a right member, and the pair is tested when the outer loop reaches the left one. Looking left would repeat earlier work. Starting j at i + 1 also guarantees that an element is never paired with itself.

    There are about n * (n - 1) / 2 pairs, hence O(n^2) time, and the method needs only a few variables, hence O(1) space. Faster ways exist, based on a hash map or on sorting, and other lessons on the same problem cover them. This one is about the plain nested loop.

    Step by step

    1. Outer loop. Use for (i <- nums.indices). nums.indices is the range of valid positions, 0 up to nums.length - 1. Every element can be the first of the pair.
    2. Inner loop. Use for (j <- i + 1 until nums.size). The word until excludes the upper end, so j stops at the last valid index. nums.size and nums.length give the same number for an array.
    3. Test the pair. If nums(i) + nums(j) == target, return Array(i, j). Scala indexes arrays with parentheses.
    4. Report failure. If both loops finish with no match, return Array(-1, -1). This line runs only after every pair has been tried.

    The solution in Scala

    class Solution {
    def twoSum(nums: Array[Int], target: Int): Array[Int] = {
        for (i <- nums.indices) {
            for (j <- i + 1 until nums.size) {
                if (nums(i) + nums(j) == target) {
                    return Array(i, j)
                }
            }
        }
        return Array(-1, -1)
    }
}

    Scala details:

    • A for loop is a method call. A loop without yield is turned into a call of foreach with the body as a function. A return inside the body leaves the enclosing method, twoSum, and Scala 3.5 prints a warning that such non-local returns are no longer supported. The code still runs and returns the pair. The clean alternative is scala.util.boundary with boundary.break, or a loop with a flag.
    • Ranges. i + 1 until nums.size is an empty range when i is the last index, so the inner loop simply doesn't run.
    • Arrays. nums(i) is a method call, nums.apply(i). Reading an index outside the array throws ArrayIndexOutOfBoundsException; the ranges here never leave the array.
    • Int arithmetic wraps. Int is 32 bits. With nums = Array(2000000000, 2000000000) the sum is 4000000000, which wraps to -294967296. So for target = -294967296 the method returns Array(0, 1), though the true sum is a different number. For ordinary inputs this doesn't matter, but converting with .toLong would avoid it.
    • The result is a new array. Printing an Array directly shows an object reference, not its contents; use mkString(", ") to see the values.

    Complexity

    Time: O(n^2). The inner loop makes n - 1 passes for i = 0, n - 2 for i = 1, and so on, a total of n * (n - 1) / 2 comparisons in the worst case, when no pair matches.

    Space: O(1). The loops use a few integers. The returned two-element array has a fixed size.

    Edge cases and common mistakes

    • Empty or one-element input. The inner loop never runs, and the method returns Array(-1, -1).
    • Using one index twice. Array(3, 4) with target = 6 returns Array(-1, -1). Starting j at i would pair the 3 with itself and answer Array(0, 0).
    • Equal values. Array(3, 3) with target = 6 returns Array(0, 1).
    • Order of the indices. The answer comes out as Array(i, j) with i < j. For Array(7, 2) and target = 9 it is Array(0, 1).
    • Values, not indices. The method returns positions, not the numbers that were added.
    • No match. Array(1, 2, 3) with target = 100 returns Array(-1, -1).

    Testing

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