Algorithm-I, Day 2-6
Ch'i YU Lv3
  2022-03-08 21:23:30 2022-03-08 21:23      2 Mins  

Topic: Two Pointers with Sliding Window

Q977 Squares of a Sorted Array

Q189 Rotate Array

Q283 Move Zeroes

Q167 Two Sum

Q344 Reverse String

Q557 Reverse Words in a String III

Q876 Middle of the Linked List

Q19 Remove Nth Node From End of List

Q3 Longest Substring Without Repeating Characters

Q567 Permutation in String

A searching algorithm which finds a pair of element's position in a sequential(sorted) array.

e.g. Given a enumerable array Grid (maybe sorted in some order), having finite integers, Two-Pointers method can find if there exists any pair of elements (Grid[i], Grid[j]) such that suits some given target.

Note: This pair of elements can also represents a sequence of items of an array, which starts at item No. i and stops at item No. j.

Pre&Post / Sliding Window Method
1
2
3
4
5
6
7
8
9
10
11
12
## Ensure that pointer H(High) is kinda ahead of the pointer L(Low).
## Hence, the pointers L & H spans a window.

while H < Border: 
    Window.push(H)		## Expand the Window
    H++;
    while valid Window:
		update Window if necessary
        Window.pop(L)	 ## Shrink the Window
        L++

return Window
Left&Right Method
1
2
3
4
5
6
7
8
9
10
11
12
13
## Do until the pointers L(Left) and R(Right) meet each other,
## Or do until the target pair is found.
    if Target == Grid[L] + Grid[R]
        return L, R
    else if Target > Grid[L] + Grid[R]
        R -= 1
    else ## Target < Grid[L] + Grid[R]
    	L += 1
	
    continue
## Note: 
## The explanation above implicitly assume that
## the array Grid is sorted ascendingly.
Time Complexities
  • Best Case Complexity: O(1)
  • Worst Case Complexity: O(n)
  • Average Case Complexity: O(n)
Space Complexities
  • O(1)
Footnote

In Q977 Squares of a Sorted Array:

Left&Right Method is applied. Take The absolute value for comparison.

In Q189 Rotate Array:

See also in: < Article Not Published Yet >

In Q283 Move Zeroes:

Left&Right Method is applied. One Pointer stands for the current working position, and another stands for the staing point of pushing in / filling with zeros.

In Q167 Two Sum:

Left&Right Method is applied.

Note: The given input array is sorted.

In Q344 Reverse String:

Left&Right Method is applied.

In Q557 Reverse Words in a String III:

Left&Right Method is applied. Just make wise usage of slicers.

In Q876 Middle of the Linked List:

Pre&Post / Sliding Window Method is recommended.

1
2
Pre += 1
Post += 2

In Q19 Remove Nth Node From End of List:

Left&Right Method is applied.

Repeat the "process" for N times, then remove the node.

In Q3 Longest Substring Without Repeating Characters:

Pre&Post / Sliding Window Method is applied.

In Q567 Permutation in String:

Note: It's much faster to create 2 dictionarys and compare them instead.