Start learning free

LESSON 194 OF 348 · NESTED LOOPS & BRUTE FORCE

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

Practice O(n²) 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

Guided

Ctrl + Enter to check

TYPESCRIPT · NESTED LOOPS & BRUTE FORCE

Two Sum in TypeScript, explained

Problem overview

The method twoSum receives an array of numbers, nums, and a target. It must return the indices of two entries that add up to target, as an array [i, j]. There is at most one solution, and the same index can't be used twice. When no pair works, the method returns [-1, -1].

For nums = [2, 7, 11, 15] and target = 9, the values at indices 0 and 1 are 2 and 7, which add up to 9. The answer is [0, 1]. Note that the result holds positions in the array, not the values.

Approach: check every pair of indices

This lesson asks for O(n^2) time and O(1) extra space, which is the brute-force budget. The idea is to try each pair of positions, once, and stop at the first pair whose values add up to target. Faster solutions exist, such as remembering the values already seen so each number needs one lookup instead of a scan, but those come later. This one needs nothing but two loops.

To visit each pair once, the outer index i takes every position, and the inner index j takes only the positions after i. A pair (i, j) and the same pair as (j, i) are then not tested twice, and j can never equal i, so an element is never paired with itself.

Step by step

Loop over the first index. i starts at 0 and runs while i < nums.length. Every position can be the first element of the pair.
Loop over the second index. Inside it, j starts at i + 1 and runs while j < nums.length. Starting right after i avoids repeats and avoids using one index twice.
Test the pair. If nums[i] + nums[j] === target, return [i, j]. A return inside the loops ends the whole method, so the search stops at the first match.
Return [-1, -1] after the loops. This line is reached only if every pair was tried and none matched.

The solution in TypeScript

class Solution {
    twoSum(nums: number[], target: number): number[] {
        for (let i = 0; i < nums.length; i++) {
            for (let j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] === target) {
                    return [i, j];
                }
            }
        }
        return [-1, -1];
    }
}

Some details worth knowing:

The outer loop could stop one step earlier. When i is the last index, the inner loop has nothing to do. Running it anyway costs nothing noticeable, and the code stays simple.
The return type is number[]. The array literal [i, j] is built at the moment of the return, so each call gets a new array.
Use ===. It compares without converting types. The annotations promise that nums holds numbers, but they are erased when the code is compiled, so nothing checks that at run time. If a string such as "3" got into the array, + would join text instead of adding.
Out-of-range reads don't crash. Reading past the end of an array in TypeScript gives undefined. The loop bounds keep both indexes inside the array, so this doesn't come up here.

Complexity

Time: O(n^2). In the worst case, when no pair matches or the match is the last pair, the inner body runs for every pair of positions: (n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2 times. That is quadratic in n. When the answer comes early, the method returns early, but the worst case sets the bound.

Space: O(1) extra. Apart from the result array of two elements, only the indexes i and j are stored.

Edge cases and common mistakes

Empty array or one element. No pair exists, so the loops finish without a match and the method returns [-1, -1].
Using one index twice. For nums = [3, 4] and target = 6 the answer must be [-1, -1]. If j started at i, the method would pair the 3 with itself and return [0, 0].
Equal values. For nums = [3, 3] and target = 6 the answer is [0, 1]. Two entries with the same value are still two different indices.
Returning values instead of indices. For [2, 7, 11, 15] the method returns [0, 1], not [2, 7].
Forgetting the fallback. Without the final return [-1, -1], a miss ends the method without returning anything, so the caller receives undefined instead of an array, and code that reads result[0] then crashes.
Negative numbers. They need no special handling. For [-3, 4, 3, 90] and target = 0 the pair is [0, 2].

Testing

nums = [2, 7, 11, 15], target = 9 gives [0, 1].
nums = [3, 2, 4], target = 6 gives [1, 2].
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 TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free