Leetcode - Two Sum problem in java

The Two Sum problem from leetcode is a algorithm challenge where you need to find two numbers in an arraythat add up to a specific target.

Problem Statement

Given an array of integers 'nums' and an integer 'target', return the indices of the two numbers such that tey add up to 'target'.
You may not use the same element twice.

Example

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

Initial Approach

Solution 1. Brute Force

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Loop through each element
        for (int i = 0; i < nums.length; i++) {
            // Loop through each element after the current element
            for (int j = i + 1; j < nums.length; j++) {
                // Check if the sum of the two elements equals the target
                if (nums[i] + nums[j] == target) {
                    // Return the indices of the two elements
                    return new int[] {i, j};
                }
            }
        }
        // If no solution is found, throw an exception
        throw new IllegalArgumentException("No two sum solution");
    }
}

#1. loop through each element: The outer loop iterates through each element in the array starting from the first element.
#2. loop through each subsequent element: The inner loop interates through the elements that come after the current element in the outer loop.
#3. check if the sum equals the target: inside the inner loop, we check if the sum of the elements at indices 'i' and 'j' equals the target.
#4. return the indices. If the sum equals the target, we return the indieces '[i,j]'.
#5. Handle no solution case: If no pair is found that sums to the target, we throw an 'IllegalArgumentException'.

Complexity Analysis

• Time complexity 0(N^2)
• Space complexity 0(1)

Solution 2. Hash Map

Using Hash Map is a more efficient solution using a HashMap.

-- What is Hash Map?--

A 'HashMap' is a part of Java's Collection Framework and provides a way to store key-value pairs. It is often implementation of the 'Map' interface and is often used for its fast retrieval capabilities.

⭐key characteristics of HashMap⭐
1. unordered collectoin
2. allows null values
3. non-sysnchronized ( you should use 'Collections.synchronizedMap()'

🌟Solution using HashMap🌟
1. Store Complement
As we iterate through the array, we calculate the complement(i.e.. 'target-nums[i])
2. Check Complement
Before adding the current element to the map, we check if its complement is already present in the map.
3. Return Indices.
If the complement exists, we return the indices of the complement and the current element.

import java.util.HashMap;
import java.util.Map;

class Solution{
	public int[] twoSum(int[] nums, int target){
    //HashMap to store the number and its index
    Map<Integer,Integer> map = new HashMap<>();
    
    //Iterate through the array
    for (int i=0; i<nums.length; i++){
    int complemet = target-nums[i]
    //check if the complement is already in the map 
    
    if (map.containsKey(complement)){
    //if found, return the indices of the complement and current number
    return new int[] { map.get(complement),i};
    //add the current number and its index to the map
    map.put(nums[i],i); 
    
    //if no solution is found, throw an exception 
    throw new IllegalArgumentException("No two sum solution"); 
    }
    }