Two Sum II - Input Array Is Sorted

Problem Statement

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers as an integer array [index1, index2] (both indices are incremented by one).

Note:

• The tests guarantee there is exactly one solution.
• You may not use the same element twice.
• The solution must use only constant extra space.

Solve Here: Two Sum II - Input Array Is Sorted

Examples:

Input	Target	Output
[2, 7, 11, 15]	9	[1, 2]
[2, 3, 4]	6	[1, 3]
[-1, 0]	-1	[1, 2]

Edge Cases:

1. Minimum array size: Array will always have at least 2 elements
2. Negative numbers: Array can contain negative numbers
3. Same numbers: You cannot use the same element twice
4. Index handling: Remember the array is 1-indexed in output

Solution Approaches:

1. Brute Force (Nested Loop)

• Description: This approach checks every pair of numbers to find the pair that adds up to the target.
• Time Complexity: O(n²) – due to nested loops
• Space Complexity: O(1) – no extra space used

fun twoSum(numbers: IntArray, target: Int): IntArray {
    for (i in numbers.indices) {
        for (j in i + 1 until numbers.size) {
            if (numbers[i] + numbers[j] == target) {
                return intArrayOf(i + 1, j + 1)
            }
        }
    }
    return intArrayOf()
}

2. Two Pointers

• Description: Utilizes two pointers—one starting at the beginning and the other at the end of the array. The goal is to adjust the pointers based on the sum of the two numbers at these positions.
• Time Complexity: O(n) – we traverse the array once
• Space Complexity: O(1) – only a few variables are used

fun twoSum(numbers: IntArray, target: Int): IntArray {
    var i = 0
    var j = numbers.size - 1
  
    while(i < j) {
        if(numbers[i] + numbers[j] > target) j--
        else if(numbers[i] + numbers[j] < target) i++
        else if(numbers[i] + numbers[j] == target) return intArrayOf(i + 1, j + 1)
    }
  
    return intArrayOf()
}

Complexity Comparison:

Approach	Time Complexity	Space Complexity
Brute Force	O(n²)	O(1)
Two Pointers	O(n)	O(1)

Conclusion:

The Two Pointers approach is optimal for this problem because it leverages the sorted nature of the array and reduces the time complexity to O(n) while maintaining constant space. The Brute Force solution, while straightforward, is less efficient and should be avoided for large inputs.