Chapter 1. Array and String

Chapter 1. Array and String#

Two Pointer#

Two types of pointers are usually used for arrays.

  • slow and fast pointer

  • left and right pointer

For all the two pointer related algorithm, we can refer to

Fast and Slow Pointer#

Fast and slow pointer can be used to modify the array in-place.

Leetcode

  • Remove duplicates

  • Remove given values

Sliding Window#

Sliding window is a type of left and right pointer. This technique is very efficient to solve substring or subsequence problem.

left, right = 0, 0
while right < len(s):
    # enlarge window
    window.add(s[right])
    right += 1

    # shrink window
    while (window needs shrink):
        window.remove(s[left])
        left -= 1

Leetcode

Left and Right Pointer#

Presum Technique#

Presum is typically used when frequent summation is required. More space for less time.

LeetCode

Diff Array#

Diff array is usually used when frequent modifications of an array given index range.

Leetcode

Traverse 2-D Matrix#

Rotate Matrix#

Leetcode

Spiral Traverse#

Leetcode

Contents