
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 1Darray, 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 prefixsum 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, breadthfirst 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 "highestpriority" 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 
 Breadthfirst search is a pathfinding method that searches in all possible directions at the same rate.
 It can be seen as opposite to depthfirst search, which explores down a single direction as far as possible before backtracking.
 BFS can also be seen as a generalproblem 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 tradeoff: 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


