Problem:
Find the rectangle with maximum area under a histogram in linear time.
Solution:

Complexity:
O(n)
Code:

kth smallest element in the union of the two sorted arrays

Problem:
Given two sorted arrays A and B of length n, find the kth smallest element in the union of the two sorted arrays. Do so in Θ(lgn).
Complexity:
O(log N)
Code:

Lucene Example