Start learning free

LESSON 193 OF 347 · NESTED LOOPS & BRUTE FORCE

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

    C# · NESTED LOOPS & BRUTE FORCE

    Two Sum in C#, explained

    Problem overview

    The method TwoSum(int[] nums, int target) receives an array of integers and a target. It must return the indices of two numbers that add up to target, as an int[] of length 2. There is at most one valid pair, and the same index can't be used twice. If no pair exists, 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 sum to 9, so the answer is {0, 1}.

    Approach: try every pair

    This lesson sets a budget of O(n^2) time and O(1) extra space. That fits the simplest idea: check every pair of positions and stop at the first one that adds up to the target. Faster solutions exist and appear in later lessons, but this brute force is the baseline they improve on.

    The pair (i, j) is the same pair as (j, i), so there is no need to check both. Fix the order by letting j always start after i. Then each pair of positions is visited once, and i is never paired with itself, which the problem forbids.

    For {2, 7, 11, 15} and target 9, the loops visit (0, 1) first: 2 + 7 is 9, so the method returns immediately with {0, 1}. For the same array and target 100, it visits all six pairs, finds nothing, and returns {-1, -1}.

    Step by step

    1. Loop over the first position. An int i runs from 0 while i < nums.Length. Every element can be the first member of the pair.
    2. Loop over the second position. Inside it, an int j runs from i + 1 while j < nums.Length. Starting right after i tries each pair once.
    3. Test the pair. If nums[i] + nums[j] == target, return a new int[] holding i and j. Returning from inside the loops ends the search at once.
    4. Report failure. After both loops, return {-1, -1}. This line is reached only when every pair has been tried without a match.

    The solution in C#

    class Solution {
    public int[] TwoSum(int[] nums, int target) {
        for (int i = 0; i < nums.Length; ++i) {
            for (int j = i + 1; j < nums.Length; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }
}

    The C# details worth knowing:

    • Creating the result. new int[]{i, j} allocates a new array of length 2 and fills it. C# arrays have a fixed length, so the result is built in one step like this.
    • Length, not length or Count. Arrays expose their size as the property Length (no parentheses). Count belongs to List<T>.
    • ++i and i++. In a loop header they behave the same, because the value of the expression is not used. Both add 1 after each pass.
    • Silent overflow. nums[i] + nums[j] is an int addition. If the true sum is beyond the int range, C# wraps around without an error: if big holds int.MaxValue, big + 1 evaluates to -2147483648. For very large inputs this could produce a false match.
    • Printing the result. Console.WriteLine(result) on an array prints the type name, not the contents. To look at it, use string.Join(", ", result).

    Complexity

    Time: O(n^2). The outer loop runs n times, and for position 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). Apart from the two-element result array, the method keeps only i and j. The result has a fixed size and doesn't grow with n.

    Edge cases and common mistakes

    • Fewer than two elements. An empty array never enters the outer loop, and a one-element array leaves the inner loop empty. Both return {-1, -1}.
    • Using one index twice. {3, 4} with target 6 must return {-1, -1}. Starting j at i would pair the 3 with itself and wrongly answer {0, 0}.
    • Equal values. {3, 3} with target 6 returns {0, 1}. Two equal values at different positions are a valid pair.
    • Negative numbers and zero. Nothing special is needed: {-3, 4, 3, 90} with target 0 returns {0, 2}.
    • Returning values instead of indices. The method returns positions, {i, j}, not nums[i] and nums[j].
    • Forgetting the final return. Without the last line the method doesn't compile, because C# requires every path through a non-void method to return a value.
    • Returning null or an empty array for "no pair". The problem asks for {-1, -1}.

    Testing

    • {2, 7, 11, 15}, target 9 gives {0, 1}.
    • {3, 3}, target 6 gives {0, 1}.
    • {3, 4}, target 6 gives {-1, -1}.
    • {7, 2}, target 9 gives {0, 1}: the smaller index always comes first.
    • An empty array with any target gives {-1, -1}.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free