Java

LeetCode Problem-1 Two Sum (Java)

Launching a fresh series dedicated to conquering LeetCode Problems, my aim to provide more than just solutions. In each leetcode problem, expect a comprehensive breakdown of the code, a deep dive into the techniques employed, and a thoughtful exploration of why we opted for a specific approach. Join me as I embark on this journey of problem-solving, where each challenge serves as a stepping stone to honing our coding skills and making informed algorithmic choices. Welcome to a series that not only solves problems but also demystifies the thought processes behind effective coding solutions.

Leetcode Problem -1 (Two Sum)

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 <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Solution:

We will use two-pointer algorithm to solve this problem.

✅ What is two-pointer technique?

The two-pointer approach is a technique used in algorithms and data structures to solve problems by using two pointers (or indices) that traverse the data structure in some way. The technique is often employed to optimize the time complexity of the solution.

Here are two common variations of the two-pointer approach:

👉 Two Pointers Moving Towards Each Other:

• In this variation, two pointers start at opposite ends of the data structure (e.g., an array or a linked list) and move toward each other until they meet.
• This is particularly useful for problems where you need to find a pair, triplet, or subarray with a specific property.
• This approach is often employed when the array is sorted.

👉 Two Pointers Moving in the Same Direction:

• In this variation, two pointers start at the same end of the data structure and move in the same direction, maintaining a certain distance between them.
• This approach is useful for problems where you need to find a subarray or a sequence with a specific property.
• It can also be used for problems involving sliding windows.

The two-pointer approach is often favored for its simplicity and efficiency. It can help reduce the time complexity of a solution from O(n²) to O(n) or O(n log n), making it more scalable for larger inputs.

The choice of using the two-pointer approach depends on the nature of the problem and the properties of the data structure involved. It is commonly used in array manipulation problems, searching for pairs or subarrays, and optimizing algorithms for linear or sublinear time complexity.

Java Code Solution:

public int[] twoSum(int[] nums, int target) {
    // Create a map to store the difference and index of each element
    Map<Integer, Integer> numIndices = new HashMap<>();

    // Iterate through the array using two pointers
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];

        // Check if the complement is in the map
        if (numIndices.containsKey(complement)) {
            // Return the indices of the two numbers
            return new int[]{numIndices.get(complement), i};
        }

        // Store the current number and its index in the map
        numIndices.put(nums[i], i);
    }

    // If no solution is found, return an empty array
    return new int[]{};
}

Code explanation:

👉 Method Signature:

public int[] twoSum(int[] nums, int target)

This method takes an array of integers (nums) and an integer target as input and returns an array of two integers representing the indices of the two numbers in the array that add up to the target.

👉 HashMap to Store Complements and Indices:

Map<Integer, Integer> numIndices = new HashMap<>();

We use a HashMap named numIndices to store the difference (complement) between the target and the current number, along with the index of that number in the array.

👉Iterating Through the Array:

for (int i = 0; i < nums.length; i++)

We iterate through the array using a for loop, where i represents the current index.

👉Calculating Complement:

int complement = target — nums[i];

For each element in the array, we calculate its complement by subtracting it from the target.

👉 Checking for Complement in HashMap:

if (numIndices.containsKey(complement))
We check if the complement is already in the numIndices map. If it is, we have found a pair whose sum is equal to the target.

👉 Returning Result:

return new int[]{numIndices.get(complement), i};

If a pair is found, we return an array containing the indices of the two numbers.

👉 Storing Current Number and Index in HashMap:

numIndices.put(nums[i], i);
If a pair is not found, we store the current number and its index in the numIndices map. This information will be used in future iterations to check for complements.

👉Handling No Solution Case:

return new int[]{};
If no solution is found during the iteration, we return an empty array.

This implementation uses two pointers, one at the beginning and one at the end of the array. By adjusting the pointers based on the comparison of the current sum with the target, the algorithm can find the indices in a more efficient manner than the O(n²) brute force approach.

✅ Time Complexity: O(n)
The algorithm iterates through the array once. In each iteration, it performs constant time operations (such as map lookups and updates). Therefore, the overall time complexity is linear with respect to the size of the input array, making it O(n).

✅ Space Complexity: O(n)
The space complexity is also linear. The algorithm uses a HashMap to store the elements of the array along with their indices. In the worst case, the HashMap may store all elements of the array, resulting in O(n) space complexity.

Why we use two-pointer approach to solve this leedcode problem?

In the context of the Two Sum problem, using the two-pointer approach can significantly improve the time complexity of the solution compared to a naive, brute-force approach.

Here’s why the two-pointer approach is effective for the Two Sum problem:

👉 Optimized Time Complexity:

• The brute-force approach would involve checking every possible pair of numbers in the array to see if they add up to the target. This would result in a time complexity of O(n²), where n is the length of the array.
• The two-pointer approach, on the other hand, allows us to find the solution in linear time, O(n). This is achieved by maintaining two pointers that traverse the array simultaneously.

👉 Utilizing Sorted Order (for some variations):

• While the Two Sum problem doesn’t explicitly require a sorted array, the two-pointer approach is often associated with sorted arrays. If the array is sorted, you can use the two-pointer approach with pointers starting at both ends and moving towards each other. This further optimizes the solution.

👉 Efficiently Exploring Possibilities:

• The two-pointer approach efficiently explores possibilities without unnecessary repetition. By using the complement of the current element (target minus the current element), the algorithm checks if the complement is already encountered in the previous elements. This avoids redundant checks and ensures a linear runtime.

👉 Space Efficiency:

• The two-pointer approach often requires constant space (in addition to the input space) for the pointers and a few variables. This makes it space-efficient compared to solutions that require additional data structures like hash tables.

In summary, the two-pointer approach is chosen for the Two Sum problem (and similar problems) because it allows for an efficient exploration of possibilities, resulting in a linear time complexity solution, which is a significant improvement over the brute-force approach. Additionally, it can be adapted to sorted arrays, providing further optimizations in certain cases.

“Congratulations on tackling this leetcode problem! Your dedication to sharpening your skills is truly commendable. Stay connected for upcoming leetocde problems in this series that will further fuel your passion for problem-solving. Remember, the journey of a coder is a continuous exploration. Happy coding, and see you in the next challenge!”

✅Similar Leetcode Problems 👇

👉 Leetcode Problem-167 Two Sum II — Input Array Is Sorted [Medium]

👉 LeetCode Problem-15 3Sum [Medium]

👉LeetCode Problem-16 3Sum Closest [Medium]

❤️ Support & Engagement ❤️

❤ If you find this article informative and beneficial, please consider showing your appreciation by giving it a clap 👏👏👏, highlight it and replying on my story story. Feel free to share this article with your peers. Your support and knowledge sharing within the developer community are highly valued.
❤ Please share on social media
❤ Follow me on : Medium || LinkedIn
❤ Check out my other articles on Medium
❤ Subscribe to my newsletter 📧, so that you don’t miss out on my latest articles.
❤ If you enjoyed my article, please consider buying me a coffee ❤️ and stay tuned to more articles about java, technologies and AI. 🧑‍💻