ā† Back

āž• Two Sum (Unsorted Array)

Use HashMap for O(n) solution!

šŸ‘¶Explain Like I'm 5

šŸ§© Real-Life Example: Finding Your Lost Sock's Match

Imagine you have a pile of random socks (unsorted!). You want to find two socks whose sizes add up to exactly 10.

āŒ Slow Way (Brute Force - O(nĀ²)):

Pick sock #1, compare with ALL other socks. Pick sock #2, compare with ALL other socks. Takes FOREVER!

If you have 100 socks, you make 10,000 comparisons! šŸ˜°

āœ… Smart Way (HashMap - O(n)):

  1. Pick up sock with size 3. You need a sock of size 7 (10 - 3 = 7).
  2. Check your "memory book" (HashMap): "Have I seen size 7?"
  3. If YES ā†’ Found it! šŸŽ‰
  4. If NO ā†’ Write down "I saw size 3 at position 0" and move to next sock.

You only touch each sock ONCE! Way faster! āš”

šŸ’” Key Insight: complement = target - current
We don't search for pairs. We search for the ONE number that completes the current number!

āš” Why HashMap is Magic: Looking up a value in HashMap takes O(1) time - instant! Like having a super-fast index in a book!

šŸ” Code Debugger

ā†’ EXECUTING
1public int[] twoSum(int[] arr, int target) {
2HashMap<Integer, Integer> map = new HashMap<>();
3...
4for (int i = 0; i < arr.length; i++) {
5int complement = target - arr[i];
6...
7if (map.containsKey(complement)) {
8return new int[]{map.get(complement), i}; // Found!
9}
10...
11map.put(arr[i], i); // Store value ā†’ index
12}
13return new int[]{-1, -1}; // Not found
14}

šŸ“Š Variables:

i (current index):0
arr[i]:3
complement:N/A
target:9

šŸŽÆ Array & HashMap

Array:

3
7
2
11
5
15
[0]
[1]
[2]
[3]
[4]
[5]

HashMap (seen numbers):

Empty - building as we go...

Click "Start" to begin visualization

1.0x (2.5s per step)
šŸŒ 0.3x (Very Slow)1.0x (Normal)šŸš€ 2.0x (Fast)

ā˜• Complete Java Solution

HashMap Pattern
public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];

        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }

        map.put(nums[i], i);  // Store value ā†’ index
    }

    return new int[]{-1, -1};  // Not found
}

// Time Complexity: O(n) - single pass
// Space Complexity: O(n) - HashMap storage

āš” Why HashMap? Time Complexity Battle!

āŒ Brute Force (Two Nested Loops):

Time: O(nĀ²) šŸŒ

For n=10,000 elements, that's 100 million comparisons!

for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { if (arr[i] + arr[j] == target) return new int[]{i, j}; } }

āœ… HashMap Solution (One Pass):

Time: O(n) āš”

For n=10,000 elements, only 10,000 operations!

for (int i = 0; i < n; i++) { if (map.containsKey(complement)) return new int[]{map.get(...), i}; map.put(nums[i], i); }

šŸ’” HashMap lookup/insert is O(1) - constant time!

That's why HashMap is 10,000x faster for large arrays! šŸš€