Algorithm Pattern and Strategy Overview

This is a serie of my note to summarize some of the algorithm patterns and strategies that are often used to solve coding problems, as I practice on leetcode.

Brute Force

Brute force is to list out all possible solutions, and is, most of the time, not optimal, but easier to come up with as long as we follow the logic flow of solving the problem. If we cannot identify a better approach, we should start from brute force then identify opportunities to optimize. Especially during interviews, it’s always better to be able to give at least a solution even if it’s brute force.

Divide and Conquer

Divde and conquer is to solve a big problem by breaking it down into smaller sub-problems.

Typical example: merge sort, quick sort etc.

Recursion / Dynamic Programming

Recursion and DP is a type of divide and conquer.

When a problem depends on the solutions of the smaller instances of itself, as we reduce the problem, we will reach a base case where the problem can’t get smaller anymore. In code it often appears as a function calls itself.

Recursion sometimes solve identical problems, and DP can be used to cache the intermediary results, to reduce the recursive function calls and improve efficiency.

Typical example: fibonacci sequence

Backtracking

When solving a problem, at each step, we have a solution space that we can choose from. We try out each of them, as we find the decision we made breaks the constraints we have, we undo the choice we made, then try another one.

Typical example: sudoku, maze

Greedy Algorithm

Greedy algorithm is when doing optimization, make the local optimal choice at each step to solve the overall problem. Local optimals doesn’t always guarantee an overall optimal solution. It is usually very difficult to identify a working greedy strategy. Like brain teasers, you need to see the problem from the right angle. It gives you the moment: Aha! The solution is simple as that.

Typical example: Dijkstra’s algorithm (shortest path)

Sliding Window

Array/list problems that requires scanning through a range of subarrays, can often be solved using brute force approach, where we usually have nested loops. By using sliding window, we can often eliminate some of the unneccesary checks and improve time complexity.

Typical example: longest substring without repeating characters

Fast and Slow Pointers

Fast and slow pointer technique is useful when dealing with data structures whose lengths are not explicit, for example linked list, graph.

Typical example: palindromic linked list