algoadvance

Leetcode 167. Two Sum II

Problem Statement

You are given a 0-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 0 <= index1 < index2 < numbers.length.

Return the indices of the two numbers, index1 and index2 (both 1-indexed), as an integer array [index1, index2] of length 2.

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

Example:

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2.

Constraints:

• 2 <= numbers.length <= 3 * 10^4
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

Clarifying Questions

1. Are all elements in the array unique? No, the array can contain duplicate elements.

2. Can the target sum be a negative number? Yes, the target can be negative as well.

3. Do we need to consider integer overflow? Typically not necessary for this problem given the constraints.

Strategy

Given that the array is sorted, we can use the two-pointer technique to solve this problem efficiently:

1. Initialization: Start with two pointers, one at the beginning (left = 0) and one at the end (right = numbers.size() - 1) of the array.
2. Iteration:
   • Calculate the sum of the elements at the two pointers.
   • If the sum is equal to the target, return the positions of the two pointers shifted by 1 (to convert from 0-indexed to 1-indexed).
   • If the sum is less than the target, increment the left pointer to increase the sum.
   • If the sum is more than the target, decrement the right pointer to decrease the sum.

This approach ensures we find the solution in linear time because we traverse the array at most once.

Code

#include <vector>

std::vector<int> twoSum(std::vector<int>& numbers, int target) {
    int left = 0;
    int right = numbers.size() - 1;
    
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return {left + 1, right + 1};  // 1-indexed positions
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    
    // The problem statement guarantees exactly one solution,
    // so we should never reach here.
    return {};
}

Time Complexity

• Time Complexity: O(n). We traverse the array at most once with the two pointers.
• Space Complexity: O(1). We use only a constant amount of extra space.

This ensures the solution is both time efficient and space efficient.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?