Two Sum — LeetCode Java Solution

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

In this blog, let’s solve Two Sum which is one of the Blind 75 List of LeetCode Problems.

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

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

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

Recommended YouTubers for LeetCode Problems:

1. NeetCode

2. Take U Forward

Free Resources for Learning Data Structures and Algorithms:

1. NeetCode Roadmap

2. Striver’s SDE Sheet

Recommended Courses for Learning Data Structures and Algorithms:

1. NeetCode Courses
2. ZTM: Mastering the Coding Interview (Big Tech): Available on Udemy and ZTM Academy
3. ZTM: Mastering the Coding Interview: Available on Udemy and ZTM Academy
4. Data Structures & Algorithms, Level-up for Coding Interviews Course
5. Become a Job Ready Programmer (Java)
6. Striver’s A2Z (Free) Course

Top Coursera Courses for Learning Data Structures and Algorithms:

1. Coding Interview Preparation (Meta)
2. Algorithms Course Part I (Princeton University)
3. Algorithms Course Part II (Princeton University)
4. Data Structures and Algorithms Specialization (UC San Diego)
5. Algorithms Specialization (Stanford)

(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 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 🙂.