Leetcode 167. Two Sum II – Input array is sorted

Link to the Problem

Two Sum II – Input array is sorted

Thought Process

The array is sorted. What is the maximum possible sum of any two numbers from the array? It is sum of highest 2 numbers. Similarly, minimum sum is sum of lowest 2 numbers. Target is going to be somewhere in between these two numbers. What if we start in the middle? We can pick one number from the beginning and one from the last. We can increment or decrement the index depending on the current sum and the target sum. This is the idea behind this “Two Pointers” approach.

Fairly detailed explanation in the video that I have made.

Two Sum Two Pointers Solution Explained

Two Sum

Code

	// Video Explanation: https://youtu.be/i2y6LTIz_WU
	class Solution {
	public:
	vector<int> twoSum(vector<int>& numbers, int target) {
	int n = numbers.size();
	int left = 0; // Smallest number.
	int right = n-1; // Largest number.
	while (numbers[left] + numbers[right] != target) {
	if (numbers[left] + numbers[right] < target) { // Current sum is not sufficient
	// to reach the target.
	left++; // Increase the smaller number.
	} else { // Current sum exceeds the target.
	right--; // Decrease the larger number.
	}
	}
	return {left+1, right+1}; // Yay, solved.
	}
	};
	// Time Complexity: O(n).
	// Space Complexity: O(1).

view raw Leetcode_167.cpp hosted with ❤ by GitHub

Is there anything that is still unclear? Let me know in the comments and I can elaborate further.

Don’t forget like & share the post, and subscribe to the blog as well as the Youtube channel to get notifications whenever solution to a new problem is added.

Happy Coding!

---

---

Related Posts