Skip to content
Tutorials Center
My learning

Topics

Lesson 55 of 63 ยท Practice and Review

CSES Sorting and Searching Walkthrough

Original walkthrough of the CSES Sorting and Searching problems: two pointers, interval greedy, binary search, prefix-sum counting and reverse-time tricks, tested in Python.

The Sorting and Searching section of the CSES Problem Set is the best place to learn how far the sentence "sort first" can take you. Almost every problem in it becomes easy after one sort, one hash map, one binary search or one sweep. The section has about 35 problems; this lesson covers the ones that teach a distinct idea, and groups the remaining ones with their siblings.

As in the other walkthroughs, the statements are my own short paraphrases (find the originals on the CSES site), and every solution is original code that was run against a brute force on small random inputs. Try a problem yourself first. If the idea does not come, the hint is almost always a sorted order or a sliding pointer.

flowchart LR
    S["Sort the data"] --> TP["Two pointers: Apartments, Ferris Wheel, Sum of Three Values"]
    S --> GR["Greedy by one key: Movie Festival, Tasks and Deadlines, Missing Coin Sum"]
    S --> BS["Binary search or bisect: Towers, Factory Machines"]
    H["Hash map of prefix sums"] --> PS["Subarray Sums, Subarray Divisibility, Sum of Two Values"]
    T["Reverse time"] --> TL["Traffic Lights"]

Five tools cover most of this section.

Two pointers and greedy by a sort key

Apartments. Applicants state a desired size, flats have sizes, and a flat suits an applicant if the sizes differ by at most k. Maximize the number of matches. Sort both lists and walk with two pointers: if the flat is too small for the current applicant it is too small for all later (larger) applicants, so drop it; if it is too large, the current applicant has no chance with this or any later flat, so drop the applicant; otherwise match them. Each pointer moves forward only, so after sorting this is linear.

Ferris Wheel. Each gondola takes at most two children, with total weight at most x. Minimize gondolas. Sort, then pair the heaviest remaining child with the lightest. If they fit together, both ride; if not, the heaviest rides alone, because it cannot fit with anyone. Exchange argument: the heaviest child's best possible partner is the lightest one, so if even that fails, nobody works.

Movie Festival. Given movies as (start, end) intervals, watch as many as possible. Sort by end time and take every movie that starts after the last chosen one ended. Sorting by start time or by length is wrong; the earliest end leaves the most room, which is the standard interval-scheduling argument (see Greedy Algorithms and How to Trust Them).

Tasks and Deadlines. Tasks with a duration and a deadline are done one after another. The reward for a task is deadline - finish time, which may be negative. Maximize the total. The deadlines do not affect the order: the total reward is the sum of deadlines minus the sum of finish times, so you want to minimize the sum of finish times, which means shortest task first.

Stick Lengths. Change the sticks to a common length with minimum total change. The best target is the median, because moving the target by one changes the cost by the number of sticks on one side minus the number on the other.

Missing Coin Sum. Given coins, find the smallest positive sum you cannot form. Sort the coins and keep reach, meaning every sum from 0 to reach is possible. A next coin c extends this to reach + c if c <= reach + 1; if c is larger there is a gap at reach + 1 and that is the answer. This is induction in six lines.

Python Sorting and greedy problems with brute-force checks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Binary search, sliding windows and reverse time

Towers. Process cubes in order; each must go on top of a strictly larger cube or start a new tower. Minimize the number of towers. Keep the list of tower tops in sorted order; place each cube on the smallest top that is strictly larger than it (bisect_right), replacing that top. If none exists, start a tower. This is the same structure as the patience-sorting algorithm for a longest increasing subsequence. The number of towers equals the length of the longest non-decreasing subsequence, by Dilworth's theorem.

Playlist. The longest stretch of songs with no repeats. Slide a window; when a song repeats inside the window, move the left edge past its previous occurrence. Store the last index of each song in a dictionary. See Two Pointers and Sliding Windows.

