Arrays & Strings Checkpoint

1. Which structure gives average O(1) lookups to detect duplicates in an array?

Set/Map Sorted list + binary search Stack Queue

2. In a monotonic decreasing stack, you pop while the current value is:

greater than top less than top equal to top only any value

3. After a binary search loop for insertion position, which pointer gives the answer?

4. Two intervals [a,b] and [c,d] overlap (sorted by start) when:

c <= b b < c a < c and b < d c == d

5. Typical time complexity of binary search?