167. Two Sum II - Input Array Is Sorted

INFO

Problem: Two Sum II - Input Array Is Sorted

Pattern: Two pointers

This is a variation of Two Sum where the input array is already sorted and the answer must use one-based indexes. Because the array is sorted, we do not need a dictionary. We can use two pointers and move them based on the current sum.

Approach

Start one pointer at the beginning and one pointer at the end:

1. Add numbers[i] + numbers[j].
2. If the sum is smaller than the target, move i right to increase the sum.
3. If the sum is larger than the target, move j left to decrease the sum.
4. If the sum equals the target, return [i + 1, j + 1].

The pointer movement works only because the array is sorted. A larger left value increases the sum, and a smaller right value decreases it.

Swift Notes

The result uses one-based positions, so the returned indexes are i + 1 and j + 1. This is different from most Swift array work, where indexes are zero-based.

The implementation uses a while i < j loop so the same element is never used twice.

Complexity

• Time complexity: O(n).
• Space complexity: O(1).

Edge Cases

• Negative numbers are valid.
• The answer may include the first or last element.
• Do not forget that the returned indexes are one-based.

class Solution {
    func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
        var i = 0
        var j = numbers.count - 1
        var result: [Int] = []
        while i < j {
            if numbers[i] + numbers[j] < target {
                i += 1
                continue
            }
            if numbers[i] + numbers[j] > target {
                j -= 1
                continue
            }
            if numbers[i] + numbers[j] == target {
                result = [i + 1, j + 1]
                break
            }
        }
        return result
    }
}

var solution = Solution()

var testcase1 = solution.twoSum([2,7,11,15], 9)
print(testcase1) // [1, 2]

var testcase2 = solution.twoSum([2,3,4], 6)
print(testcase2) // [1, 3]

var testcase3 = solution.twoSum([-1, 0], -1)
print(testcase3) // [1, 2]