Two Sum - Java Solution

1. Introduction

In this post, we'll delve into a common problem in algorithmic interviews and coding challenges: finding two numbers in a sorted array that sum up to a specific target. This problem is an excellent example of how to apply the two-pointer technique in a sorted array to achieve an efficient solution.

Problem

Given a 1-indexed, sorted array of integers 'numbers', we are tasked with finding two numbers such that their sum equals a given target number. The solution must return the indices of these two numbers, incremented by one, as an integer array of length 2. It's important to note that each number in the array can only be used once and the solution should only use constant extra space.

2. Solution Steps

1. Initialize two pointers: one at the start and another at the end of the array.

2. Calculate the sum of the elements pointed by the two pointers.

3. If the sum equals the target, return the indices of these two elements.

4. If the sum is less than the target, move the start pointer to the right.

5. If the sum is greater than the target, move the end pointer to the left.

6. Repeat steps 2-5 until the solution is found.

3. Code Program

public class TwoSum {
    public static void main(String[] args) {
        int[] numbers = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(numbers, target);
        System.out.println("[" + result[0] + ", " + result[1] + "]"); // Output
    }

    // Function to find two numbers such that they add up to a specific target
    public static int[] twoSum(int[] numbers, int target) {
        int start = 0; // Starting pointer
        int end = numbers.length - 1; // Ending pointer

        while (start < end) {
            int sum = numbers[start] + numbers[end]; // Calculate sum of the two numbers
            if (sum == target) {
                return new int[]{start + 1, end + 1}; // Return indices (1-indexed)
            } else if (sum < target) {
                start++; // Move the start pointer to the right
            } else {
                end--; // Move the end pointer to the left
            }
        }
        return new int[]{-1, -1}; // Return default value if no solution is found
    }
}

Output:

[1, 2]

Explanation:

1. twoSum: This function uses a two-pointer approach. The start pointer is initialized at the beginning of the array, and the end pointer at the end.

2. In each iteration, it calculates the sum of the elements pointed to by start and end.

3. If this sum equals the target, it returns the indices of these elements (adjusted for 1-indexing).

4. If the sum is less than the target, the algorithm moves the start pointer to the right, as the array is sorted in non-decreasing order.

5. If the sum is greater, the end pointer is moved to the left.

6. The loop continues until a solution is found or all possibilities are exhausted.