Menu
I was wondering about the significant difference between 'sliding window' and 'two pointer' problem.
It is giving me a hard time to differentiate between the two.
602
Edit PagePage History. The two pointer method is a helpful technique to keep in mind when working with strings and arrays. It's a clever optimization that can help reduce time complexity with no added space complexity (a win-win!)
Two pointers is really an easy and effective technique that is typically used for searching pairs in a sorted array. Given a sorted array A (sorted in ascending order), having N integers, find if there exists any pair of elements (A[i], A[j]) such that their sum is equal to X.
Introduction. The Sliding window is a problem-solving technique of data structure and algorithm for problems that apply arrays or lists. These problems are painless to solve using a brute force approach in O(n²) or O(n³). However, the Sliding window technique can reduce the time complexity to O(n).
Sliding window algorithms can be implemented with a single pointer and a variable for window size. Typically we use all of the elements within the window for the problem (for eg - sum of all elements in the window).
Two pointer technique is quite similar but we usually compare the value at the two pointers instead of all the elements between the pointers.
Two pointers can also have variations like fast-slow pointer.
Hope it answers your question.
156
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
