# Largest Rectangle in Background

Imagine a photo taken to be used in an advertisement. The background on the left of the motive is whitish and you want to write some text on that background. So you scan the photo with a high resolution scanner and, for each line, count the number of pixels from the left that are sufficiently white and suitable for being written on. Your job is to find the area of the largest text box you can place on those pixels.

Example:
In the figure below, the whitish background pixels of the scanned photo are represented by asterisks.

```
*********************************
*********
*******
******
******
******
**************
**************
**************
***************
*********************

``` 

If you count the pixels on each line from the left you get the list (or array, depending on which language you are using) `[33, 9, 7, 6, 6, 6, 14, 14, 14, 15, 21]`. The largest reactangle that you can place on these pixels has an area of 70, and is represented by the dots in the figure below.

```
*********************************
*********
*******
******
******
******
..............
..............
..............
..............*
..............*******
``` 

Write a function that, given a list of the number whitish pixels on each line in the background, returns the area of the largest rectangle that fits on that background.

Difficulty: EASY
Tags: Fundamentals

Starter code:
def largest_rect(histogram):
	

Solutions:
def largest_rect(h):
	st = []
	m = 0
	i = 0
	while i < len(h):
		if len(st) == 0 or h[st[-1]] <= h[i]:
			st.append(i)
			i += 1
		else:
			l = st.pop()
			m = max(m, h[l] * (i if len(st) == 0 else i - st[-1] - 1))
	while len(st) > 0:
		l = st.pop()
		m = max(m, h[l] * (i if len(st) == 0 else i - st[-1] - 1))
	return m


def largest_rect(h):
	(r, s, i, l) = (0, [], 0, len(h))
	while i < l:
		if not s or h[s[-1]] <= h[i]:
			s.append(i)
			i += 1
		else:
			t = s.pop()
			a = i - s[-1] - 1 if s else i
			a *= h[t]
			r = r if r > a else a
	while s:
		t = s.pop()
		a = i - s[-1] - 1 if s else i
		a *= h[t]
		r = r if r > a else a
	return r


from itertools import groupby

def largest_rect(histogram):
	histogram.append(0)
	stack = [-1]
	result = 0
	for i in range(len(histogram)):
		while histogram[i] < histogram[stack[-1]]:
			h = histogram[stack.pop()]
			w = i - stack[-1] - 1
			result = max(result, h * w)
		stack.append(i)
	histogram.pop()
	return result


def largest_rect(histogram):
	(stack, max_area) = ([], 0)
	for (i, h) in enumerate(histogram + [0]):
		while stack and h <= histogram[stack[-1]]:
			height = histogram[stack.pop()]
			width = i if not stack else i - stack[-1] - 1
			max_area = max(max_area, height * width)
		stack.append(i)
	return max_area


def largest_rect(histogram):
	dim = len(histogram)
	if dim == 0:
		return 0
	max_el = max(histogram)
	min_el = min(histogram)
	if max_el == min_el:
		return dim * max_el
	area = max_el if max_el > min_el * dim else min_el * dim
	arr_work = [histogram]
	while len(arr_work) > 0:
		h = arr_work.pop()
		dim = len(h)
		max_el = max(h)
		min_el = min(h)
		if max_el * dim < area:
			continue
		if max_el == min_el:
			if area < dim * max_el:
				area = dim * max_el
			continue
		area = min_el * dim if area < min_el * dim else area
		split_index = h.index(min_el)
		if split_index * max_el >= area:
			arr_work.append(list(reversed(h[:split_index])))
		if (dim - 1 - split_index) * max_el >= area:
			arr_work.append(list(reversed(h[split_index + 1:])))
	return area


def largest_rect(heights):
	maxArea = 0
	stack = []
	for (i, h) in enumerate(heights):
		start = i
		while stack and stack[-1][1] > h:
			(index, height) = stack.pop()
			maxArea = max(maxArea, height * (i - index))
			start = index
		stack.append((start, h))
	for (i, h) in stack:
		maxArea = max(maxArea, h * (len(heights) - i))
	return maxArea


def largest_rect(r):
	(s, m) = ([-1], 0)
	for i in range(len(r)):
		while s[-1] != -1 and r[s[-1]] >= r[i]:
			m = max(m, r[s.pop()] * (i - s[-1] - 1))
		s.append(i)
	while s[-1] != -1:
		m = max(m, r[s.pop()] * (len(r) - s[-1] - 1))
	return m


from collections import deque

def largest_rect(a):
	(areas, stack, a) = ([], deque(), a + [0])
	for (i, x) in enumerate(a):
		j = i
		while len(stack) > 0 and x <= stack[-1][1]:
			(j, h) = stack.pop()
			areas.append((i - j) * h)
		stack.append((j, x))
	return max(areas or [0])


def largest_rect(histogram):
	(lis, ris) = ([], [])
	st = []
	for i in range(len(histogram)):
		while st and histogram[st[-1]] >= histogram[i]:
			st.pop()
		lis.append(st[-1] if st else -1)
		st.append(i)
	st = []
	for i in reversed(range(len(histogram))):
		while st and histogram[st[-1]] >= histogram[i]:
			st.pop()
		ris.append(st[-1] if st else len(histogram))
		st.append(i)
	return max((w * (ri - li - 1) for (w, li, ri) in zip(histogram, lis, reversed(ris))), default=0)


def largest_rect(histogram):
	if not histogram:
		return 0
	maxi = 0
	pile = []
	for elt in histogram:
		coeff = 0
		while pile and elt < pile[-1][0]:
			(top1, top2) = pile.pop()
			coeff += top2
			score = top1 * coeff
			maxi = max(maxi, score)
		pile.append([elt, coeff + 1])
	coeff = 0
	while pile:
		(top1, top2) = pile.pop()
		coeff += top2
		score = top1 * coeff
		maxi = max(maxi, score)
	return maxi