Two Sum Problem- Leetcode

This is a straightforward fundamental question for any student wanting to start the DSA journey. This article will help you to understand the problem in a very simple way and help you to code better in Java.

Problem Statement:

Two sum is an Array problem, that states suppose you are given an array of integer arr and an integer variable target. We need to return the indices of the two numbers such that they add up to the target.
- with the condition of assuming that each input would have exactly one solution, and we may not use the same element twice.

Input: arr = [2,7,11,15], target = 17
Output: [0,3]
Explanation: Because arr[0] + arr[3] == 17, we return [0, 3].

Explanation:

Let’s take an array arr, that contains the number of integers [2,7,11,15]. The target value is 17. To solve the following question we can use pointers i and j that will traverse the whole array and check if:-
arr[i] + arr[j] == target respectively.

checking for 1st iteration

If the sum of both numbers is not equal to the target value we will increment the pointers i and j accordingly.

checking for 2nd iteration

checking for 3rd iteration

If the sum of both numbers is equal to the target value we will return the indices of pointers i and j accordingly.
Therefore the output of the above problem would be 0 and 3.

Code:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int [] output = new int[2] ;
        for (int i = 0; i < nums.length; i++){
            for (int j = i+1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target){
                    output[0] = i;
                    output[1] = j;
                }
            }
        }
        return output;
    }
}

— -edited — -

Optimal Approach-

We can use the Hash function for the optimal approach (i.e O(n) time complexity)

• Initialize an empty Hash Set.
• For each integer in the array-
  Calculate the difference between the current element and the target value.
  Check whether the .difference calculated above is present in the set
• If the difference already exists in the set, return the current element index and the difference index as the result.
• Otherwise, insert the current integer into the set.

class Solution {
  public static int[] twoSum(int[] nums, int target) {
       Map<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int difference = target - nums[i];
            if (numMap.containsKey(difference)) {
                return new int[] { numMap.get(difference), i };
            } else {
                numMap.put(nums[i], i);
            }
        }
        return new int[] {};
  }

}

Hope this helps every beginner to start up their coding journey and practice more and more questions even if it means excelling at easy type questions first!

Thank you!
Oshi Raghav