LESSON 250 OF 347 · BINARY SEARCH

Two Sum in C#: O(n log n) with Sorting and Binary Search

Practice O(n log 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:

Your algorithm should run in O(n log n) time and use O(n) extra space.

STEP 1 OF 14

Guided

Ctrl + Enter to check

C# · BINARY SEARCH

Two Sum in C#, explained

Problem overview

The method TwoSum receives an int[] nums and an int target. It returns the indices of two different positions whose values add up to target, or {-1, -1} when no such pair exists. There is at most one valid pair, and the same index can't be used twice, although two equal values at different indices are fine.

For 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}.

The lesson asks for O(n log n) time and O(n) extra space. That rules out checking every pair, which costs O(n²), and points toward sorting.

Approach: sort the pairs, then search for each complement

If a value x belongs to the answer, its partner must be exactly target - x, the complement. Finding one specific value in a sorted array takes O(log n) with binary search, so one search per element gives O(n log n) in total, and the sort itself costs the same.

Sorting causes one problem: it moves values away from their original positions, and the answer needs the original indices. The fix is to sort small {value, originalIndex} pairs instead of bare values. Each value carries its index wherever the sort puts it.

The search for the partner of position i only looks at positions i + 1 and beyond. Every pair of positions has a left member, so it gets found when the loop reaches that member. Starting at i + 1 also stops an element from pairing with itself.

Take nums = {3, 9, -2, 5} with target = 3. The sorted pairs are {-2, 2}, {3, 0}, {5, 3} and {9, 1}. At position 0 the value is -2, so the search looks for 5 among positions 1 to 3 and finds it at position 2. The method returns the original indices stored in those two pairs: {2, 3}. Running the solution below on this input does return 2, 3.

Other approaches exist. A Dictionary<int, int> of values seen so far solves Two Sum in O(n) time, and a two-pointer scan over the sorted pairs works too. This lesson practises binary search, so it searches for each complement directly.

Step by step

Declare sortedNums as an int[][] with nums.Length rows. This is a jagged array: an array of arrays. Each row is created in the next step.
Fill each row with new int[]{nums[i], i}, value first. Putting the value first means that ordering by the first element orders the pairs by value.
Sort with a comparison. An int[] has no natural order, so Array.Sort receives a lambda that compares two rows by their first element. A negative result puts the first row before the second.
Loop over the sorted positions with i. Each pair is tried as the left member of the answer.
Search for the complement with BinarySearch(sortedNums, i + 1, sortedNums.Length - 1, target - sortedNums[i][0]) and store the result in j. The search range starts to the right of i.
On a hit, return the original indices, sortedNums[i][1] and sortedNums[j][1], not i and j.
After the loop, return {-1, -1}, because the loop only finishes without returning when no pair adds up to target.
Write the helper's signature. BinarySearch takes the pairs, the inclusive range first to last and the value to find.
Loop while the range is non-empty: while (first <= last). The range is empty once first passes last.
Compute the midpoint as first + (last - first) / 2. It equals the average but never adds the two bounds, so it can't overflow.
Return middle when its value matches.
Go right with first = middle + 1 when the middle value is too small, since everything to its left is smaller still.
Otherwise go left with last = middle - 1.
Return -1 after the loop, which tells the caller that no partner exists in the searched range.

The solution in C#

class Solution {
    public int BinarySearch(int[][] sortedNums, int first, int last, int value) {
        while (first <= last) {
            int middle = first + (last - first) / 2;
            if (sortedNums[middle][0] == value) {
                return middle;
            } else if (sortedNums[middle][0] < value) {
                first = middle + 1;
            } else {
                last = middle - 1;
            }
        }
        return -1;
    }

    public int[] TwoSum(int[] nums, int target) {
        int[][] sortedNums = new int[nums.Length][];
        for (int i = 0; i < nums.Length; i++) {
            sortedNums[i] = new int[]{nums[i], i};
        }
        Array.Sort(sortedNums, (first, second) => first[0] - second[0]);

        for (int i = 0; i < sortedNums.Length; i++) {
            int j = BinarySearch(sortedNums, i + 1, sortedNums.Length - 1, target - sortedNums[i][0]);
            if (j != -1) {
                return new int[]{sortedNums[i][1], sortedNums[j][1]};
            }
        }
        return new int[]{-1, -1};
    }
}

C# details worth knowing

int[][] versus int[,]. int[][] is an array of separate arrays, and new int[nums.Length][] creates only the outer array, with every row null until you assign it. That is why the fill loop is needed. int[,] is a different type, a single rectangular block.
The sort comparison. Array.Sort(array, comparison) accepts a lambda that returns a negative number, zero or a positive number. The lambda's parameter names first and second belong only to the lambda.
Subtraction as a comparison can overflow. first[0] - second[0] is fine for small values, but for values of very different sign and large size the subtraction wraps around silently, because int arithmetic is unchecked by default. For example, int.MaxValue - (-2) evaluates to -2147483647 in unchecked code, so the sign is wrong. An overflow-safe comparison is first[0].CompareTo(second[0]). The same concern applies to target - sortedNums[i][0].
Returning an array. new int[]{-1, -1} creates a fresh two-element array each time.

Complexity

Building the pairs takes O(n) time and sorting takes O(n log n). The loop then runs at most n times, and each iteration does one O(log n) binary search, so the loop costs O(n log n). The total is O(n log n).

The n pairs, each an array of two ints, are the extra space, so it is O(n). The binary search is iterative and needs only a few variables.

Edge cases and common mistakes

Returning sorted positions. After sorting, positions mean nothing to the caller. Return the second element of each pair, not i and j.
Searching from 0. If the search starts at 0 or i, a number can pair with itself. For nums = {3, 2, 4} and target = 6, the single 3 would answer with a pair of the same index. Starting at i + 1 avoids this, and the method returns {1, 2} here.
Duplicates. With {3, 3} and target = 6, the two 3s sit at different indices, so {0, 1} is valid, and that is what the method returns.
No solution or empty input. {1, 2} with target = 10 gives {-1, -1}, and so does an empty array, since the loop body never runs.
Binary search on unsorted data. Skipping the sort step gives wrong answers without any error.
Lowercase names. Code ported from Java often uses binarySearch and nums.length. In C# the method is declared as BinarySearch and the array's size is nums.Length.

Testing

nums	target	result
`{2, 7, 11, 15}`	9	`{0, 1}`
`{3, 9, -2, 5}`	3	`{2, 3}`
`{3, 3}`	6	`{0, 1}`
`{3, 2, 4}`	6	`{1, 2}`
`{1, 2}`	10	`{-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