Start learning free

LESSON 194 OF 348 · NESTED LOOPS & BRUTE FORCE

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

    KOTLIN · NESTED LOOPS & BRUTE FORCE

    Two Sum in Kotlin, explained

    Problem overview

    The function twoSum(nums: IntArray, target: Int): IntArray receives an array of integers and a target. It must return the indices of two numbers that add up to target, as an IntArray of two elements. If no such pair exists, it returns [-1, -1]. There is at most one solution, and the same index can't be used twice, although two equal values at different indices are fine.

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

    The statement allows O(n^2) time and O(1) extra space. That is the budget of a brute-force search over all pairs.

    Approach: check every pair of indices

    The answer is a pair of positions, so the candidates are all pairs of positions (i, j). Trying them all and testing nums[i] + nums[j] == target is guaranteed to find the solution if there is one.

    To avoid wasted work, take only pairs with i < j. The pair (j, i) has the same sum as (i, j), so testing it would repeat the same check. Requiring j to start at i + 1 also stops an element from being paired with itself, which the problem forbids.

    This is the simplest correct solution. Faster ones exist, such as remembering the numbers already seen in a hash map, but this lesson builds the nested-loop version first.

    Step by step

    1. Loop over every possible first index. Use for (i in nums.indices). The property indices is the range of valid positions, 0 until nums.size.
    2. Loop over the second index. Inside it, use for (j in i + 1 until nums.size). The range starts after i and stops before nums.size. For the last i the range is empty, so the inner body doesn't run.
    3. Test the pair and return. If nums[i] + nums[j] == target, return intArrayOf(i, j). Returning from inside the loops ends both of them, so the search stops at the first match. With at most one solution, it is the only match.
    4. Handle the no-solution case. After the loops, return intArrayOf(-1, -1). The line is reached only when every pair has been tried without success.

    Take nums = [3, 4] and target = 6. The loops try only (0, 1), whose sum is 7. Nothing matches, so the function returns [-1, -1]. It doesn't pair the 3 with itself.

    The solution in Kotlin

    class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        for (i in nums.indices) {
            for (j in i + 1 until nums.size) {
                if (nums[i] + nums[j] == target) {
                    return intArrayOf(i, j)
                }
            }
        }
        return intArrayOf(-1, -1)
    }
}

    The Kotlin details worth knowing:

    • IntArray. It is Kotlin's array of primitive int values, created with intArrayOf(...) and read with nums[i]. It differs from Array<Int>, which holds boxed objects, and from List<Int>. The function signature uses IntArray, so the result has to be one too.
    • Operator precedence in ranges. In i + 1 until nums.size, the arithmetic i + 1 is evaluated first, then until builds the range. No parentheses are needed.
    • Return from inside a loop. A return leaves the whole function, not only the loop it is in. That is why no break is needed.
    • Printing and comparing arrays. Printing an IntArray directly gives an object description such as [I@1b6d3586. Use contentToString() to see [0, 1]. And == on two arrays compares references, so two arrays with the same contents are not equal: contentEquals compares the elements.
    • Empty ranges are fine. If the start is greater than the last allowed value, the loop simply doesn't run, so no extra check for a short array is needed.
    • Int addition wraps. 2000000000 + 2000000000 gives -294967296, not 4000000000. With those two numbers and target = -294967296, the function returns [0, 1]. The lesson's inputs stay far from this limit. For arbitrary values, you could add them as Long.

    Complexity

    Time: O(n^2). For n numbers, the pairs with i < j number n(n - 1) / 2. In the worst case, when there is no solution or it sits at the end, all of them are tested, and each test takes constant time.

    Space: O(1). The function uses only the two loop variables and, at the end, one small result array whose size doesn't depend on n.

    Edge cases and common mistakes

    • Fewer than two numbers. An empty array or a single element has no pair. The loops find nothing and the function returns [-1, -1].
    • Equal values. [3, 3] with target 6 returns [0, 1]. Two different positions that hold the same number are allowed.
    • Using the same element twice. [3, 4] with target 6 returns [-1, -1]. Starting j at i would wrongly report [0, 0].
    • Returning values instead of indices. The answer for [2, 7, 11, 15] is [0, 1], not [2, 7].
    • Negative numbers. The comparison works without changes: [-3, 4, 3, 90] with target 0 returns [0, 2].
    • Forgetting the final return. A Kotlin function with a block body and a return type must return on every path. Without the last line the code doesn't compile.
    • Returning a List. The signature needs an IntArray, so listOf(i, j) is a type error.
    • Order of indices. The smaller index comes first. For [7, 2] and target 9 the result is [0, 1].

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