Change the problem first
Transform and conquer solves a problem in two stages: first transform the input or the problem into a form that is easier to handle, then solve that easier form. The transformation cost is paid up front in exchange for a cheaper solve.
Three styles of transformation
- Instance simplification: convert the input to a more convenient instance. Sorting a list before searching it, or before removing duplicates, makes the later step trivial.
- Representation change: keep the same data but store it differently. Building a heap to support repeated minimum extraction, or a balanced search tree for ordered queries, changes the representation, not the data.
- Problem reduction: map the problem to a different problem with a known solution, such as expressing a task as a shortest path or as a system of linear equations.
When it pays off
Transform and conquer wins when the transformation is cheaper than the savings it unlocks, or when it is done once and reused across many queries. Sorting an array once costs a sort, but it then enables many fast binary searches, amortizing the transformation over all the queries that follow.
Key idea
Transform and conquer reshapes a problem, by simplifying the instance, changing its representation, or reducing it to a known problem, so that the solving stage becomes easy enough to justify the transformation cost.