A collection of optimized algorithm implementations in Python — each function is written using the most efficient known approach for its problem, avoiding brute-force solutions in favour of techniques like monotonic stacks, prefix sums, sliding windows, binary search, and greedy strategies.
These algorithms were studied and trained specifically for high-frequency trading (HFT) and quantitative finance firms, where performance, correctness, and low latency are critical. Problems like sliding window medians, LRU/priority caching, monotonic stacks, and interval scheduling are commonly encountered in technical interviews and production systems at firms such as Jane Street, Citadel, Two Sigma, and similar.
Covers arrays, strings, heaps, stacks, queues, sliding windows, prefix sums, binary search, bit manipulation, trees, and caching. Every entry includes its time and space complexity so you can see exactly what "optimized" means in practice.
- Arrays & Intervals
- Prefix Sums & Subarrays
- Sliding Window
- Sorting & Greedy
- Monotonic Stack
- Heaps & Priority Queues
- Strings
- Binary Search
- Bit Manipulation
- Queues & Stacks
- Trees & Serialization
- Caching
- File & Log Parsing
Merges all overlapping intervals in a list.
Time: O(N log N) — sort dominates
Space: O(N) — merged output list
Returns all missing ranges within [l, r] from a sorted array.
Time: O(N)
Space: O(N) — gap list
Finds the minimum number of intervals to remove so no two overlap (greedy, sort by end time).
Time: O(N log N)
Space: O(1)
Finds the maximum number of train platforms needed given arrival and departure times.
Time: O(N log N) — two sorts + two-pointer scan
Space: O(1)
Finds the maximum profit from non-overlapping job intervals using DP + binary search.
Time: O(N log N)
Space: O(N) — DP array
Finds the minimum number of jumps to reach the end of an array (greedy).
Time: O(N)
Space: O(1)
Finds the length of the longest consecutive sequence using a hash set for O(1) lookups.
Time: O(N)
Space: O(N) — set
Finds the largest product of four adjacent numbers in any direction (horizontal, vertical, diagonal) in a grid.
Time: O(R·C) — constant checks per cell
Space: O(1)
Finds a subarray (or counts all subarrays) with sum equal to a target using a prefix-sum hash map.
Time: O(N)
Space: O(N)
Finds the maximum subarray sum (Kadane's algorithm).
Time: O(N)
Space: O(1)
Finds the longest subarray with sum equal to k using an earliest-index prefix map.
Time: O(N)
Space: O(N)
Finds the length of the longest subarray with sum equal to zero.
Time: O(N)
Space: O(N)
Counts all subarrays with sum equal to k using prefix sums.
Time: O(N)
Space: O(N)
Computes the sum of all multiples of n below limit using the arithmetic series formula. solve_efficiently combines multiples of 3 and 5 with inclusion-exclusion.
Time: O(1)
Space: O(1)
Finds the maximum value in each sliding window of size k using a monotonic deque.
Time: O(N) — each element pushed/popped at most once
Space: O(k) — deque
Finds the first negative number in each window of size k.
Time: O(N)
Space: O(k) — deque of negative indices
Streams sensor readings from a file and yields the moving average of the last k values.
Time: O(N)
Space: O(k) — sliding deque + running sum
Finds the minimum window substring of s that contains all characters of p.
Time: O(|s| + |p|)
Space: O(|s| + |p|) — two character maps
Groups words that are anagrams of each other by sorting each word as a canonical key.
Time: O(N · W log W) — W = max word length
Space: O(N · W)
Finds the starting gas station index for a circular route (greedy single pass).
Time: O(N)
Space: O(1)
Maximises the minimum distance between k cows placed in stalls (binary search on answer).
Time: O(N log N + N log D) — D = stall range
Space: O(1)
Minimises the maximum pages assigned to any student given a sorted book list (binary search + feasibility check).
Time: O(N log S) — S = sum of pages
Space: O(1)
Splits a sorted array into two numbers with minimum possible sum (digit-level addition).
Time: O(N log N)
Space: O(N)
For each element finds the next greater element to its right.
Time: O(N)
Space: O(N) — index stack + result array
Same as above but treats the array as circular (two-pass iteration).
Time: O(N)
Space: O(N)
Finds the largest rectangle area in a histogram (monotonic stack, dummy sentinel).
Time: O(N)
Space: O(N)
Computes total water trapped between histogram bars (two-pointer approach).
Time: O(N)
Space: O(1)
Computes the stock span — how many consecutive days before today had a lower or equal price.
Time: O(N)
Space: O(N)
Returns the next greater element and its distance for each reading.
Time: O(N)
Space: O(N)
Finds the maximum histogram rectangle area when one boundary bar may be removed.
Time: O(N) — four linear passes
Space: O(N) — four boundary arrays
Returns the running median after each insertion using a max-heap (small half) and a min-heap (large half).
Time: O(N log N)
Space: O(N)
Returns the k-th largest element seen so far after each insertion using a min-heap of size k.
Time: O(N log k)
Space: O(k)
Merges k sorted arrays using a min-heap.
Time: O(N·M log N) — N rows, M columns
Space: O(N) — heap
In-place heap sort using a max-heap built bottom-up.
Time: O(N log N)
Space: O(log N) — recursion stack
Online median finder. addNum keeps two heaps balanced; findMedian reads their tops.
| Method | Time | Space |
|---|---|---|
addNum(num) |
O(log N) | O(N) total |
findMedian() |
O(1) | O(1) |
Maintains a sliding window of the last k prices with O(log k) updates and O(1) stats.
| Method | Time | Space |
|---|---|---|
add_price(price) |
O(log k) | O(k) total |
get_stats() |
O(1) | O(1) |
Computes the median of every sliding window of size k using two heaps with lazy removal.
Time: O(N log k)
Space: O(k)
Returns the k most frequent events, with ties broken by first occurrence.
Time: O(N log N)
Space: O(N)
Finds the first non-repeating character. firstNonRepeating returns the result after each prefix.
Time: O(N)
Space: O(1) — fixed 26-char frequency array
Counts deletions needed to make s1 an anagram of s2.
Time: O(N + M)
Space: O(1)
Reverses the order of dot-separated words, filtering empty parts.
Time: O(N)
Space: O(N)
Reverses a string using Python slice.
Time: O(N)
Space: O(N) — new string
Checks if a string is a palindrome using two pointers.
Time: O(N)
Space: O(1)
Validates that all brackets are correctly matched and nested.
Time: O(N)
Space: O(N) — stack
Parses and checks intersection of two start-end intervals from a comma-separated text line.
Time: O(1)
Space: O(1)
Finds the index of the minimum element in a unimodal array using ternary search.
Time: O(log N)
Space: O(1)
Finds the minimum element in a rotated sorted array using binary search.
Time: O(log N)
Space: O(1)
See Sorting & Greedy — both use binary search on the answer space.
Counts the number of set bits using the n & (n-1) trick (clears the lowest set bit each iteration).
Time: O(log N) — one iteration per set bit
Space: O(1)
Reverses all 32 bits of an integer.
Time: O(1) — always 32 iterations
Space: O(1)
Finds the single non-duplicate element in an array using XOR accumulation.
Time: O(N)
Space: O(1)
Checks if n is a power of two via n & (n-1) == 0.
Time: O(1)
Space: O(1)
Returns N multiplied by its number of set bits.
Time: O(log N)
Space: O(1)
Implements a FIFO queue using two stacks. Each element is moved at most once, giving amortised O(1) per operation.
| Method | Time | Space |
|---|---|---|
enqueue(x) |
O(1) | O(1) |
dequeue() |
O(N) worst / O(1) amortised | O(1) |
peek() |
O(N) worst / O(1) amortised | O(1) |
empty() |
O(1) | O(1) |
Implements a LIFO stack using a deque by rotating all elements on each push.
| Method | Time | Space |
|---|---|---|
push(x) |
O(N) | O(N) total |
pop / top / size |
O(1) | O(1) |
Processes insert, delete, and frequency-check queries in O(1) each using two hash maps (value→count and count→frequency).
Time: O(Q) — Q = number of queries
Space: O(N) — distinct values
Finds two task durations that together fill a time slot exactly (complement hash map, similar to Two Sum).
Time: O(N)
Space: O(N)
Standard binary tree node with val (or data), left, and right fields.
Space: O(1) per node
Serializes/deserializes a binary tree to/from a comma-separated string using pre-order DFS. Null nodes are represented as "N".
Time: O(N)
Space: O(N)
BFS-based serialization to/from an array. Null nodes are stored as -1.
Time: O(N)
Space: O(N)
Pretty-prints a binary tree with indentation showing left/right children.
Time: O(N)
Space: O(H) — recursion stack; H = tree height
Prefix tree supporting insert, exact search, and prefix search.
| Method | Time | Space |
|---|---|---|
insert(word) |
O(L) | O(L) new nodes |
search(word) |
O(L) | O(1) |
isPrefix(prefix) |
O(L) | O(1) |
L = length of the word/prefix.
O(1) get and put using a hash map + doubly linked list. Least recently used item is evicted when capacity is exceeded.
| Method | Time | Space |
|---|---|---|
get(key) |
O(1) | O(1) |
put(key, value) |
O(1) | O(C) total |
C = cache capacity.
Extends LRU with priority levels. Within each priority level, eviction is LRU. Across levels, the lowest-priority item is evicted first.
| Method | Time | Space |
|---|---|---|
get(key) |
O(1) | O(1) |
put(key, value, priority) |
O(P) | O(C) total |
updatePriority(key, new_prio) |
O(1) | O(1) |
P = distinct priority levels. Eviction uses min() over priority keys — replace with a sorted structure for O(log P).
Parses a CSV trade-data line into a structured dict with timestamp, symbol, price, and quantity.
Time: O(1) Space: O(1)
Generator that yields one parsed trade record at a time — O(1) memory regardless of file size.
Time: O(N) Space: O(1)
Reads a unified diff and computes the net line-change per 10-line bucket of the original file.
Time: O(N) Space: O(B) — B = distinct buckets
Recursively flattens a nested JSON object into a flat key-value dict and writes it as a single-row CSV.
Time: O(K) — K = total scalar fields Space: O(K)
Filters and structures log lines matching a regex pattern, dropping DEBUG-level entries.
Time: O(N·L) — L = avg line length Space: O(N)
Reads a log file and counts ERROR entries grouped by hour bucket.
Time: O(N) Space: O(H) — H = distinct error hours
| Notation | Name | Example functions |
|---|---|---|
| O(1) | Constant | isPowerOfTwo, reverseBits, solve_efficiently |
| O(log N) | Logarithmic | countSetBits, findMinimum, minNumber |
| O(N) | Linear | Most sliding window, prefix sum, stack/queue functions |
| O(N log N) | Linearithmic | mergeIntervals, heapSort, getMedian, groupAnagrams |
| O(N log k) | Sub-linearithmic per element | kthLargest, SlidingWindowMedian, TradingWindow |
- Python 3.8+
- Standard library only (
collections,heapq,bisect,re,math,json,csv)