Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Minimum Area Rectangle
Bookmark
Input
Standard
Rectangle
Multiple
points
=
[[1,1],[1,3],[3,1],[3,3],[2,2]]
lastX · (y1,y2) → x
min area = ∞
a rectangle needs two columns that share the same y-pair
lastX · (y1,y2) → x
min area = ∞
a rectangle needs two columns that share the same y-pair
lastX · (y1,y2) → x
min area = ∞
column x =
1
: y = {1, 3}
lastX · (y1,y2) → x
min area = ∞
right edge: y-pair (
1, 3
) at x = 1
lastX · (y1,y2) → x
min area = ∞
no earlier column has (
1, 3
) yet
lastX · (y1,y2) → x
(1,3)
→ 1
min area = ∞
remember lastX[(1, 3)] =
1
lastX · (y1,y2) → x
(1,3)
→ 1
min area = ∞
column x =
3
: y = {1, 3}
lastX · (y1,y2) → x
(1,3)
→ 1
min area = ∞
right edge: y-pair (
1, 3
) at x = 3
area 4
lastX · (y1,y2) → x
(1,3)
→ 1
min area = 4
rectangle [1..3] × [1..3] → area = 2 × 2 =
4
(new min!)
lastX · (y1,y2) → x
(1,3)
→ 3
min area = 4
remember lastX[(1, 3)] =
3
area 4
lastX · (y1,y2) → x
(1,3)
→ 3
min area = 4
minimum area rectangle =
4
algo
master
.
io
Step:
Find the minimum axis-aligned rectangle
0 / 10
Input
Standard
Rectangle
Multiple
points
=
[[1,1],[1,3],[3,1],[3,3],[2,2]]
0 / 10
algo
master
.
io
Step:
Find the minimum axis-aligned rectangle
