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
Leetcode 1. Two Sum - Diagram to assist visualization, Problem Solving, Leetcode, Leetcode Solutions, Crack Coding Interview, Coding Interview, Data Structures and Algorithms
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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s