Sliding window / Two pointers
When working with arrays, the sliding window is a popular technique for efficiently solving problems with just two-pointers. The main idea behind the sliding window technique is to have a left and a right pointer and to slide those in the correct direction when appropriate.
Imagine we’re trying to find a perfect range (subarray) in an array and we slide the right pointer as much as possible, then we adjust the left one by moving it closer to the right one. Then we move the right one again as much as possible, and then we adjust the left one again. We repeat this process until finding the best range possible and this technique is called the sliding window.
Challenge - Find two numbers that sum up to k
Given a sorted array of
n numbers and a target value of k, you are asked to find two numbers from that array that would sum up to k. Note that the values in the array are sorted in increasing order. You’re not allowed to use dictionaries, maps, hashmaps, etc.Input
The first line of the input contains two integers -
n the number of elements in the array (1 ≤ n ≤ ) and the number k . The following line contains n integers separated by a space, that represent the elements of the array in increasing order. Output
The program should print two integers from the array that sum up to
k. The first integer should be the smallest possible. In case it’s not possible to find such two numbers, the program should print Impossible.Examples
Input | Output |
5 11
-2 3 4 8 9 | 3 8 |
5 1000
-2 3 4 8 9 | Impossible |
Tutorial
As the array is sorted in increasing order, we can start with two pointers pointing to the beginning of the array and to the very end of it and adjust them depending on their sum.
In case the sum of those two is larger than
k, we can decrease the right pointer. In case the sum is smaller than k, we can increase the left pointer. Finally, in case the sum is exactly k, we can print those elements and stop the program.n, k = ... # Initialize n and k
a = ... # Initialize the array (it's in increasing order)
l, r = 0, len(a) - 1 # Initialize the left and right pointers
while l < r: # While l and r are different
if a[l] + a[r] > k: # If the sum is greater => decrease it by moving r
r -= 1
elif a[l] + a[r] < k: # If the sum is smaller => increase it by moving l
l += 1
else: # a[l] + a[r] == k => stop the program
print(a[l], a[r])
break
else: # while...else = no-break -> we didn't find anything
print('Impossible')“Two-pointers” is a generic method that can be applied in different scenarios. The main idea is to pick the initial starting positions for the left and the right pointers (which might be very different from problem to problem), and the rule of how to update the pointer positions (this can also be very different from problem to problem).
In this scenario, we picked the left to be at the beginning of the array and the right to be at the very end. Yet, in another problem, we might need to set the right pointer to be at the beginning of the array as well. In some different scenarios, we might set the left pointer to the very end of the array and slide those two to the start.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB