Two Sum II – Input Array Is Sorted | Two Sum II – Input Array Is Sorted LeetCode Solution in Java

Introduction

LeetCode is a popular platform for practicing coding and algorithmic problems. One such problem is “Two Sum II – Input Array Is Sorted,” which is a great exercise for enhancing your problem-solving skills. In this blog post, we will explore this problem, understand its requirements, and implement a solution in Java.

Problem Statement

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

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

Let’s break down the problem with an example:

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [2,7]

In this example, we have an input array numbers that is sorted in ascending order. We need to find two numbers in the array that add up to the target value 9. The numbers 2 and 7 meet this criteria, so the function should return [2,7].

Approach

To solve this problem, we can use a two-pointer approach. Here are the steps:

1. Initialize two pointers, left and right, at the beginning and end of the array, respectively.
2. While left is less than right, do the following: a. Calculate the sum of the elements at positions left and right. b. If the sum is equal to the target, return the pair [numbers[left], numbers[right]] as the solution. c. If the sum is less than the target, increment left to move towards larger values. d. If the sum is greater than the target, decrement right to move towards smaller values.
3. If no such pair is found while traversing the array, return an empty array since there is always exactly one solution.

Let’s implement this approach in Java.

Java Solution

Here’s the Java code to solve the “Two Sum II – Input Array Is Sorted” problem using the two-pointer approach:

public int[] twoSum(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;

    while (left < right) {
        int sum = numbers[left] + numbers[right];

        if (sum == target) {
            return new int[]{left + 1, right + 1}; // Add 1 to convert from 0-based index to 1-based index
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    return new int[0]; // If no solution is found
}

Let’s analyze the code:

• We initialize two pointers, left and right, at the start and end of the array, respectively.
• We use a while loop to iterate through the array. The loop continues as long as left is less than right.
• Inside the loop, we calculate the sum of the elements at the left and right positions.
• If the sum is equal to the target, we return a new array containing the indices of the two numbers that add up to the target. Note that we add 1 to the indices to convert from 0-based indexing to 1-based indexing as required by the problem statement.
• If the sum is less than the target, we increment left to move towards larger values.
• If the sum is greater than the target, we decrement right to move towards smaller values.
• If the loop completes without finding a solution, we return an empty array to indicate that no such pair exists.

Complexity Analysis

• Time Complexity: The two-pointer approach runs in linear time, O(n), where n is the number of elements in the input array. This is because we traverse the array once from both ends.
• Space Complexity: The space complexity is O(1) as we are using a constant amount of extra space regardless of the input size.

Testing the Solution

Let’s test our solution with a few examples to ensure it works correctly.

Example 1:

int[] numbers = {2, 7, 11, 15};
int target = 9;
int[] result = twoSum(numbers, target);
System.out.println(Arrays.toString(result)); // Output: [2, 7]

The function correctly returns [2, 7], as explained earlier.

Example 2:

int[] numbers = {1, 2, 3, 4, 4, 9, 56, 90};
int target = 8;
int[] result = twoSum(numbers, target);
System.out.println(Arrays.toString(result)); // Output: [4, 4]

In this example, we have repeated values in the array, and the function still finds the correct pair [4, 4] that adds up to the target.

Example 3:

int[] numbers = {1, 2, 3, 4};
int target = 8;
int[] result = twoSum(numbers, target);
System.out.println(Arrays.toString(result)); // Output: [2, 4]

Even when the input array has only unique elements, the function correctly returns [2, 4] as the solution.

Conclusion

In this blog post, we explored the “Two Sum II – Input Array Is Sorted” problem on LeetCode. We discussed the problem statement, the two-pointer approach to solve it, and implemented the solution in Java. The two-pointer approach is an efficient way to find pairs of elements that add up to a specific target in a sorted array.

By understanding and implementing such problems, you can improve your algorithmic and coding skills. Solving problems on platforms like LeetCode is an excellent way to practice and sharpen your abilities. Happy coding!

Thank You!

Read More-

Merge Two Binary Trees – Leetcode-617 | Merge Two Binary Trees LeetCode Solution in Java – https://kamleshsingad.com/how-to-merge-two-binary-trees-solution-in-java/

206. Reverse Linked List | Reverse Linked List LeetCode Solution in Java | Code with Kamlesh – https://kamleshsingad.com/what-is-reverse-linked-list-leetcode-solution-in-java/

Contains Duplicate LeetCode Solution in Java | Leet code Must Do Questions | Code with Kamlesh – https://kamleshsingad.com/contains-duplicate-leetcode-solution-in-java/