This question is just as one would expect it. The first thought you get to solve it will probably be the right one.
For each element arr[i], we search for arr[i] + k in the array, and whenever it is found, we increment a counter variable.
But the twist here is that arr.index() is linear search, and is an O(n) function. Since we are putting this in a loop, the naive O(n2) solution gives a TLE.
Enter the bisect package. To use it we have to add this line at the top of our code:
What does this do? Gives us binary search out of the box.
The bisect package contains 2 particularly useful functions:
bisect_left(array, element) returns the index of leftmost occurrence element in array.
bisect_right(array, element) returns the index of rightmost occurrence element in array.
Binary search is an O(logn) algorithm. Therefore our solution is O(nlogn) and it now passes all the testcases.
Note that the array must be sorted in order for binary search to work. So before calling bisect_left, we must sort the array.
For each element arr[i], we search for arr[i] + k in the array, and whenever it is found, we increment a counter variable.
But the twist here is that arr.index() is linear search, and is an O(n) function. Since we are putting this in a loop, the naive O(n2) solution gives a TLE.
Enter the bisect package. To use it we have to add this line at the top of our code:
from bisect import bisect_left
What does this do? Gives us binary search out of the box.
The bisect package contains 2 particularly useful functions:
bisect_left(array, element) returns the index of leftmost occurrence element in array.
bisect_right(array, element) returns the index of rightmost occurrence element in array.
Binary search is an O(logn) algorithm. Therefore our solution is O(nlogn) and it now passes all the testcases.
Note that the array must be sorted in order for binary search to work. So before calling bisect_left, we must sort the array.
No comments:
Post a Comment