Two Sum | LeetCode in C# | Brute force approach

You might want to read the Hash Table solution. It’s better.

Intuition

When I first encountered the Two Sum problem, my initial thought was to check each possible pair of numbers in the array. If a pair sums to the target value, then that would be our solution.

This brute force method should work, but intuitively, I thought there might be more efficient ways.

However, starting with the simplest idea often helps to understand the problem better and refine the approach.

Approach

To implement the brute force solution, I used a nested loop technique where I iterated through the array with one pointer, and for each element, iterated again through the remaining elements with a second pointer.

For every pair of numbers evaluated by these pointers, I check if they add up to the target.

If they do, I return their indices.

While this approach will solve the problem, it isn’t optimized for larger datasets, but it’s a straightforward implementation to quickly get a functional solution.

Complexity

• Time complexity: The time complexity is \(O(n^2)\) because, for every element, we iterate through the remaining elements to find a pair.
• Space complexity: The space complexity is \(O(1)\). We do not use any additional data structures; our output array result is constant in size.

Code

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        var result = new int[2];
        
        for(var i=0; i<nums.Length-1; i++) {
            for(var j=i+1; j<nums.Length; j++) {
                var a = nums[i];
                var b = nums[j];
                var c = a + b;
                if(c == target)
                    return new int[]{i,j};
            }
        }
        
        return result;
    }
}

Video

Conclusion

This solution solves the Two Sum problem as defined by LeetCode, effectively identifying pairs of numbers in the array that add up to the target sum.

While the approach is straightforward, it serves as a foundation for further optimization, such as using a hash table or dictionary to improve efficiency to \(O(n)\) time complexity.

References

• Two Sum - LeetCode