LeetCode 1: Two Sum | Brute Force, Two-Pointer, Hash Map Approaches | C++, Java, Python

🔍 *Two Sum Problem Explained*
Welcome to the first coding walkthrough! 🚀 In this video, we’ll solve the Two Sum Problem, a common coding interview question, using three different approaches:

1️⃣ *Brute Force Approach*
2️⃣ *Two-Pointer Approach*
3️⃣ *Hash Map Approach*

🧠 *Brute Force Approach*
*Intuition*
To solve the problem, we need to find two numbers, *x* and *y*, in the array such that their sum equals *target*. In the brute force approach, we consider all possible pairs of elements in the array and check if their sum matches the target. This ensures that we find the solution, as we are trying every possible combination.

*Approach*
- Use two loops: the outer loop selects the first number (*x*), and the inner loop iterates over the remaining numbers (*y*) to find a match where *x + y = target*.

*Complexity*
- Time Complexity: *O(n^2)*
- Space Complexity: O(1)

---

🧠 *Two-Pointer Approach*
*Intuition*
In the brute force approach, we try every pair of numbers in the array. However, if the array is sorted, we can reduce unnecessary comparisons. By starting with two pointers—one at the beginning (smallest number) and one at the end (largest number)—we can strategically move them based on whether their sum is greater or less than the target. This allows us to skip many invalid pairs.

*Approach*
- First, store the original indices of the numbers in a HashMap so that we can map back to the original positions after sorting.
- Next, sort the array to ensure the numbers are in ascending order.
- Initialize two pointers: one at the beginning of the sorted array (i) and the other at the end (j).
- Check the sum of the two numbers: if it equals the target, map back to the original indices and return the result; if less than the target, move the left pointer (i) to the right; if greater, move the right pointer (j) to the left.

*Complexity*
- Time Complexity: *O(n log n)*
- Space Complexity: *O(n)*

---

🧠 *Hash Map Approach*
*Intuition*
In the brute force approach, for every number *x*, we search for another number *y* that satisfies *x + y = target*. Instead of repeatedly searching for *y* in the array, we can store the values we are looking for in a hash map. This way, we can instantly check if *y* exists in the array as we iterate through it.

*Approach*
- Initialize an empty hash map to store the complements (i.e., *target - x*) and their corresponding indices.
- Iterate through the array, calculate the complement (target - current number) for each element, check if the complement exists in the hash map (return indices if found), and if not, add the complement with its index to the hash map.

*Complexity*
- Time Complexity: *O(n)*
- Space Complexity: *O(n)*

---

📂 *Links and Resources*

🤔 *Feedback and Suggestions*
I hope this video helps you solve the problem with confidence!
If you have any feedback or suggestions, drop them in the comments below. Your input helps me improve!

Happy coding, and I’ll see you in the next problem! 😊