Skip to content

Latest commit

 

History

History
24 lines (21 loc) · 1.78 KB

general-problem-solving.md

File metadata and controls

24 lines (21 loc) · 1.78 KB
description
Consolidating some of the common patterns and problem solving methods you can try when working on problems

General Problem Solving

{% hint style="info" %} This list is not exhaustive! If you wish to contribute more techniques, please email me at woojiahao1234@gmail.com {% endhint %}

  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.md)
    1. Divide and conquer, similar to merge sort
    2. arrays manipulation + binary-search.md such as prefix sums + binary search
    3. sorting.md + operations on sorted array
    4. segment-trees.md+ iterating over all ranges
    5. Applying the sweep line algorithm if there are intervals.md + events
  5. Minimum/maximum across queries: try using heaps.md or double-ended-queues.md
    1. heaps.md can be used to track the minimum during any query
    2. double-ended-queues.md can be used to represent the current maximum (as the front) and potential maximums (subsequent elements) in the event where the current maximum "expires"