Start learning free

LESSON 229 OF 347 · TWO POINTERS

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

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

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


STEP 1 OF 10
    Ctrl + Enter to check

    C# · TWO POINTERS

    Two Sum in C#, explained

    Problem overview

    TwoSum receives an int[] nums and an int target. It returns the indices of two numbers that add up to target, or {-1, -1} if no pair exists. There is at most one solution, 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 add up to 9, so the result is {0, 1}. The statement also sets a budget of O(n log n) time and O(n) extra space.

    Approach

    The brute force checks every pair of indices, which is O(n²). A hash-based approach reaches O(n). This lesson uses a third idea: sort, then squeeze from both ends.

    Once the values are in ascending order, put one pointer, first, on the smallest value and another, last, on the largest. Look at their sum:

    • If it equals target, you found the pair.
    • If it is too small, the current smallest value fails even with the largest remaining partner, so no pairing can work for it. Move first right to a bigger value.
    • If it is too large, the current largest value fails even with the smallest remaining partner. Move last left to a smaller value.

    Each step discards one candidate for good, so the scan takes at most n steps. The sort is the expensive part, at O(n log n).

    Sorting has one catch. It moves the values, but the answer needs original indices. So before sorting, every value is paired with its index. The pair {value, index} travels together through the sort, and the indices are read from the pairs at the end.

    Step by step

    1. Allocate the pairs. sortedNums is a jagged int[][] with one row per element. new int[nums.Length][] creates the outer array only, so each row starts as null.
    2. Fill each row with new int[]{nums[i], i}: index 0 holds the value and index 1 the original position.
    3. Sort by value. An int[] has no natural order, so Array.Sort takes a comparison lambda, (first, second) => first[0] - second[0]. A negative result puts first before second.
    4. Declare both pointers in one statement: first at 0 and last at sortedNums.Length - 1.
    5. Loop while first < last. When they meet, every pair has been ruled out.
    6. Add the two values, sortedNums[first][0] and sortedNums[last][0], into sum.
    7. On a match, return the original indices sortedNums[first][1] and sortedNums[last][1].
    8. Too small: ++first. Too large: --last.
    9. Fall back to {-1, -1} after the loop.

    The solution in C#

    class Solution {
    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]);

        int first = 0, last = sortedNums.Length - 1;
        while (first < last) {
            int sum = sortedNums[first][0] + sortedNums[last][0];
            if (sum == target) {
                return new int[]{sortedNums[first][1], sortedNums[last][1]};
            } else if (sum < target) {
                ++first;
            } else {
                --last;
            }
        }
        return new int[]{-1, -1};
    }
}

    C# details:

    • Jagged array. int[][] is an array whose elements are themselves arrays, and the inner arrays can be created one at a time. That fits here because every row is a two-element pair.
    • The lambda is a Comparison<int[]>. Array.Sort(array, comparison) sorts in place and calls the lambda to order two elements. It returns negative, zero or positive, like CompareTo.
    • Two things called first. The lambda's parameter first and the local variable first declared a few lines later are unrelated. The code compiles with the current compiler, but different names would be clearer.
    • int first = 0, last = ... declares two variables of the same type in one statement.
    • The sort is not stable. Equal values may end up in either order, which doesn't matter here, since any pair of equal values that works is a valid answer.

    The subtraction comparator can overflow

    first[0] - second[0] is a classic shortcut, and it is only safe while the difference fits in an int. C# int arithmetic wraps around silently by default. For example, 2,000,000,000 minus -2,000,000,000 gives -294,967,296 instead of 4,000,000,000, so the sort treats the larger value as smaller. Running this code on {2000000000, -2000000000, 1, 3} with target 4 leaves the values in the order 2000000000, -2000000000, 1, 3, which is not sorted, and it returns {-1, -1} although indices 2 and 3 are a valid pair. Comparing with first[0].CompareTo(second[0]) has no such problem. The same wrap-around applies to sum for huge values. For modest inputs, the lesson's version is fine.

    Complexity

    Time: O(n log n). Building the pairs is O(n), the sort is O(n log n), and the two-pointer scan moves one pointer per iteration, so it takes at most n - 1 iterations.

    Space: O(n). There are n small arrays, one per element, plus the outer array. The sort works on the array in place.

    Edge cases and common mistakes

    • Fewer than two elements. With an empty array, last is -1, so the loop doesn't run. With one element, the pointers are equal. Both return {-1, -1}.
    • Equal values. {3, 3} with target 6 returns {0, 1}. The two 3s are different positions, so this is allowed.
    • The same element twice. {3, 4} with target 6 returns {-1, -1}. The pointers never share an index, since the loop stops when they meet.
    • Returning sorted positions. first and last are positions in the sorted array. The answer comes from the second element of each pair.
    • Order of the result. The index of the smaller value comes first. For {7, 2} and target 9 the code returns {1, 0}.
    • Sorting only the values. If you sort a plain copy of nums, the indices are lost.

    Testing

    • {2, 7, 11, 15}, target 9 gives {0, 1}.
    • {3, 9, -2, 5}, target 3 gives {2, 3}.
    • {3, 4}, target 6 gives {-1, -1}.
    • {}, target 9 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