LeetCode with C# - Two Sum

Welcome to my series on LeetCode and solving problems with C#. The goal of this series is to help those who are trying to solve LeetCode problems without directly giving them a copy paste answer. To help you direct your brain on how to think about the given problem.

With that let’s get into it. Today’s problem is Two Sum.

If you just want the solution and skip all the fun, just scroll down to the bottom.

Problem

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

What does this mean?

We are given an array of integers called nums with another single integer called target. We need to return another array that holds the 2 indexes from nums that can be added together to get the target value.

For example.

Nums = [1,2,3,4]
Target = 6

Looking at this with the human brain it should stand out that 4 + 2 makes 6. Therefore our end result would need to return [1,3].

Break down problem into thoughts with words

So we know we need to return 2 numbers. We will need something to hold that value. We can make a new array to hold those values that has a length of 2. I will call this solution, because it will hold our answers to this problem.

int[] solution = new int[2];

We will have to preform some loop to go through the values. That is straightforward enough, for loop.

for (int currentIndex = 0; currentIndex < nums.Length; currentIndex++){
   //do some cool stuff inside this.
}

So if we start to think about the problem we have to get 2 numbers that add to equal our target. We know that for sure there is one answer (as given by the requirements), and that two numbers will always add to be our target.

We have an A + B = C situation going on here. With this formula the following is also true:
C - B = A

If we can sub out our code requirements for these variables we start to see something taking shape.

Target — Nums[CurrentIndex] = Potential Number In The Array.

Great! We have something to start with.

Taking the target value and subtracting the value of the current index in the array (nums), we have a potential number to go look up in the array.

Getting a number to search for

Inside our loop we want to set up a number to search for. Let’s do that like so:

int searchTarget = target - nums[currentIndex];

Then we need to check if this search number exists in the array and ensure that we aren’t looking at the same number twice. We can do that using Contains and Index Of.

Please note: I don’t suggest using C#’s Array.Find method as that returns 0 if the lookup is not found and then you’d have to handle that scenario.

//Contains Look Up
nums.Contains(searchTarget)
//Index of Look Up
nums.IndexOf(nums, searchTarget)
//Combination of them
if (nums.Contains(searchTarget) && Array.IndexOf(nums, searchTarget) != currentIndex)

If these look up conditions are true then we can insert into our solution array and return the solution!

solution[0] = currentIndex;
solution[1] = Array.IndexOf(nums, searchTarget);
return solution;

Fancy! Let’s string it all together for a solve!!!

Iterative Solution (Using Array Index Look Ups)

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
         int[] solution = new int[2];
        
        for (int currentIndex = 0; currentIndex < nums.Length; currentIndex++ ) {
            
            int searchTarget = target - nums[currentIndex];
            
            if (nums.Contains(searchTarget) && Array.IndexOf(nums, searchTarget) != currentIndex) {
                
                solution[0] = currentIndex;
                solution[1] = Array.IndexOf(nums, searchTarget);
                
                return solution;
            }            
        }  
        
        return solution;        
    }
}

This solution has a time complexity of O(n)² given that the for loop is present along with the nums.Contains search.
There are other single time complexity solutions for this problem but I consider them less readable (especially for beginners) so I have chosen to not display them here.

If you want to view those, solve this problem on Leetcode.com https://leetcode.com/problems/two-sum/solution/