Design - cocoder39/coco39_LC GitHub Wiki

hash

• 380. Insert Delete GetRandom O(1) (two pointers delete)
• 381. Insert Delete GetRandom O(1) Duplicates allowed (two pointers delete)
• 588. Design In Memory File System
• 981. Time Based Key Value Store (dict + binary search)

stack & queue

• 20. Valid Parentheses
• 232. Implement Queue using Stacks
• 225. Implement Stack using Queues
• 155. Min Stack (implement min queue with min stack)
• 895. Maximum Frequency Stack (similar technique is used in 146 LFU cache to identify min or max frequency in O(1))

monotonic stack

• 255. Verify Preorder Sequence in Binary Search Tree (monotonic stack, vector mimics stack)
• 84. Largest Rectangle in Histogram (not dp, monotonically increasing stack)
• 85. Maximal Rectangle (84. Largest Rectangle in Histogram)
• 316. Remove Duplicate Letters
• 321. Create Maximum Number

monotonic queue

• 239. Sliding Window Maximum

array

• 348. Design Tic-Tac-Toe

hashtable (O(1) indexing) + Doubly linked list (maintain order + O(1) insertion and deletion)

• 460. LFU Cache
• 146. LRU Cache (record min freq O(1) instead of maintaining freq in sorted data structure O(log N), similar technique is used in 895. Maximum Frequency Stack to identify min or max frequency in O(1)))