Leet Code 1: Two Sum

https://leetcode.com/problems/two-sum/description/ 

 

Given the constraints:

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹

Let’s analyze what time complexities (TC) are feasible for this problem:

---

✅ Feasible Time Complexities for n ≤ 10⁴

Time Complexity	Feasible?	Reason
O(1)	✅	Always fast, constant-time ops
O(log n)	✅	Log(10⁴) = 14, extremely fast
O(n)	✅	Linear scan over 10⁴ elements is very fast (~0.001 sec)
O(n log n)	✅	10⁴ * log(10⁴) ≈ 140,000 operations – totally fine
O(n²)	⚠️ Borderline	10⁸ operations (10⁴²) – may work, but not preferred for interviews
O(2^n)	❌	2^10⁴ = way too large
O(n!)	❌	Factorial growth explodes even for small n

✅ Best Time Complexity You Should Aim For:

• O(n) using HashMap:
  This is the optimal solution for the Two Sum problem.

❌ Avoid:

• Brute-force nested loops (O(n²)), which will do ~10⁸ comparisons.

---

💡 Summary Table:

Complexity	Status	Use Case
O(1)	✅ Feasible	Constant logic, math
O(log n)	✅ Feasible	Binary search
O(n)	✅ Feasible	Hash maps, one-pass logic
O(n log n)	✅ Feasible	Sorting, trees, maps
O(n²)	⚠️ Risky	Brute-force double loop
O(2^n), O(n!)	❌ Too slow	Recursion, permutations

---

• You can't use the same element twice.
• There is exactly one valid answer.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

package jan25;

import java.util.HashMap;

public class TwoSum {
    public static void main(String[] args) {
        int[] result = twoSum(new int[]{2, 8, 7, 11, 15}, 9);
        System.out.println("[" + result[0] + ", " + result[1] + "]");
    }

    public static int[] twoSum(int[] nums, int target) {
        // Space: O(n) — In worst case, we may store all n numbers in the map
        HashMap<Integer, Integer> map = new HashMap<>(); // value → index

        // Time: O(n) — Loop runs once for each of the n elements
        for (int i = 0; i < nums.length; i++) {
            // Time: O(1) — Arithmetic operation
            int complement = target - nums[i];

            // Time: O(1) — HashMap lookup for complement
            if (map.containsKey(complement)) {
                // Time: O(1) — HashMap get operation
                return new int[]{map.get(complement), i};
            }

            // Time: O(1) — HashMap put operation
            map.put(nums[i], i);
        }

        // Time: O(1) — Default return, though problem guarantees one solution
        return new int[]{};
    }
}

Case	Time Complexity	Space Complexity	Explanation
Best	O(1)	O(1)	Complement found in the very first or early iteration.
Average	O(n)	O(n)	One pass through n elements; each insert and lookup is O(1).
Worst	O(n)	O(n)	Complement found at the end; map stores all elements before that point.

✅ Note: HashMap operations (put, get, containsKey) are O(1) on average due to constant-time hashing.
❗ In rare cases of hash collisions (Java’s internal handling), it could degrade, but average-case holds for interviews.