Save the largest area

Problem Statement

In the historic city of Technisia there are rectangular monuments made of stones. The monuments are placed on the ground in such a way that they all lie in one row. The width of each monument is one unit and the length may vary.  The population of the city is growing and people need empty spaces to build houses and markets. The mayor decides to demolish the monuments and presents a demolition schedule.

You being a monument lover, would like to preserve the most of what can be preserved, hence you start finding a solution to save the largest area. Upon your request the mayor granted you permission to preserve a continuous rectangular shape out of the monument. You want to preserve the maximum area possible.

Here are the monuments

Save the largest area

You can choose to protect any rectangular portion as shown below, but the aim is to save the one with largest area. Here are few options for you.

Save the largest area

Clearly in the above image the the model with a = 21 is the logical choice to save.  The task at hand is to write a program to find the maximum possible area which can be saved from demolition.

Approach

Like most of the problem statements we can solve this using the brute force technique and many other ways.

Trivial Solution

Here is a simple algorithm for solving this:

  1. Start from the beginning of the array.
  2. For every element ai of the array
    1. Move to the right until you get an element smaller than ai or the end of the array. Let say the index of the element is k.
    2. Move to the left until you get an element smaller than ai. Let say the index of the element is j.
    3. The total area which can be saved is ai * (k-j)

Source Code

Analysis

The above algorithm runs in O(N2) time because the outer loop runs for the length of the array and the inner loop runs till both the ends from one element.

Space required is constant because we do not use any extra space apart from few temporary variables

A Recursive Solution

While writing the above solution, I realized that the approach is similar to the one used in finding the diameter of a tree. Here is how:

  1. Find the smallest element in the array, say its ai.
  2. Now recursively find the largest area to the left of ai. Say it AL
  3. Recursively find the largest area to the right of ai. Say it AR
  4. The largest area which can be saved is the maximum of AL, AR or ai * length of the array.

Here is a visual of how the recursion will take place.

Save the largest area

  • The first step divides the array into two chunk through the red block.
  • The left and right are then divided through the green blocks on both the sides
  • The third recursion step divides the remaining array through the blue block.

Source Code

Here is the github link for a working code

Analysis

The above algorithm runs in O(NlogN) time  for the same reason as the diameter of a tree problem.

T(N) = T(N/2) + T(N/2) + constant;
T(N) = 2 * T(N/2) + cN
The solution to this recurrence is O(NlogN).

For prove you can check the post about merge sort. If you face any difficulty understanding the post, please let me know in the comments below.

Side Note: Can we do better? O(NlogN) is great to achieve. But can we improve this? May be a linear time algorithm. Stay connected for further updates on the same.