Grade 12 · 7 algorithmsCitește în română

Advanced techniques: two pointers, binary search on the answer, monotonic stacksTehnici avansate: doi pointeri, căutare binară pe răspuns, stive monotone

Every advanced techniques: two pointers, binary search on the answer, monotonic stacks algorithm from the Romanian high school curriculum, with the idea explained, its complexity, examples and code you can edit and run right here.

Create a free account Browse the collection

7algorithms
6chapters
1grade

Advanced techniques: two pointers, binary search on the answer, monotonic stacks

Tehnici avansate: doi pointeri, căutare binară pe răspuns, stive monotone · 7 algorithms

Binary search on the answerCăutare binară pe răspunsWe have n chapters with a[i] pages, in order, and k proofreaders. Every proofreader gets a run of consecutive chapters. We want the busiest…O(n log n)
Two pointers: pairs with sum x in a sorted arrayDoi pointeri — perechi cu suma x într-un vector sortatThe array has n distinct values in strictly increasing order. We want the position pairs i < j with a[i] + a[j] = x. Instead of trying all n * (n-1)…O(n)
Majority element (Boyer-Moore)Element majoritar (Boyer-Moore)The majority element appears more than n / 2 times. The voting algorithm keeps a candidate and a counter: a value equal to the candidate increases…O(n)
Sliding window: the longest subarray with sum ≤ SFereastra glisantă — cea mai lungă secvență cu suma ≤ SAll numbers are strictly positive. We keep a window [st, dr] and its sum. We always extend the right end by one element; while the sum exceeds S, we…O(n)
Monotonic stack: the next greater elementStiva monotonă — următorul element mai mareFor every a[i] we look for the first strictly greater value to its right (or -1). We keep a stack with the positions still 'waiting' for a greater…O(n)
Generating subsets with bitmasksGenerarea submulțimilor cu măști de bițiA subset of {a[0], ..., a[n-1]} can be encoded as a number masca between 0 and 2^n - 1: bit i of the mask is 1 if a[i] belongs to the subset. Bit i…Exponential
2D prefix sumsSume parțiale pe matrices[i][j] = the sum of the elements in the rectangle with corners (1, 1) and (i, j). It is computed once: s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] -…O(n²)