Two Sum - LeetCode's Solution In C# With Both O(n) And O(n^2) Approach

Introduction

Let's look at the multiple solutions for the following problem,

Problem: Assume you have 2 inputs, the first one is an array and the second is the target: which is the sum of 2 elements in the array. All you have to do is to find those 2 numbers and return their indices.

Sounds easy but given different test cases it could be challenging.

input 1: { 2, 7, 11, 15 }, target: 9 - answer is [0,1] since 2+7 = 9

input 2: { 3, 2, 4 }, target: 6 - answer is [1,2] since 2+4 = 6

input 3: { 0, 3, 2, 0 }, target: 0 - answer is [0,3] since 0+0 = 0

Few points before we jump into coding.

Always have validations at the beginning of the method.
Look for the boundary value test cases.

let's get cracking.

Solution 1: The Brute Force Approach

Straight away, what we can do is to add 2 elements of the array and compare the result with the target. In order to perform the addition, we need to add one element of the array with every other element in the array to cover all the possibilities. With this brute force approach as we are iterating through loop twice we will have Time Complexity of O(n^2) and Space complexity would be O(1).

/// <summary>
/// Brute force: Time Complexity: O(n^2), Space complexity: O(1) 
/// </summary>
/// <param name="nums"></param>
/// <param name="target"></param>
/// <returns>integer array of indices</returns>
private static int[] TwoSumBruteForce(int[] nums, int target) {
    //Declarations
    int arrayLength = nums.Length;
    //Validations
    if (nums == null || arrayLength < 2) {
        return Array.Empty < int > ();
    }
    //Logic
    for (int i = 0; i < arrayLength; i++) {
        for (int j = i + 1; j < arrayLength; j++) {
            if (nums[i] + nums[j] == target) return new int[] {
                i,
                j
            };
        }
    }
    return Array.Empty < int > ();
}

Listing 1

Solution 2: The Optimized Approach

Rather than comparing each element of an array let's just use maths here. Which will avoid iterating an array twice.
Let's see what kind of information is provided. We have 2 elements of array, Ok good, and we also have a target. Now we can build our logic around this information and can have an optimized solution.

We need a suitable data structure that can hold key-value pairs. In C# We have a Dictionary.

But why Key-Value pairs? So the key can hold the element of the array and the value will hold the index of that element (which is expected to be returned).

let's take first test case: input 1: { 2, 7, 11, 15 }, target: 9 - answer is [0,1] since 2+7 = 9

If I start iterating through a loop, I get to the first element which is 2.
Next, Let's deduct these 2 from the target which is 9: will get 7.
let's add 2 to the dictionary with its index, Now dictionary will have [2, 0]
Going for the second iteration. Next value is 7.
Again did the deduction: 9-7: will get 2. We will see if the dictionary has an entry of 2. Yes it has. Well these are the 2 indices that makes the sum, so just return the value from the dictionary (index of 2) and the current value of i (index of 7). Because 2 + 7 = 9.

With this optimized approach we will have Time Complexity: O(n) since we are iterating the loop once and Space complexity would be O(n).

/// <summary>
/// Using a Dictionary: Time Complexity: O(n), Space complexity: O(n) 
/// </summary>
/// <param name="nums"></param>
/// <param name="target"></param>
/// <returns>integer array of indices</returns>
private static int[] TwoSumOptimized(int[] nums, int target) {
    //Declarations
    int arrayLength = nums.Length;
    Dictionary < int, int > resultDictionary = new();
    //Validations
    if (nums == null || arrayLength < 2) {
        return Array.Empty < int > ();
    }
    //Logic
    for (int i = 0; i < arrayLength; i++) {
        int firstNumber = nums[i];
        int secondNumber = target - firstNumber;
        if (resultDictionary.TryGetValue(secondNumber, out int index)) {
            return new [] {
                index,
                i
            };
        }
        //resultDictionary.Add(firstNumber, i);
        resultDictionary[firstNumber] = i;
    }
    return Array.Empty < int > ();;
}

Listing 2

Notice how I have commented dictionary.Add(), the reason being dictionaries can't add entries with similar keys so you come across with a test case such as this: { 1, 1, 2, 1, 1, 2 } and target: 4.

See image 1 throwing an error when I tried to run the program with the above test case.

Image 1

So instead what we are doing is, We are going to only keep one entry in the dictionary. Hence using brackets to add the value instead of Add function. For test case in solution 2, dictionary will have this entry [2, 0]

Code snippet in listing 3 is overall code with the main method.

namespace Solution
{
    public class Program
    {
        static public void Main()
        {
            // Brute force: Time Complexity: O(n^2), Space complexity: O(1) 
            // ({ 2, 7, 11, 15 }, 9);
            // ({ 3, 2, 4 }, 6);
            // ({ 3, 3 }, 6);
            int[] resultOfBruteForce = TwoSumBruteForce(new int[] { 0, 4, 3, 0 }, 0);
            Console.WriteLine("------------------ BruteForce Solution ------------------");
            Console.WriteLine("--------- Time Complexity: O(n^2), Space complexity: O(1)  ---------");
            Console.WriteLine(string.Join(" ", resultOfBruteForce));

            Console.WriteLine();

            // Using a Dictionary: Time Complexity: O(n), Space complexity: O(n) 
            // ({ 2, 7, 11, 15 }, 9);
            // ({ 3, 2, 4 }, 6);
            // ({ 3, 3 }, 6);
            int[] resultOfOptimized = TwoSumOptimized(new int[] { 1, 1, 2, 1, 1, 2 }, 4);
            Console.WriteLine("------------------ Optimized Solution ------------------");
            Console.WriteLine("--------- Time Complexity: O(n), Space complexity: O(n)   ---------");
            Console.WriteLine(string.Join(" ", resultOfOptimized));
        }

        /// <summary>
        /// Using a Dictionary: Time Complexity: O(n), Space complexity: O(n) 
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns>integer array of indices</returns>
        private static int[] TwoSumOptimized(int[] nums, int target)
        {
            //Declarations
            int arrayLength = nums.Length;
            Dictionary<int, int> resultDictionary = new();

            //Validations
            if (nums == null || arrayLength < 2)
            {
                return Array.Empty<int>();
            }

            //Logic
            for (int i = 0; i < arrayLength; i++)
            {
                int firstNumber = nums[i];
                int secondNumber = target - firstNumber;
                if (resultDictionary.TryGetValue(secondNumber, out int index))
                {
                    return new[] { index, i };
                }

                //resultDictionary.Add(firstNumber, i);
                resultDictionary[firstNumber] = i;
            }

            return Array.Empty<int>(); ;
        }


        /// <summary>
        /// Brute force: Time Complexity: O(n^2), Space complexity: O(1) 
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns>integer array of indices</returns>
        private static int[] TwoSumBruteForce(int[] nums, int target)
        {
            //Declarations
            int arrayLength = nums.Length;

            //Validations
            if (nums == null || arrayLength < 2)
            {
                return Array.Empty<int>();
            }

            //Logic
            for (int i = 0; i < arrayLength; i++)
            {
                for (int j = i + 1; j < arrayLength; j++)
                {
                    if (nums[i] + nums[j] == target)
                        return new int[] { i, j };
                }
            }
            return Array.Empty<int>();
        }
    }
}

Listing 3

Image 2 is an output of listing 3.

Image 2

And that's how you do it.

Summary

We have covered 2 possible solutions for one of the most common interview questions. Always root for optimizing solutions, it proves your logical ability.

Note: Attached source code is running on .NET 6.

Link to the problem: https://leetcode.com/problems/two-sum/