Algorithmic Gems — Thinking backwards

In this series I talk to computer scientists and software engineers about advanced algorithmic ideas that aren’t typically captured in programming or algorithms textbooks, I try to keep it simple and light but feel free to leave a comment if you’ve a question and I will make sure to reply to you.

Today I’d like to point out a very simple, yet very powerful technique when it comes to problem solving: Think backwards!

In many cases it’s a lot easier or more efficient to solve a problem by trying to move from the end to the start rather than the other — more straightforward — way around.

Thinking backwards is a way of thinking rather than one fixed standard approach, it can come in many flavors depending on the problem. Here are a couple of common examples of how thinking backwards can be applied to problem solving:

1. Many sources / One destination

Imagine N police cars at different locations trying to reach a crime scene as quickly as possible, which car gets to the crime scene first? Well, by thinking forwards we can calculate the shortest path from each police car (the logical source) to the crime scene (the destination) and then simply pick the car with the minimum distance to the crime scene, that is N runs of a single-source shortest path algorithm.

Instead, by thinking backwards we can calculate the shortest path from the crime scene (the source) to the police cars (the destinations) and then pick the car with the minimum distance, thus solving the problem in only one run of the shortest path algorithm.

2. Assume + Verify

Another instance of a backwards-thinking approach to problem solving is to find a strategy to enumerate multiple possible answers for the problem (two common strategies are brute force and binary search) and then verify and choose one of the enumerated possibilities, this is in contrast to trying to compute the answer directly (forward thinking) which might be more difficult to achieve.

Alright, I hope today’s topic was useful. You can read previous algorithmic gems here, and as always I love to hear any feedback or questions.

You can follow Algorithmic Gems on Facebook and YouTube to receive future algorithmic gems, also feel free to share this with anyone who might find it useful.

Thanks for reading!