Defense of a Kingdom Problem

Solve another interesting problem based on the Greedy approach.

We'll cover the following

Problem statement

You are given the height and width of a field with the location of towers that guard the horizontal and vertical lines corresponding to their positions, where no two towers share a row or a column. Find out the largest unbounded area (the white rectangle).

In the example given below, we have a height of 6 and a width of 8. We also have 3 tower places. The largest unbounded area is 6 units.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.