educative.io

How sliding window approach is different from two pointers approach

Courses
,
#1

How sliding window approach is different from two pointers approach.

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5440275650445312

#2

Hello @Avinash_Kumar_Singh,

The two-pointer method helps 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 by utilizing extra pointers to avoid repetitive operations—mainly used on sorted array/list.
Suppose we want to find a pair of 2 elements equal to the number n in a sorted array. We will use two pointer method.
On the other hand, we want to find the two contiguous elements equal to the number n in an array. We will use the sliding window approach.

#3

thanks man

#4

Did some more research and found

  1. Two pointers is really an easy and effective technique that is typically used for searching pairs in a sorted array.

  2. This technique shows how a nested for loop in some problems can be converted to a single for loop to reduce the time complexity.

  3. Common patterns in 2 pointers
    3.1 Two pointers starting from start and end until they meet.
    3.2 Two pointers moving at a different speed.

  4. A sliding window is a sublist or subarray that runs over an underlying data structure. The data structure is iterable and ordered, such as an array or a string. At a high level, you can think of it as a subset of the two pointers method. It normally encompasses searching for the longest, shortest, or optimal sequence that satisfies a given condition.

  5. When to use sliding pattern
    To identify problems where a sliding window can be helpful, look for a few properties:

  • Whenever you need to calculate running average
  • If you want to formulate a set of adjacent pairs
  • The problem involves an ordered data structure
  • If you need to identify a target value in an array
  • If you need to identify a longest, shortest, or most optimal sequence that satisfies a given condition in a collection
  1. A sliding window uses two pointers; the difference is that the window includes all elements in between those two pointers to some effect.
    For example, sliding window problems might involve contiguous values:
  • Min/max Sub array with target sum
  • Substring problems
  • Two pointer problems doesn’t necessarily care about the elements between those pointers:
  • Removing duplicates
  • Pair with target sum
3 Likes