Posts

A hash map is an unordered data structure that stores key-value pairs. A hash map can add and remove elements in $O(1)$, as well as update values associated with a key and check if a key exists, also in $O(1)$. The biggest disadvantage of hash maps is that for smaller input sizes, they can be slower due to overhead. Because big O ignores constants, the $O(1)$ time complexity can sometimes be deceiving - it’s usually something more like $O(10)$ because every key needs to go through the hash function, and there can also be collisions....

Technically, an array can’t be resized. A dynamic array, or list, can be. In the context of algorithm problems, usually when people talk about arrays, they are referring to dynamic arrays. Given an array, a subarray is a contiguous section of the array. All the elements must be adjacent to each other in the original array and in their original order. A subarray or substring is a contiguous section of an array or string....

Monotonic: (of a function or quantity) varying in such a way that it either never decreases or never increases. A monotonic stack or queue is one whose elements are always sorted. It can be sorted either ascending or descending. Monotonic stacks and queues maintain their sorted property by removing elements that would violate the property before adding new elements. By maintaining the sorted property, the search space is reduced. Pseudocode for maintaining a monotonic increasing stack over an input array:...