Problem: Leet Code 1 - Two Sum

QUESTION:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

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

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 10<sup>4</sup>

• -10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>

• -10<sup>9</sup> <= target <= 10<sup>9</sup>

• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less thanO(n<sup>2</sup>) time complexity?

---

💭Analyzing question:

1. To check that any two numbers add up to the given target is the main notion of this given question.

2. We can either check sum of each element and its consecutive element add up to the target element received from the user. This method often comes to the mind, and it involves lots of computation by the computer, so it is considered as Brute force Approach to solve a problem.

In other way, in which this problem can be approached with is to find difference between the target and the array element in order, if the difference is present in the array, we can directly return the position that is the index at which the element is present by using HashMap concept, which can be much more optimal one in case of computation. The required code snippet is attached below.

---

💡Approach:

• Declare HashMap to store the array element and the index at which its is present

• Using loop find the difference between the target element and the array element for each instance of loop.

• The difference is stored in variable complement, and presence of complement in map is checked using built-in function.

• If present, then the index of the difference and the current array element is returned in the form of array.

• If not present, then the array element and its index is added to the hashmap as Key-Value pairs.

In case we don’t find any pair of indices, we return an empty array.

---

💻My Java Code:

Brute force Approach:

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

Optimal Approach:

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

---

🖥️Output:

---

⏱️Efficiency of my Approaches:

Brute force Approach:

• Time Complexity: O(N²)

• Space complexity: O(1)

Optimal Approach:

• Time Complexity: O(N²)

Space complexity: O(N)

---

🧠My Learnings:

1. Looping and Conditional Statements Concept

HashMap and its operations

---

Tags:

#Java #Leetcode #ProblemSolving #DSA