Dam of Candies

This article describes the question from Day 8 of the 30 Days of Code competition hosted by Geeks for Geeks.

Question

Geek wants to make a special space for candies on his bookshelf. Currently, it has N books of different heights and unit width. Help him select 2 books such that he can store maximum candies between them by removing all the other books from between the selected books. The task is to find out the area between 2 books that can hold the maximum candies without changing the original position of selected books.

Example 1:

Input: N = 3, height[] = {1, 3, 4} Output: 1 Explanation:

1. Area between book of height 1 and book of height 3 is 0 as there is no space between them.
2. Area between book of height 1 and book of height 4 is 1 by removing book of height 3.
3. Area between book of height 3 and book of height 4 is 0 as there is no space between them.

Example 2:

Input: N = 6, height[] = {2, 1, 3, 4, 6, 5} Output: 8 Explanation: We remove the 4 books in the middle creating length = 4 for the candy dam. Height for dam will be min(2,5) = 2. Area between book of height 2 and book of height 5 is 2 x 4 = 8.

Your Task:
You don't need to read input or print anything. Complete the function maxCandy() which takes the array height[] and size of array N as input parameters and returns the maximum candies geek can store

Expected Time Complexity: O(N) Expected Auxiliary Space: O(1)

Constraints: 1 ≤ N ≤ 105

Simple Solution

This is the naive solution to this problem. We create a function area, this computes the area between two different heights. It takes into account the fact that adjacent pairs can't form a damn by subtracting one. We map over all the possible pairs and calculate their area. The largest area represents the largest dam. So we take the maximum value from our search above.

from itertools import combinations 

class Solution:
    def area(self, pair):
        d = pair[1][0] - pair[0][0] - 1
        h = min((pair[1][1],pair[0][1]))
        return d * h 

    def maxCandy(self, h, n): 
        a = list(map(self.area, combinations(enumerate(h),2)))
        if not a:
            return 0
        return max(a)

This solution does not meet the time complexity O(N) for the question. Our solution performs four operations (enumerate, combinations, map, max) on a list of elements of size N O(4*N). We need to optimize this code, to complete the area calculation in one pass.

Optimized Solution

Here we propose a solution that fits the O(N) time complexity. The solution is similar in form to the previous days.

class Solution:
    def maxCandy(self, h, n): 
        if n < 3:
            return 0
        p = 0 
        q = n - 1
        a = 0
        m = (n-2) * min(h[0],h[n-1])
        while p < q:
            a = min(h[p],h[q]) * (q-p-1)
            m = max(a,m)
            if h[p] < h[q]:
                p += 1
            else: 
                q -= 1
        return m

If there are only two books or less. It is not possible to build a dam. They are either adjacent to each other. Or, we only have one book. Both of these scenarios are invalid conditions for a candy dam.

We use to pointers p and q. p starts from the first height and moves forward, to the right. q is the final height and moves backwards, to the left. We perform the same area calculation as before. The minimum of the heights, multiplied by their distance subtracted by 1.

We check to see which height is taller, or p or q. If the q is larger, we increase the p, since we may find another value which can form a larger area. If the p is greater, we decrease the q, similarly, we may find another value that gives a greater area.

We store the maximum area that has been found so far in a variable m. We simply perform a max operation on the previous maximum and the current, to keep this value updated. Finally, after once complete pass, and q is no longer greater than p (i.e, our pointers converge), we return the largest area that we found.