General Problem Solving

Consolidating some of the common patterns and problem solving methods you can try when working on problems

This list is not exhaustive! If you wish to contribute more techniques, please email me at [email protected]

1. Finding the median of data: focus on the definition of a median and model the solution after it

2. Sub-array problems: think about using sliding windows discussed under Arrays

3. Sub-sequence problems: think about sorting (if possible)

4. $O(n \log n)$ upper bound (found using Runtime Predictions)

   1. Divide and conquer, similar to merge sort

   2. Arrays manipulation + Binary Search such as prefix sums + binary search

   3. Sorting + operations on sorted array

   4. Segment Trees+ iterating over all ranges

   5. Applying the sweep line algorithm if there are Intervals + events

5. Minimum/maximum across queries: try using Heaps or Double Ended Queues

   1. Heaps can be used to track the minimum during any query

   2. Double Ended Queues can be used to represent the current maximum (as the front) and potential maximums (subsequent elements) in the event where the current maximum "expires"