3. Two pointers Flashcards
What is the two-pointer technique?
This technique refers to using two pointers that start at opposite ends of an array and gradually move towards each other.
What is the time complexity of the naive approach to the Two Sum problem?
O(n^2)
What is the key to eliminating pairs in the two-pointer technique?
Understanding why we are able to eliminate pairs is key to understanding the two-pointer technique.
What does the two-pointer technique leverage to improve efficiency?
The fact that the input array is sorted.
In the example of nums = [1, 3, 4, 6, 8, 10, 13] and target = 13, what is the first sum calculated?
14
Why do we move the right pointer back when the sum is too large?
To get a smaller number, which might bring the sum closer to the target.
What do we do when the sum is too small?
Move the left pointer right to get a larger number, which might bring the sum closer to the target.
What is the time complexity reduction achieved by the two-pointer technique?
From O(n^2) down to O(n)
What do the two pointers represent in the two-pointer technique?
The pair of numbers we are currently considering.
What do we repeatedly compare in the two-pointer technique?
The sum of the current pair to the target.
When should you consider using the two-pointer technique?
For questions that involve searching for a pair (or more) of items in an array that meet a certain criteria.
Fill in the blank: The two-pointer technique is useful for finding a pair of items that sum to a given _______.
[target]
Fill in the blank: The two-pointer technique can also be used to find a triplet of items that sum to _______ in a given array.
[0]
True or False: The two-pointer technique can be applied to find the maximum amount of water that can be held between two array items representing wall heights.
True
