Two Sum II - Input Array Is Sorted

Medium

Zomato

0 views

Topics:

ArraysTwo PointersBinary Search

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[index₁] and numbers[index₂] where 1 <= index₁ < index₂ <= numbers.length.

Return the indices of the two numbers, index₁ and index₂, added by one as an integer array [index₁, index₂] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index₁ = 1, index₂ = 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 index₁ = 1, index₂ = 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 index₁ = 1, index₂ = 2. We return [1, 2].

Constraints:

2 <= numbers.length <= 3 * 10⁴
-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.

Try coding it in LeetCode

Two Sum II - Input Array Is Sorted

Medium

Zomato

0 views

Topics:

ArraysTwo PointersBinary Search

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[index₁] and numbers[index₂] where 1 <= index₁ < index₂ <= numbers.length.

Return the indices of the two numbers, index₁ and index₂, added by one as an integer array [index₁, index₂] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index₁ = 1, index₂ = 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 index₁ = 1, index₂ = 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 index₁ = 1, index₂ = 2. We return [1, 2].

Constraints:

2 <= numbers.length <= 3 * 10⁴
-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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array `numbers` contain negative numbers, zeros, or duplicate values?
What should I return if no two numbers add up to the `target`? Should I return null, an empty array, or throw an exception?
The problem states the array is sorted. Is it sorted in ascending or descending order?
Are the indices I return 0-based or 1-based?
If there are multiple pairs that sum up to the target, is it acceptable to return any one of them, or is there a specific pair I need to return (e.g., the pair with the smallest indices)?

Brute Force Solution

Approach

The brute force approach to this problem is like trying every possible pair of numbers to see if they add up to the target. It is a very direct, but potentially slow, way to find the solution. We simply check every combination until we find the right one.

Here's how the algorithm would work step-by-step:

Take the very first number from the list.
Add it to every other number in the list, one at a time.
Each time you add them, check if the result is equal to the target number.
If you find a pair that adds up to the target, you're done!
If not, move to the second number in the original list.
Now, add that second number to every number that comes *after* it in the list (you don't need to re-check combinations you already tried).
Again, check if any of these sums equal the target. If so, you're done!
Continue this process, taking each number in the list and adding it to all the subsequent numbers, until you either find a matching pair or you've exhausted all possible combinations.

Code Implementation

def two_sum_brute_force(numbers, target):
    # Iterate through each number in the list.
    for first_index in range(len(numbers)):
        # For each number, iterate through all subsequent numbers.
        for second_index in range(first_index + 1, len(numbers)):
            # Check if the sum of current pair equals the target.
            if numbers[first_index] + numbers[second_index] == target:
                return [first_index + 1, second_index + 1]

    # Return an empty list to indicate no solution was found.
    return []

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach iterates through the input array of size n. For each element, it compares it with every subsequent element in the array to find a pair that sums to the target. In the worst case, for the first element, we might need to check n-1 other elements, for the second n-2 elements, and so on. Thus, the total number of comparisons can be approximated as n * (n-1) / 2. Simplifying this expression, we arrive at a time complexity of O(n²).

Space Complexity

O(1) – The provided brute force approach iterates through the input array but does not create any additional data structures that scale with the input size N. It only uses a fixed number of variables, such as those to store the two numbers being added or to track the current indices. Therefore, the auxiliary space used is constant, irrespective of the input array's length.

Optimal Solution

Approach

Since the numbers are already sorted, we can use this ordering to our advantage. We'll start by looking at the numbers at the beginning and the end and then carefully move inwards until we find the pair that adds up to our target.

Here's how the algorithm would work step-by-step:

Imagine two 'pointers', one at the very beginning of the list of numbers, and the other at the very end.
Add the two numbers that these pointers are pointing to.
If the sum is exactly what we're looking for, then we've found our pair and we're done!
If the sum is too small, it means we need to consider a larger number, so we move the pointer at the beginning forward to the next number.
If the sum is too big, it means we need to consider a smaller number, so we move the pointer at the end backward to the previous number.
Keep doing this, moving the pointers closer together, until you find the pair that adds up to the target, or the pointers cross each other (in which case, there's no solution).

Code Implementation

def find_two_sum(numbers, target):
    left_index = 0
    right_index = len(numbers) - 1

    while left_index < right_index:
        current_sum = numbers[left_index] + numbers[right_index]

        if current_sum == target:
            return [left_index + 1, right_index + 1]

        elif current_sum < target:
            # Sum is too small, need larger numbers
            left_index += 1

        else:
            # Sum is too large, need smaller numbers
            right_index -= 1

    # No such pair exists
    return []

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses two pointers, one starting at the beginning and the other at the end of the sorted array. In each iteration, we compare the sum of the numbers pointed to by these pointers with the target. Based on the comparison, we either find the solution, move the left pointer one step to the right, or move the right pointer one step to the left. Since the pointers move towards each other and each pointer can traverse at most n elements, the maximum number of iterations is proportional to n. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses only two pointers, one at the beginning and one at the end of the sorted array. These pointers are integer variables and require constant space. The space used by the algorithm does not grow with the input size N, where N is the number of elements in the input array. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Empty input array	Return an empty array or null to indicate no solution when the input array is empty.
Input array with fewer than 2 elements	Return an empty array or null since a pair cannot be formed with less than two numbers.
No solution exists (no two numbers sum to the target)	Return an empty array or null to signal that no such pair exists in the input.
Large input array that could cause performance issues	Two-pointer approach offers O(n) time complexity, ensuring good performance for large inputs.
Input array contains duplicate numbers and a valid solution exists using duplicates	The two-pointer approach will correctly identify the indices of the duplicate numbers that sum to the target.
Input array contains negative numbers	The two-pointer approach works correctly with negative numbers since the array is sorted.
The target value is very large and might cause integer overflow during addition	Use a language construct to prevent integer overflow, like casting to a larger numeric type if necessary or checking before adding.
Multiple valid solutions exist	Return the first valid solution encountered; the problem statement doesn't require finding all solutions.