Algorithm_Day01_Two Sum_lc#1

🧩 Problem Description

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

💡 Naive Approach (Brute Force)

The most straightforward idea is to check all pairs using two nested loops.
This guarantees we find the solution, but it’s inefficient for large arrays.

🔢 Java Code – Brute Force

class Solution {
    public int[] twoSum(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 new int[] {}; 
    }
}

⏱ Complexity

• Time Complexity: O(n²)
• Space Complexity: O(1)

⚠️ This solution does not scale — it fails performance constraints on large inputs.

---

💡 Optimized Approach (Hash Map)

To reduce time complexity, we use a hash map to store values we’ve seen and their indices.
While iterating, we check whether target - current has already been seen.

🔎 Key Points

• In practice, hash tables are fast — usually O(1) for most operations.
• Worst case happens when many keys collide (bad hash function or high load factor).
• Java’s HashMap uses a red-black tree (Deeper explanation will be covered in a future post.) for long collision chains (O(log n) worst case for search).

🔢 Java Code – Hash Map

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(); // hashtable always 
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {
                return new int[] {seen.get(complement), i};
            }
            seen.put(nums[i], i);
        }
        return new int[] {}; 
    }
}

⏱ Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

✅ Efficient and suitable for large datasets.

---

✍️ Summary

• Always start with brute force to validate your logic.
• Then optimize using data structures like hash maps.