NUHMAN.com

Introduction

LeetCode 167 requires finding two numbers from a sorted array that sum up to a specific target. This problem is a variant of the classic Two Sum problem, but with the additional constraint that the input array is sorted in non-decreasing order.

Problem Statement

Given a 1-indexed array of integers numbers sorted in non-decreasing order, find two numbers such that they add up to a specific target. Return the indices of the two numbers (1-based index).

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

Function Signature:

go

func twoSum(numbers []int, target int) []int

• Input:
• numbers: A slice of integers numbers where the elements are sorted in non-decreasing order.
• target: An integer target that represents the sum we are looking for.
• Output:
• A slice of two integers [index1, index2] where:
• 1 <= index1 < index2 <= numbers.length
• numbers[index1 - 1] + numbers[index2 - 1] == target

Approach

Given that the array is sorted, we can efficiently use a two-pointer approach to solve the problem.

Steps:

1. Initialize Two Pointers:

• One pointer (left) starts at the beginning of the array.
• The other pointer (right) starts at the end of the array.

1. Iterate to Find the Target Sum:

• Check the sum of the elements at the left and right pointers.
• If the sum equals the target, return the 1-based indices of these two elements.
• If the sum is less than the target, increment the left pointer to increase the sum.
• If the sum is greater than the target, decrement the right pointer to decrease the sum.

1. Stop When the Pointers Meet:

• Since the array is sorted, the two pointers will eventually meet or cross each other. At that point, the solution will have been found.

Time Complexity:

• O(n), where n is the number of elements in the array. We are iterating through the array once with two pointers.

Space Complexity:

• O(1), since we only use two pointers and no additional data structures.

Go Implementation

go

func twoSum(numbers []int, target int) []int {
    left, right := 0, len(numbers)-1
    
    for left < right {
        sum := numbers[left] + numbers[right]
        
        if sum == target {
            return []int{left + 1, right + 1} // Return 1-based indices
        } else if sum < target {
            left++ // Move the left pointer to the right to increase the sum
        } else {
            right-- // Move the right pointer to the left to decrease the sum
        }
    }
    
    return nil // In case no solution is found, although the problem guarantees one solution
}

Explanation of the Code:

1. Initializing Pointers:

• We start with left at index 0 (first element) and right at the last index (len(numbers)-1).

2. Two-pointer Approach:

• We calculate the sum of the elements at the left and right pointers.
• If the sum equals the target, we return the 1-based indices of these elements.
• If the sum is less than the target, we need a larger sum, so we increment the left pointer to the right.
• If the sum is greater than the target, we need a smaller sum, so we decrement the right pointer to the left.

3. Return 1-based Indices:

• Since the problem specifies 1-based indices, we return left+1 and right+1 instead of the 0-based indices.

4. Edge Case:

• If no solution is found (though the problem guarantees exactly one solution), we return nil.

Example

Example 1:

go

numbers := []int{2, 7, 11, 15}
target := 9
result := twoSum(numbers, target)
fmt.Println(result) // Output: [1, 2]

Explanation:

• The two numbers that sum up to 9 are 2 and 7, and their 1-based indices are 1 and 2.

Example 2:

go

numbers := []int{1, 2, 3, 4, 5}
target := 6
result := twoSum(numbers, target)
fmt.Println(result) // Output: [1, 5]

Explanation:

• The two numbers that sum up to 6 are 1 and 5, and their 1-based indices are 1 and 5.

Example 3:

go

numbers := []int{1, 2, 3, 4, 5, 6}
target := 8
result := twoSum(numbers, target)
fmt.Println(result) // Output: [2, 5]

Explanation:

• The two numbers that sum up to 8 are 2 and 6, and their 1-based indices are 2 and 5.

Conclusion

LeetCode 167: Two Sum II - Input Array is Sorted can be solved efficiently using the two-pointer approach. By leveraging the sorted property of the array, we can reduce the time complexity to O(n), making it an optimal solution for this problem. The solution is concise, and the algorithm operates with constant space, making it very efficient.