Two Sum — LeetCode Java Solution
Tags: java, datastructures, algorithms, leetcode
Published: 2023-08-11 10:45:56

Hello readers, let’s solve a LeetCode problem today.

In this blog, let’s solve [Two Sum](https://leetcode.com/problems/two-sum/description/) which is one of the [Blind 75 List of LeetCode Problems](https://leetcode.com/discuss/interview-question/460599/Blind-75-LeetCode-Questions).

The Two Sum problem is a classic coding challenge and the No. 1 problem on LeetCode, that asks us to find two numbers in an array that add up to a given target. 

In this blog post, we will explore two different approaches to solving this problem: the Brute Force approach and the Optimal approach. We will examine the problem statement, understand the test cases, and dive into the code implementations for both approaches. Additionally, we will analyze the time and space complexities of each solution.

**Understanding the Problem:**

- Given an array of integers **`nums`** and a target integer **`target`**, the task is to find two numbers in the array such that their sum equals the target.
- Our objective is to return the indices of these two numbers.
- The problem also mentions that each input will have ***exactly* one solution**, and you cannot use the *same* element twice.

**Understanding the Test Cases:**

To better understand the problem, let's consider a few simple test cases:

**Test Case 1:**

```
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
```

Explanation: The sum of the numbers at indices 0 and 1 is equal to the target value of 9.

**Test Case 2:**

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

Explanation: The sum of the numbers at indices 1 and 2 is equal to the target value of 6.

**Test Case 3:**

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

Explanation: The sum of the numbers at indices 0 and 1 is equal to the target value of 6.

**Brute Force Approach: Nested Loops**

```java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = 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) {
                    result[0] = i;                    
                    result[1] = j;                    
                    return result;
                }
            }
        }
        return result;
    }
}
```

**Key Points:**

- We go through each number in the array and add it to every other number to see if their sum equals the target.
- If we find two numbers that add up to the target, we return their indices.

**Time Complexity:** O(N^2)

- The brute force approach uses nested loops to check every pair of numbers, resulting in a time complexity of O(N^2), where n is the size of the input array.

**Space Complexity:** O(1)

- The space complexity of this approach is O(1) because we only need a fixed-size **`result`** array to store the indices.

**Optimal Approach: Hashmap**

```java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++) {
            int numberToFind = target - nums[i];
            if(map.containsKey(numberToFind)) {
                result[0] = map.get(numberToFind); 
                result[1] = i;
            }
            map.put(nums[i], i);
        }
        return result;
    }
}
```

**Key Points:**

- For each number in the array, we calculate the difference between the target and that number.
- We check if this difference exists in the HashMap, which means we have found a pair of numbers that add up to the target.
- If we find such a pair, we return their indices.
- Otherwise, we keep adding the numbers and their indices to the HashMap.

**Time Complexity:** O(N)

- The optimal approach has a time complexity of O(N), because we iterate through the input array **`nums`** only once, and each lookup operation in the HashMap takes constant time.

**Space Complexity:** O(N)

- The space complexity of the optimal approach is O(N) because, in the worst case, we may need to store all the elements of the array in the HashMap.

**Google Engineer - Coding Interview Style - Video Solution**

https://www.youtube.com/watch?v=XKu_SEDAykw

**Also, checkout, NeetCode Video Solution:** 

https://www.youtube.com/watch?v=KLlXCFG5TnA

**Recommended Resources to Learn Data Structures and Algorithms**

Basics of DS Algo Blogs:

1. [Hashing in Java](https://medium.com/techsoftware/understanding-hashing-in-java-exploring-hashmap-and-hashset-b2c7d28453c)

Recommended YouTubers for LeetCode Problems:

1. [NeetCode](https://www.youtube.com/@NeetCode)

2. [Take U Forward](https://www.youtube.com/@takeUforward/featured)

Free Resources for Learning Data Structures and Algorithms:

1. [NeetCode Roadmap](https://neetcode.io/roadmap?utm_source=aswin)

2. [Striver’s SDE Sheet](https://takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems/)

Recommended Courses for Learning Data Structures and Algorithms:

1. [NeetCode Courses](https://neetcode.io/courses?utm_source=aswin)
2. ZTM: Mastering the Coding Interview (Big Tech): Available on [Udemy](https://click.linksynergy.com/link?id=JDofPMV5KuY&offerid=1060092.3919716491451706865583445&type=2&murl=https%3A%2F%2Fwww.udemy.com%2Fcourse%2Fmaster-the-coding-interview-big-tech-faang-interviews%2F) and [ZTM Academy](https://academy.zerotomastery.io/a/aff_rml6679s/external?affcode=441520_dcwk-s8s)
3. ZTM: Mastering the Coding Interview: Available on [Udemy](https://click.linksynergy.com/link?id=JDofPMV5KuY&offerid=1060092.391976131953022569348758&type=2&murl=https%3A%2F%2Fwww.udemy.com%2Fcourse%2Fmaster-the-coding-interview-data-structures-algorithms%2F) and [ZTM Academy](https://academy.zerotomastery.io/a/aff_nqb6sg6w/external?affcode=441520_dcwk-s8s)
4. [Data Structures & Algorithms, Level-up for Coding Interviews Course](https://click.linksynergy.com/link?id=JDofPMV5KuY&offerid=1060092.391975289945963380819471&type=2&murl=https%3A%2F%2Fwww.udemy.com%2Fcourse%2Fcpp-data-structures-algorithms-levelup-prateek-narang%2F)
5. [Become a Job Ready Programmer (Java)](https://medium.com/techsoftware/become-a-job-ready-programmer-1e5a8cdd1351)
6. [Striver’s A2Z (Free) Course](https://takeuforward.org/strivers-a2z-dsa-course/strivers-a2z-dsa-course-sheet-2/)

Top Coursera Courses for Learning Data Structures and Algorithms:

1. [Coding Interview Preparation (Meta)](https://imp.i384100.net/QyNgyo)
2. [Algorithms Course Part I (Princeton University)](https://imp.i384100.net/KjqAe9)
3. [Algorithms Course Part II (Princeton University)](https://imp.i384100.net/VmbWyE)
4. [Data Structures and Algorithms Specialization (UC San Diego)](https://imp.i384100.net/g1AVOA)
5. [Algorithms Specialization (Stanford)](https://imp.i384100.net/75G7ag)

(Note: The Coursera courses can be audited to get free access to the lectures)

**🎙 Disclosure:** Please note that some of the links mentioned on this page may be affiliate links. This means that if you click on one of these links and make a purchase, I may earn a small commission from the sale.

**Who Am I?**

I’m Aswin Barath, a Software Engineering Nerd who loves building Web Applications, now sharing my knowledge through [Blogging](https://medium.com/techsoftware) during the busy time of my freelancing work life. Here’s the link to all of my craziness categorized by platforms under one place: https://linktr.ee/AswinBarath

**Keep Learning**

Now, I guess this is where I say goodbye 👋. But, hey it’s time for you to start **learning** with your newfound Knowledge(Power)👨‍💻👩‍💻. Good Job that you made it this far 👏 & **Thank you** so much for reading my Blog 🙂.