The Array cheatsheet!
You read a DSA problem and you know certain patterns it might fit in, you examine it more closely and zero in on the pattern you think will work, and it does work, your solution gets accepted, how do you feel in that moment?
Well to keep you guys feeling “pretty pretty pretty good”, I’ve compiled certain patterns I’ve observed most array or let’s say sequence problems can be broken down into.
This is just a compilation from my experience, I would love your input to improve and extend it!
- Slide those windows!
More often than not, if we are asked to find a continuous subarray or a substring, the sliding window technique is what we should be looking for.
The basic structure of the solution is to find the first window and then basically increase the end one by one, and for every increase of the end, check if the start needs to be updated to make the window valid again.
Here are a few questions that can be solved using sliding windows:
- Minimum Size Subarray Sum
- Longest Repeating Character Replacement
- Subarray Product Less Than K
- Longest Substring Without Repeating Characters
If you notice above we are looking for a subarray or a substring in all the questions above.
2. The Pre and Post fixes!
Calculating the prefix/ postfix sum, min or max can help solve a lot of array problems. Let's look at a few.
- Partition array into disjoint intervals
Here we calculate prefix and postfix, minimum and maximum elements for each index, problem then boils down to calculating the index till all the max prefix is less than the max postfix. - Product of an array except self
Here we try to calculate the prefix/ postfix product for each index, by iterating through once for prefix and in reverse order for postfix. Now the problem boils down to multiplying the prefix and postfix values for each index! - Buy-Sell stocks
This again can be solved by just trying to calculate the maximum postfix values for each index by reverse iterating the array, now that value is the selling point for each index and we can then find the max profit calculating the profits for each index!
3. Matrix’s the book-keeper!
Sometimes when we aren’t allowed to use extra space, we can use the matrix’s rows/ columns to do the book-keeping.
- Set Matrix Zeroes
We use the first row and column to track which row and column are to be made zero! - Game of Life
Here as we process the matrix we update the values, to be able to calculate the current row we need the original values above and towards the left of the current index, we do that by saving the last row and the current row, instead of having to make a new matrix for the solution.
4. The good old Kadane’s!
I don’t think we need an introduction here, but it just had to be mentioned.
Maximum subarray sum and product are a few of the basic questions it solves.
As I’ve covered in another article before, it can solve much more, including problems on binary trees like Binary tree maximum path sum!
5. Those two pointers!
Two-pointers is another technique that solves a bunch of problems. It usually works well with sorted sequences, where we can start the pointers at the extreme end and update either one to try to reach closer to the result.
We can use the concept even with unsorted arrays. Container with most water is a very interesting example of that. All we have to do is start the pointers at the extreme ends and try to increase the smaller value so we can find a bigger container!
- Two, three, four Sum!
- Three sum closest
- Shortest Unsorted Continuous Subarray
- Container with most wate
6. Merge those intervals!
The most confusing thing about merging intervals is getting lost in the cases. Below is all the cases we need to remember when we think about merging two intervals, this will help us solve ALL the merge interval problems.
7. Chicken or the egg debate!
Dealing with circular array can get quite tricky, I’ve convered different strategies in the separate article here!
I hope this article helps in building up structured thinking to tackle array related problems. I’m gonna cover other data structures in future articles.
Thanks for reading and please feel free to comment if you can add more ideas to this list!
