🔍 Problem Description
Given an integer array nums and an integer target, return the indices of the two numbers whose sum equals target. You may assume exactly one solution exists and you can't use the same element twice.
public int[] TwoSum(int[] nums, int target)
Examples:
nums = [2,7,11,15], target = 9 // → [0,1]
nums = [3,2,4], target = 6 // → [1,2]
nums = [3,3], target = 6 // → [0,1]
#### 🔁 1. Brute‑Force (Nested Loops)
public int[] TwoSumBrute(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 };
}
}
return Array.Empty<int>();
}
- 🕒 Time: O(n²) – checks every possible pair
- 💾 Space: O(1) – constant space usage
- ✅ Best for tiny arrays or as a conceptual starting point
🗂️ 2. Two‑Pass Hash Map
public int[] TwoSumTwoPass(int[] nums, int target) {
var map = new Dictionary<int, int>(nums.Length);
for (int i = 0; i < nums.Length; i++)
map[nums[i]] = i;
for (int i = 0; i < nums.Length; i++) {
int comp = target - nums[i];
if (map.TryGetValue(comp, out int j) && j != i)
return new int[]{ i, j };
}
return Array.Empty<int>();
}
- 🕒 Time: O(n) – two passes
- 💾 Space: O(n) – storing elements in map
🔥 3. One‑Pass Hash Map (Optimal)
public int[] TwoSumOnePass(int[] nums, int target) {
var map = new Dictionary<int, int>(nums.Length);
for (int i = 0; i < nums.Length; i++) {
int comp = target - nums[i];
if (map.TryGetValue(comp, out int j))
return new int[]{ j, i };
map[nums[i]] = i;
}
return Array.Empty<int>();
}
- 🕒 Time: O(n) – single traversal
- 💾 Space: O(n) – map tracks seen values
🧪 4. Benchmark Insights
- “The brute force solution outperforms the Dictionary solution … for small or skewed inputs”
- “Arrays will be faster no matter the size. … dense buffers pretty often perform best”
- Reddit benchmarking shows brute force beating hash-map for small inputs, but hash-map scales much better on larger, randomized datasets
- stackoverflow.com
📊 Quick Comparison Table
Method Time Space Ideal Use Case
Brute Force O(n²) O(1) Tiny arrays, simple logic
Two‑Pass Hash Map O(n) O(n) Good clarity, two-stage logic
One‑Pass Hash Map O(n) O(n) Interview-friendly, single-scan optimal
🚀 5. Visual Explanation
🧠 6. Challenges & Extensions
- ✅ Return all unique pairs — avoid duplicates using sets
- 🎯 Adapt to streaming input — handle data in chunks
- 📉 Space-optimized variant: sort + two-pointer, then map back indices
- ⚡ Benchmark with BenchmarkDotNet — validate real-world performance
✅ Conclusion
- 🟢 Brute Force: easiest but becomes impractical as n grows
- 🟢 One-Pass Hash Map: balanced, efficient, ideal for interviews
- 🎯 Always consider data size, distribution, and cache behavior when choosing your approach
📝 Call to Action
- Implement all three methods in C# code.
- Benchmark them using BenchmarkDotNet across diverse datasets.
- Share surprising results—especially browser-based micro-benchmark behaviors 👇
- Need help setting up benchmarks, visual diagrams, or tackling streaming data? Just ask!