CSES Problem Set
I like to do CSES sometimes. Here's a (probably incomplete) list of whatever I solved — the Sorting and Searching section is fully up to date.
Equivalently, you can browse the solutions directly in the cses-sols repository on GitHub.
Apartments
Sort both arrays, then two-pointer sweep matching each applicant to the closest apartment within tolerance k.
Array Division
Binary search on the maximum subarray sum, greedily checking whether that limit needs at most k subarrays.
Building Roads
Solution implementation
Building Teams
Solution implementation
Collecting Numbers
Single pass over the positions array, counting how often the next number appears before the current one.
Collecting Numbers II
Maintain the round count from Collecting Numbers and update it incrementally after each swap by rechecking only the neighborhoods of the two swapped values.
Concert Tickets
Keep ticket prices in a multiset and use upper_bound to find the most expensive ticket within each customer’s budget.
Counting Rooms
Solution implementation
Course Schedule
Solution implementation
Dice Combinations
Solution implementation
Distinct Numbers
Insert every value into a map and read off the number of distinct keys.
Distinct Values Subarrays
Sliding window tracking the most recent duplicate position, counting subarrays ending at i with all distinct values.
Distinct Values Subarrays II
Sliding window capped at k distinct values, growing and shrinking the window while summing valid subarray lengths.
Distinct Values Subsequences
Count value frequencies, then multiply (count + 1) across all values and subtract 1 for the empty subsequence.
Dynamic Range Minimum Queries
Solution implementation
Dynamic Range Sum Queries
Solution implementation
Edit Distance
Solution implementation
Factory Machines
Binary search on time, checking whether all machines together can produce enough units by that time.
Ferris Wheel
Two-pointer greedy: try to pair the lightest remaining person with the heaviest, otherwise seat the heaviest alone.
Flight Discount
Solution implementation
Flight Routes
Solution implementation
Game Routes
Solution implementation
High Score
Solution implementation
Josephus Problem I
Simulate directly with an ordered set of survivors, walking k steps forward before each elimination.
Josephus Problem II
Binary search over a segment tree of alive positions to jump straight to the k-th surviving person after each elimination.
Longest Flight Route
Solution implementation
Maximum Subarray Sum
Kadane's algorithm: extend the running sum while it helps, and reset once it turns negative.
Maximum Subarray Sum II
Prefix sums plus a sliding multiset of window-start prefix sums to bound the subarray length between a and b.
Message Route
Solution implementation
Minimizing Coins
Solution implementation
Missing Coin Sum
Sort the coins and greedily extend the reachable prefix sum, stopping at the first gap.
Monsters
Solution implementation
Movie Festival
Greedy interval scheduling: sort by end time and take a movie whenever it starts after the last one ends.
Movie Festival II
Greedy interval scheduling generalized to k halls, tracked as a multiset of k free end times.
Nearest Smaller Values
Coordinate-compress the values and query a segment tree for the most recent earlier index holding a smaller value.
Nested Ranges Check
Sort ranges by (start, -end) and sweep once forward and once backward to mark containment.
Nested Ranges Count
Compress coordinates and sweep with a Fenwick-style segment tree to count containing and contained ranges.
Playlist
Sliding window keeping the last-seen position of every song, shrinking the window whenever a repeat appears.
Reading Books
Sum all reading times, but double the longest book’s time if it alone exceeds the rest combined (parallel reading).
Restaurant Customers
Sort arrivals and departures separately, binary searching departures to count customers still present at each arrival.
Room Allocation
Sweep arrival/departure events in time order, assigning the smallest currently free room number.
Round Trip
Solution implementation
Shortest Routes I
Solution implementation
Shortest Routes II
Solution implementation
Static Range Minimum Queries
Solution implementation
Static Range Sum Queries
Solution implementation
Stick Lengths
Sort the sticks and align every stick to the median, which minimizes total absolute distance.
Subarray Divisibility
Prefix sums modulo n, counting subarrays with remainder 0 via combinatorics on matching remainders.
Subarray Sums I
Prefix sums with a hashmap of counts to find subarrays summing to a fixed target.
Subarray Sums II
Same prefix-sum-and-hashmap approach as Subarray Sums I, extended to arrays with negative values.
Sum of Four Values
Fix the first two values, then two-pointer over the sorted remainder to complete the target sum.
Sum of Three Values
Fix the first value, then two-pointer over the sorted remainder to complete the target sum.
Sum of Two Values
Hashmap of value positions to find a complementary pair in one pass.
Tasks and Deadlines
Greedy: sort tasks by duration and process the shortest first to maximize total points from finish times.
Towers
Patience-sorting greedy: place each cube on the smallest existing tower it still fits on, else start a new tower.
Traffic Lights
Maintain a multiset of light positions and a parallel multiset of gap lengths, updating both as each new light is added.
Weird Algorithm
Simple simulation following the algorithm rules