Two Sum(LeetCode#1)

Introduction:

Welcome back to my "Mastering DSA with LeetCode" series! Today, we're tackling one of the most famous and fundamental interview questions out there: "Two Sum" (LeetCode #1). If you're starting your DSA journey, this problem is a must-solve, as it perfectly introduces the power and efficiency of using Hash Maps.

Understanding the Problem:

We are given an array of integers, nums, and an integer target. Our goal is to find two distinct indices i and j within the nums array such that nums[i] + nums[j] == target.

The problem guarantees that there will always be exactly one valid pair of indices, and we should return the answer with the smaller index first.

Let's illustrate with an example:

• Input: nums = [3, 4, 5, 6], target = 7

• Expected Output: [0, 1]

• Explanation: nums[0] (which is 3) + nums[1] (which is 4) equals 7. The indices are 0 and 1.

My Thought Process & Approach:

When first encountering "Two Sum," a common initial thought is to use nested loops. You could pick the first number, then iterate through the rest of the array to find its complement.

This brute-force approach has a time complexity of O(N^2), which means it gets very slow for large arrays. Given the efficiency expectations in coding interviews, I immediately thought about how to reduce that quadratic complexity.

This is where the magic of a HashMap comes in. A HashMap allows us to store key-value pairs and retrieve values by their keys in average O(1) time. For "Two Sum," the key insight is:

For each number nums[i] we encounter, we need to know if its "complement" (target - nums[i]) has already been seen in the array, and if so, what its index was.

Here's the refined, single-pass logic:

1. Initialize a HashMap: Create an empty HashMap where we will store (number, index) pairs. The number will be the key, and its index will be the value.

2. Iterate Through the Array (Once): Go through nums from left to right, using a single loop with index i.

3. Calculate Complement: For each nums[i], calculate complement = target - nums[i].

4. Check HashMap for Complement:

   • Before adding nums[i] to the map, check if the complement already exists as a key in our HashMap.

   • If hm.containsKey(complement) is true, it means we've found the other number of our pair! Its index is hm.get(complement), and the current number's index is i. We store these two indices (ensuring the smaller index comes first, as per the problem) and return immediately because the problem guarantees exactly one solution.

5. Add to HashMap: If the complement was not found, it means nums[i] itself hasn't been used yet as part of a pair (from the numbers we've seen so far). So, add nums[i] and its current index i to the HashMap: hm.put(nums[i], i). This makes nums[i] available as a complement for future numbers in the array.

This approach allows us to find the pair in a single pass, significantly improving efficiency.

Java Code Implementation:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> hm = new HashMap<>();
        int n = nums.length;
        int[] ans = new int[2];
        for(int i =0;i<n;i++){
            if(hm.containsKey(target-nums[i])){
                ans[0] = hm.get(target-nums[i]);
                ans[1] = i;
            }
            hm.put(nums[i],i);
        }
        return ans;
    }
}

Time and Space Complexity Analysis:

• Time Complexity: O(N)

  • We iterate through the input array nums exactly once.

  • Inside the loop, HashMap.containsKey() and HashMap.put() operations take average O(1) time.

  • In the worst case (the solution pair is at the end, or no solution found), the loop runs N times, making the overall time complexity linear, O(N).

  • This is optimal time complexity because, in the worst case, you might need to look at every element once.

• Space Complexity: O(N)

  • In the worst case (e.g., the solution pair is at the end, or all elements are unique up to the solution), the HashMap will store up to N unique elements and their indices.

  • Therefore, the space required by the HashMap grows linearly with the size of the input array, resulting in O(N) space complexity. This is optimal for approaches using auxiliary space to track seen elements.