problem URL:https://leetcode.com/problems/two-sum/

Two Sum Problem
Difficulty Level: Easy
Statement: Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.

Approach 1: Brute Force

The brute force approach is simple. Loop through each element x and find if there is another value that equals target-x. To find the second index, we need to iterate through the rest of the array elements.
Time-Complexity: O(n^2)
Space-Complexity: O(1)

Code:

    public int[] twoSum(int[] nums, int target) 
    {
        int res[] = new int[2];  //1
        for(int i=0;i<nums.length-1;i++)  //2
        {
            for(int j=i+1;j<nums.length;j++)  //3
            {
                if(nums[j] + nums[i]==target)  //4
                {
                    res[0] = i;
                    res[1] = j;
                }
            }
        }
        
        return res;  //5
    }

Code WalkThrough:
Step 1: Create an array of size 2 to store the result.
Step 2: The first loop to iterate the 1st element.
Step 3: Second loop to find the second element whose sum is equal to the target.
Step 4: Checking if the sum of the first loop index(i) element and second loop index(j) element is equal to the target. if step 4 is true then we will store the index in the result array(res) that we created in step 1.
Step-5: Once the iteration is completed, we will return the result array(res).

Approach-2: Using HashTable

We can reduce the time complexity by looking up a value to O(1) using a HashMap that maps a value to its index.
Time-Complexity: O(n)
Space-Complexity: O(n)

public int[] twoSum(int[] numbers, int target) {
    Map<Integer, Integer> map = new HashMap<>();  //1
    for(int i = 0; i < nums.length; i++) 
    {
       if(map.containsKey(target - nums[i])) { //2
        return new int[]{map.get(target - nums[i]), i}; //3
       }
        map.put(nums[i], i); //4
    }
  throw new IllegalArgumentException("No two sum solution");
}

Code WalkThrough:
Step 1: Create a hashmap to store the array elements as Key and the index as value
Step 2: We are checking whether the second value(target-nums[i]) is present in the HashMap or not.
Step 3: If the step-2 check is true, then we are creating an array and fill the required index by fetching it from the hash map.
Step 4: If the step-2 check is false, then we are adding the value at i index into the Hash Map.

Categorized in:

Tagged in:

,