grid47 Exploring patterns and algorithms
Oct 21, 2024
5 min read
Solution to LeetCode 167: Two Sum II - Input Array Is Sorted Problem
Given a sorted array of integers, find two numbers whose sum equals a target value. Return the indices of these two numbers, ensuring they are 1-indexed.
Problem
Approach
Steps
Complexity
Input: The input consists of a sorted array `numbers` of integers and a `target` integer.
Example: numbers = [1, 5, 8, 12], target = 13
Constraints:
• 2 <= numbers.length <= 30,000
• -1,000 <= numbers[i] <= 1,000
• The array is sorted in non-decreasing order.
• -1,000 <= target <= 1,000
Output: Return an array of two integers representing the 1-indexed positions of the two numbers that add up to the target.
Example: Output: [2, 3]
Constraints:
• The output array contains exactly two integers.
Goal: The goal is to find two indices such that the sum of the numbers at those indices equals the target.
Steps:
• Use a two-pointer approach to iterate through the array.
• Start with pointers at the beginning and end of the array.
• Move the pointers towards each other based on whether the sum is less than or greater than the target.
Goal: The constraints ensure the problem has a manageable input size, and there is exactly one solution.
Steps:
• The length of the array is between 2 and 30,000.
• There will always be exactly one solution.
Assumptions:
• The array is already sorted in non-decreasing order.
• There is exactly one valid solution.
• Input: numbers = [1, 5, 8, 12], target = 13
• Explanation: The sum of 5 and 8 equals 13, so the solution is at indices 2 and 3.
Approach: We will use a two-pointer approach to efficiently find the solution in O(n) time.
Observations:
• The array is sorted, so we can use the two-pointer technique to find the pair.
• We will initialize two pointers: one at the beginning and one at the end of the array, and move them based on the current sum.
Steps:
• Initialize two pointers: left at the beginning (index 1) and right at the end (last index).
• Check the sum of the values at these pointers.
• If the sum is equal to the target, return the indices.
• If the sum is less than the target, move the left pointer to the right.
• If the sum is greater than the target, move the right pointer to the left.
Empty Inputs:
• The problem guarantees that the array will always have at least two elements.
Large Inputs:
• For large arrays, the solution is efficient with O(n) time complexity.
Special Values:
• If the target is negative, the same approach works.
Constraints:
• Since the array is sorted and there's exactly one solution, the two-pointer approach is optimal.
vector<int> twoSum(vector<int>& nums, int target) {
Define the function 'twoSum' which takes a vector of integers 'nums' and an integer 'target', and returns a vector of two indices whose sum equals the target.
2 : Variable Initialization
vector<int> ans(2, 0);
Initialize a vector 'ans' with two elements, both set to 0, which will store the indices of the two numbers that sum to the target.
3 : Map Declaration
map<int, int> mp;
Declare a map 'mp' to store the complement (target - nums[i]) as the key, and the index of the number as the value.
4 : For Loop
for(int i =0; i < nums.size(); i++) {
Start a loop to iterate through each element of the input vector 'nums'.
5 : Condition Check
if(mp.count(nums[i])) {
Check if the current number 'nums[i]' exists in the map 'mp'. If it does, the two sum condition is met.
6 : Index Assignment
ans[0] = mp[nums[i]] +1;
If the condition is true, assign the index of the first number (found in the map) to 'ans[0]'. Add 1 to make the index 1-based.
7 : Index Assignment
ans[1] = i +1;
Assign the current index 'i' to 'ans[1]' (adding 1 to make it 1-based) as the second index of the two numbers whose sum equals the target.
8 : Return Statement
return ans;
Return the result vector 'ans' containing the indices of the two numbers that sum to the target.
9 : Else Condition
} else {
If the current number is not in the map, proceed to store its complement (target - nums[i]) in the map.
10 : Map Insertion
mp[target - nums[i]] = i;
Store the complement of the current number (target - nums[i]) as the key and its index 'i' as the value in the map 'mp'.
11 : Return Statement
return ans;
Return the 'ans' vector, which will contain the indices of the two numbers whose sum equals the target, if they are found.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we only need to iterate through the array once.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) as we are using only constant extra space.
