The Two Sum problem is a fundamental coding challenge frequently encountered in technical interviews. It tests a developer's ability to manipulate arrays and utilize efficient data structures like hashmaps. In this post, we will solve the Two Sum problem in C#, explaining both a brute-force method and an optimized solution using a dictionary. By the end, you will be well-equipped to handle this type of problem efficiently in C#.

Problem Statement

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

Constraints:

  1. You may assume that each input will have exactly one solution.
  2. You cannot use the same element twice.

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]  // nums[0] + nums[1] = 2 + 7 = 9

Step-by-Step Solution

Step 1: Brute-Force Approach

The brute-force solution involves checking every possible pair of elements in the array to see if their sum equals the target. While easy to implement, it is inefficient for large datasets.

Approach:

  1. Iterate through each element in the array.
  2. For each element, iterate through the rest of the array to check if their sum equals the target.
  3. If a valid pair is found, return their indices.

C# Code (Brute Force):

public 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 };
                }
            }
        }
        throw new ArgumentException("No two sum solution");
    }
}

Explanation:

  • The outer loop iterates through each element of the array.
  • The inner loop checks if any subsequent element adds up to the target with the current element.
  • If a valid pair is found, their indices are returned.

Time Complexity:

  • Time Complexity: O(n^2) — The solution checks each element with every other element, resulting in a quadratic time complexity.

Example:

class Program {
    static void Main(string[] args) {
        Solution solution = new Solution();
        int[] nums = { 2, 7, 11, 15 };
        int target = 9;
        int[] result = solution.TwoSum(nums, target);
        Console.WriteLine($"Indices: {result[0]}, {result[1]}");  // Output: Indices: 0, 1
    }
}

Step 2: Optimized Approach Using a Dictionary

The brute-force approach works but is inefficient. We can improve this by using a dictionary (similar to a hashmap in other languages) to store elements we’ve seen as we iterate through the array, allowing for fast lookups and solving the problem in linear time.

Optimized Approach:

  1. Initialize an empty dictionary to store numbers and their indices.
  2. Iterate through the array.
  3. For each number, calculate the difference between the target and the current number.
  4. Check if the difference exists in the dictionary.
    • If it does, return the current index and the index from the dictionary.
    • If not, store the current number and its index in the dictionary for future lookups.

C# Code (Optimized Solution):

using System;
using System.Collections.Generic;

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> map = new Dictionary<int, int>();
        
        for (int i = 0; i < nums.Length; i++) {
            int complement = target - nums[i];
            if (map.ContainsKey(complement)) {
                return new int[] { map[complement], i };
            }
            map[nums[i]] = i;
        }
        
        throw new ArgumentException("No two sum solution");
    }
}

Explanation:

  • Dictionary<int, int> map: This dictionary stores numbers as keys and their indices as values.
  • For each number, calculate the complement (target - nums[i]).
  • If the complement is already in the dictionary, the indices are returned.
  • If not, store the current number and its index in the dictionary for future reference.

Time Complexity:

  • Time Complexity: O(n) — Each element is processed only once, and lookups in the dictionary take constant time.

Example:

class Program {
    static void Main(string[] args) {
        Solution solution = new Solution();
        int[] nums = { 2, 7, 11, 15 };
        int target = 9;
        int[] result = solution.TwoSum(nums, target);
        Console.WriteLine($"Indices: {result[0]}, {result[1]}");  // Output: Indices: 0, 1
    }
}

In this example, when the iteration reaches 7, it computes 9 - 7 = 2. Since 2 is already in the dictionary (with index 0), it returns [0, 1].

Edge Cases

While the problem guarantees exactly one solution, you should still account for various edge cases during implementation:

  1. Negative and Positive Numbers:
    The array may contain both negative and positive numbers. Ensure that the solution works for both.

    int[] nums = {-3, 4, 3, 90};
int target = 0;
int[] result = TwoSum(nums, target);
Console.WriteLine($"{result[0]}, {result[1]}");  // Output: 0, 2

  2. Duplicate Values:
    The array may contain duplicate values, and the solution should still return the correct indices.

    int[] nums = {3, 3};
int target = 6;
int[] result = TwoSum(nums, target);
Console.WriteLine($"{result[0]}, {result[1]}");  // Output: 0, 1

  3. Array with Only Two Elements:
    Since the problem guarantees at least two elements, the array can have exactly two elements, and the solution should still work.

    int[] nums = {1, 4};
int target = 5;
int[] result = TwoSum(nums, target);
Console.WriteLine($"{result[0]}, {result[1]}");  // Output: 0, 1

  4. Zeros in the Array:
    If the array contains zeros, the solution should correctly handle the target involving zero.

    int[] nums = {0, 4, 3, 0};
int target = 0;
int[] result = TwoSum(nums, target);
Console.WriteLine($"{result[0]}, {result[1]}");  // Output: 0, 3

  5. Large Inputs:
    If the array contains a large number of elements, the hash map approach ensures efficiency even with significant data size.

    int[] nums = new int[100000];
for (int i = 0; i < 100000; i++) nums[i] = i;
int target = 199999;
int[] result = TwoSum(nums, target);
Console.WriteLine($"{result[0]}, {result[1]}");  // Output: 99998, 99999

Conclusion

The Two Sum problem is a great exercise for learning how to optimize algorithms using data structures like dictionaries (hashmaps). By switching from a brute-force approach to a dictionary-based solution, we reduce the time complexity from O(n^2) to O(n), making the solution scalable even for larger datasets.

Mastering the Two Sum problem in C# prepares you for more complex algorithmic challenges and teaches you how to make efficient use of dictionaries to handle problems involving searches and lookups.