Intro
Recognizing the patterns is key to solving these problems quickly in an interview, because you won’t have time to research the problem, break down thoroughly, and try somethings…
Categories
There are two categories
- Linear: work with arrays, linked lists, and strings
- Non-linear: work with trees and graphs
Linear patterns# Intro
References
Two Pointers
Common pattern utilizing two pointers to minimize the time complexity of traversing a linear DS instead of BruteForce
Allows for solving in O(n) which boosts efficiency
Same Direction
The pointers move in the same direction. Ideal for scanning or processing in a single pass.
Fast and slow pointer approach
Great for detecting cycles in LinkedLists or finding the middle of the list.
- Slow ptr moves one step at a time
- Fast ptr moves two steps at a time Allowing for checking cycles if the fast ptr lands on the slow ptr…
Opposite Direction.
Typically used in problems that involve “Finding pairs” or comparing elements from opposite ends.
Find two numbers sum to target value
One ptr at the start and one at the end. Then move the pointers one step in their respective directions each iteration, while checking if they sum up. This eliminates unnecessary comparisons.
Sliding window
A variant of the Two Pointers but with a more focused purpose.
These two pointers, start and end, form a “window” of elements that moves through the DataStructure.
This allows us to manage a range of elements such as a sub-array or substring.
Dynamically resizing
Depending on the problem and the conditions, sometimes the window dynamically adjusts its size as it progresses. Either, by extending the end or shrinking the start.
A common problem is the Longest Substring Without Repeating Characters and combines HashMap to solve it. I’ve solved it here Hashmap An extremely powerful pattern for tracking contiguous sequences when dealing with strings, arrays, and linked lists by controlling range of elements.
Frequency and Count problems
Depending on the problem, if you’re presented with a “find longest” or “what’s the shortest…” premise for a problem, you’re likely going to need a Hashmap of some sort to count the occurrences.
For example: Longest Palindrome
Binary Search
A common pattern and traversal method, DO NOT confuse it with BinarySearchTree and Binary Trees. This is referring to Binary Search in Linear DS, like outlined here Binary Search.
Non-Linear patterns
Graphs and Trees
I’ve written about Trees and Graphs before so be sure to check those out.
Algorithms
- BFS
- DFS
- BackTracking
- Heaps aka Priority Queue Read in more detail in Graph and Tree Algorithms
Dynamic Programming
Ugh how I dread DynamicProgramming. It’s hard to formulize and template due to the nuance it takes from the problems themselves. Read Dynamic Programming