Leetcode – 1 – Two Sum

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1]

Description:

The essence of this problem is that we have to find the index of the elements from the given input array which will add upto the target value.

Brute Force Solution: (Two loops)

On seeing this problem we will imagine that we have an array which we have to be iterated to its length to cover all the elements in the array. Lets assign the index pointer as i for the loop

We also derive that we have to take the reference to the next element which will also to be iterated to the length of the array. The index pointer for this can be j. pointer j will be i+1

We can check the sum of two elements at index i , j and compare with the target value. With this we will get the index value of the first and second element

  • First loop , index variable i
  • second loop , index variable j = i + 1
  • Add the element at the index i and j and check if its equal to the target value
  • return elements at i and j

1

Code:

public int[] twoSum(int[] nums, int target){
  if(nums != null && nums.length == 1 && target == nums[0]){
    return target;
  }

  if(nums != null && nums.length > 0){
     int n = nums.length;
     int[] result = new result[2];
    for(int i=0;i<n;i++){
        for(int j = i+1;j<n;j++){
           if(nums[i] + nums[j] == target){
              result[0] = nums[i];
              result[1] = nums[j];
              return result;
           }
        }
    }
  }
}

Time Complexity: O(n2)

  • first loop executes the statement inside it for n times
  • second loop executes the statement inside it for n times
  • so, n * n = O(n2)

Space Complexity:O(1)

  • you will be assigning values for i, j, result elements inside the loops  – O(1)

Efficient solution: (Using HashMap)

If we think further we can store the difference of the elements from the target value in a hash map and return the elements index when we encounter the element again on iteration

  • First loop , index variable i
  • Check of the key exists in a hashmap otherwise add the difference
  • If key exists, then we return the index of the previously stored difference and the current index

2

Code:

public int[] twoSum(int[] nums, int target){
  int n = nums.length;
  int[] result = new int[2];
  
  HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for(int i=0;i<n;i++){
        if(map.containsKey(nums[i])){
            result[0] = map.get(nums[i]);
            result[1] = i;
            break;
        }
        else{
            map.put(target - nums[i], i);
        }

  }
  return result;
  
  }

Time Complexity: O(n)

  • put and get operation for the HashMap involves O(1)
  • Loop through the elements upto n – O(n)

Space Complexity: O(n)

  • We will be adding elements to the map which will be O(n)

Available Test Cases: 16

  • Check for null input array
  • Check for duplicate elements
  • Check for target which does not appear
  • Check with duplicate elements
  • Check for negative elements
  • Check for multiple target values

 Github:

Leetcode_1_Two_sum

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: