Two Sum - Algorithm

Two Sum

📝 Problem Statement

Given an array nums and an integer target, return indices of the two numbers such that they add up to target. Assume exactly one solution, no duplicate elements.

🎯 Core Concepts & Classification

• Problem Type: Pair Finding / Complement Search. The core is finding a complement (target - x) for each number x.
• General Strategy: Demonstrates efficient Searching Algorithms using appropriate Data Structures.

💡 Solution Strategies & Rationale

1. Brute Force (Nested Loops)

   • Idea: Check every unique pair (nums[i], nums[j]).
   • Complexity: O(N^2) Time, O(1) Space.
   • Rationale: Establishes a baseline; simple. Useful for very small N.

2. Hash Map (Optimal for this problem)

   • Idea: Iterate once. For each num, calculate its complement (target - num). Check if complement is already in the map. If not, add (num, index) to map.
   • Complexity: O(N) Time (average), O(N) Space.
   • Rationale: Achieves O(1) average time for lookups/insertions. Best when original indices are required and fast existence checks are key. Highlights [[Time-Space Trade-off]].

3. Sorting Algorithms + Two Pointers

   • Idea: Sort array (or (value, original_index) pairs). Use two pointers (left, right) to converge on the target sum.
   • Complexity: O(N log N) Time (due to sort), O(1) or O(N) Space.
   • Rationale: Powerful for variations (e.g., 3Sum, 4Sum, finding all pairs) or when original indices aren’t a strict requirement. Sorting creates order that enables linear scans.

🔑 Key Takeaways & General Principles

• Identify the Complement: Many problems are reduced to finding a specific dependent value (Y) for a given value (X).
• Hash Map for Speed: When you need to quickly check for the existence of an element or its complement (often O(1) average time), a Hash Map is your go-to data structure. This is a common Time-Space Trade-off.