Factory Machines. Machine i makes one product every t[i] seconds. What is the least time to make p products? Binary search on the answer: in T seconds the machines make sum(T // t[i]) products, which is monotonic in T. The upper bound is min(t) * p. See Binary Search on Answer.

Traffic Lights. A street of length x gets traffic lights one at a time at given positions; after each insertion, print the length of the longest lit-free stretch. Insertions split gaps, which is awkward; deletions merge gaps, which is easy. So process the insertions in reverse: start with all lights, store neighbors in a linked list (dictionaries prev, nxt), and remove one light at a time, which merges two gaps. The longest gap only grows as you go backwards, so one running maximum suffices. Read the recorded values in the original order. This reverse-time trick is a form of offline processing.

Python Towers, playlist, factory machines and traffic lights

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Prefix sums with a hash map

Sum of Two Values. Find two different positions whose values add up to x. One pass with a dictionary of earlier values: for each element look up x - value. Sum of Three Values is the same task for three positions: sort indices by value, fix the first, and run two pointers on the rest, O(n^2). A four-value version fixes two and uses a dictionary of pair sums, O(n^2) time and memory.

Subarray Sums II. Count subarrays whose sum is exactly x, with negative numbers allowed. A two-pointer window fails with negatives. Use prefix sums P: a subarray (l, r] has sum P[r] - P[l], so for each r count earlier prefixes equal to P[r] - x. Keep a counter of prefix values seen so far (and seed it with the empty prefix 0). See Prefix Sums and Difference Arrays.

Subarray Divisibility. Count subarrays whose sum is divisible by n. Two prefixes give a divisible subarray exactly when they are equal modulo n. Count how many earlier prefixes share the current remainder. In C++ negative remainders need a fix; Python's % already returns a non-negative result for a positive modulus.

Python Sum of values and subarray counting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every function is checked against the O(n^2) or O(n^3) definition on small random arrays that include negative numbers, which is where prefix-sum solutions most often break.

Where the other problems fit

  • Distinct Numbers, Distinct Values Subarrays: use a set or a sliding window of distinct values.
  • Concert Tickets and Room Allocation: a sorted multiset or a heap that always gives the best available option, see Monotonic Stacks, Heaps and Deques.
  • Restaurant Customers: a sweep over arrival and departure events, see Sorting, Events and Sweeps.
  • Maximum Subarray Sum: Kadane's algorithm, one pass. Nearest Smaller Values: a monotonic stack.
  • Collecting Numbers: count positions where pos[i + 1] < pos[i].
  • Josephus Problem with queries: see the classic puzzles section of Ad Hoc and Constructive Problems.
  • Array Division and Reading Books: binary search on the answer, and a short formula with maximum.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In Movie Festival, why do you sort by end time?

    An exchange argument shows that replacing the first movie of any optimal schedule by the one that ends earliest keeps the schedule valid.
  2. 2. Why does a hash map of prefix sums solve Subarray Sums II when negatives are present, while a sliding window does not?

    A window needs the sum to move in one direction when you move a pointer. Negatives break that, while prefix differences do not care.
  3. 3. Why is Traffic Lights solved in reverse time?

    Merging gaps only increases the maximum, so one variable is enough. Splitting would need a structure that can decrease the maximum.
  4. 4. Which key minimizes the sum of finish times in Tasks and Deadlines?

    The total reward is the sum of deadlines minus the sum of finish times. Running short tasks first makes the finish times, and their sum, as small as possible.

Summary

  • Sorting followed by two pointers solves matching problems (Apartments, Ferris Wheel, Sum of Three Values).
  • Interval and scheduling problems are greedy by a single key: end time for Movie Festival, duration for Tasks and Deadlines, the median for Stick Lengths.
  • Binary search covers monotonic answers (Factory Machines) and tower-top structures (Towers, with bisect).
  • Prefix sums plus a hash map count subarrays with a sum or a divisibility property, even with negatives.
  • Reverse time turns hard splits into easy merges (Traffic Lights).

Next: CSES DP Problems Walkthrough