| |
Key Ideas |
Example Problems |
Additional problems |
| Topic 0: Introduction |
- Know how to perform input/output efficiently in your language.
- Understand overflow
-
Topic 0 Problem Set
|
|
|
Topic 1:
Sums, Prefix Sums, and Difference Arrays |
- Sum and
prefix sums:
For many problems where data is stored in an 1D-array, computing the sum or prefix (or postfix) sums can reduce the complexity from O(n^2) to O(n).
- For some problems, it is necessary to store these sums in another array, requiring O(n) extra memory.
For other problems, maintaining a running sum suffices. Some problems requires storing information other than sum of prefix.
- Difference array: With range updates (changing array A's elements in an range by a constant value), maintaining the array where each element represents difference of two adjacent elements in A makes each update constant time. Some discrete event simulation can be viewed as range updates along the time dimension. Difference array to prefix-sum array is differentiation to integration in calculus.
-
Topic 1 Problem Set
|
|
|
Topic 2:
Histograms, Sets, and Maps |
- Histogram: A histogram counts the number of times a value appears. When the values we want to count are integers in a small range, the histogram can be stored using an array. When the values are in a bigger range, we can use Map to store them.
- Set: A set an important data structure, it supports efficient addition / removal, while maintaining uniqueness of elements. An ordered set also enable finding the first / last element.
- Map: A map stores mappings from keys to values. It can be viewed as more powerful arrays. While arrays map integer indices to values, maps can map anything to values.
-
Topic 2 Problem Set
|
|
|
Topic 3:
Introduction to Dynamic Programming |
- Dynamic Programming:
Solving problems using recursion (using solutions to subproblems) and storing solutions of subproblems to avoid recomputation.
Key is to figure out the recursion relationship.
Sometimes need to define subproblems with more inputs.
-
Topic 3 Problem Set
|
|
|
Topic 4:
Two Pointers and Sliding Window |
- Two pointers:
One maintains two pointers (indices) into either one array or two arrays, and move the pointers based on
values at the pointers.
- Sliding window: A window slides through an array (both ends of the window move along one direction).
One maintains a summary of what are in the window, and decides how to slide based
on that summary.
-
Topic 4 Problem Set
|
|
|
Topic 5:
Binary Search and Bisection |
- Binary Search can be used to efficiently search sorted lists.
- Keep a low and high value for the range that the target value could possibly be in.
- There are multiple ways to write code for binary search that work.
- Bisection is a variant of binary search that solves a monotonic function.
-
Topic 5 Problem Set
|
|
|
Topic 6:
Stacks |
- A stack is a simple data structure that allows push(), pop() and top()
- Elements are always accessed from the top of the stack, so FILO (first in, last out)
- Used implicitly for implementing function calls, and can be explicitly used for many tasks.
- Useful to remember and undo operations
- Useful to process balanced bracket sequences
- Useful to evaluate expressions, especially Reverse Polish Notation.
-
Topic 6 Problem Set
|
|
LeetCode: Minimum Add to Make Parentheses Valid
LeetCode: Score of Parentheses
LeetCode: Valid Parentheses (Req, Stack)
LeetCode: Baseball Game (Req, Stack)
LeetCode: Asteroid Collision (Req, Stack)
LeetCode: Valid Parenthesis String
Kattis: Even Up Solitaire (2013 ICPC North American Qualifier)
Kattis: Pairing Socks
Kattis: Working at the Restaurant
Kattis: Game of Throwns
|
| Topic 7: Queues, Deques, and Priority Queues |
- Queues are a data structure that allows insertion from one end and removal from the other.
- Most of the time, problems that can be solved with queues can also be solved with a sliding window.
- (We will talk about another method that uses queues, breadth-first search, in Topic 9.)
- Deques are data structures that allow insertion and deletion from both sides.
- Priority queues are data structures that allow for efficient removal of a "highest-priority" element.
- In Java and Python (with heapq), priority queues remove the smallest priority first, while in C++, they remove the largest priority first.
- An easy way to sort a priority queue in the opposite direction is to multiply all priorities by -1.
-
Topic 7 problem set
|
|
|
| Topic 8: DFS |
- Depth First Search (DFS) is a general technique to solve lots of problems.
- Use recursion, but mark cells as visited to prevent an infinite loop.
-
Topic 8 problem set
|
|
|
| Topic 9: BFS |
- Breadth-first search is a pathfinding method that searches in all possible directions at the same rate.
- It can be seen as opposite to depth-first search, which explores down a single direction as far as possible before backtracking.
- BFS can also be seen as a general-problem solving technique.
-
Topic 9 problem set
|
|
|
| Topic 10: Graphs |
- A graph is a collection of vertices and edges (connections between vertices).
- Different graph representations (adjacency list and adjacency matrix) have a trade-off: adjacency list is more compact, but adjacency matrix can check if an edge exists in constant time.
- Graph traversals (DFS and BFS) can be applied to all graphs, just as we applied it to specific cases in the previous topics.
- Graph traversals can solve a wide range of problems.
-
Topic 10 problem set
|
|
|