Intro

Arrays are the most fundamental data structure. Every other data structure either uses arrays internally or exists to address their limitations.

In this section, I'll teach you four techniques that transform how you think about array problems. Prefix sums let you answer range queries in $O(1)$.

Difference arrays let you perform range updates in $O(1)$. Two pointers reduce $O(n^2)$ searches to $O(n)$. Sliding window solves subarray problems without nested loops. By the end of this section, you'll solve array problems in $O(n)$ that others solve in $O(n^2)$.