b.stefanuk.caAlgorithms and How to Solve Them
Algorithm Tips
- Forwards/backwards Be aware of opportunities to do a forward then a backwards pass, multiple passes is still O(n) time and it can sometimes keep space complexty to O(1)
- Two pointer For certain types of problems, consider using a two pointer approach, for example,
- Start from either end and move inwards.
- Move left and right pointers according to different conditions.
- Turtle and hare: Use one pointer that moves faster than the other. This can also be useful in linked list problems.
- Increment/decrement: Some voting algorithms, like majority element, can be effectively solved with a combined increment and decrement approach. Also useful in hash tables problems.
- Quick swap index values with
A[i], A[j] = A[j], A[i]
- Once you have an example. Draw it out, don't just try and visualize it the steps you need, but actually draw out a diagram of the problem. This is an essential part of the problem solving process that I typically forgot when I was beginning with these problems.
Tip
Think about the equation (if it exists) that solves the problem at hand. For example, in the Two Sums problem the equation is
num[i] + num[j] == target. In what ways can this be re-arranged to help resolve the algorithm?num[i] == target - num[j]perhaps?
String Matching Problems
- If you need to match unordered data, consider using a HashTable or an array where the indices are the keys, this will allow you to match anagrams of strings, for example