132 Geeky Buildings

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

Question

There are N buildings in Linear Land. They appear in a linear line one after the other and their heights are given in the array arr[]. Geek wants to select three buildings in Linear Land and remodel them as recreational spots. The third of the selected building must be taller than the first and shorter than the second. Can geek build the three-building recreational zone?

Example 1:

Input: N = 6 arr[] = {4, 7, 11, 5, 13, 2} Output: True Explanation: [4, 7, 5] fits the condition.

Example 2:

Input: N = 4 arr[] = {11, 11, 12, 9} Output: False Explanation: No 3 buildings fit the given condition.

Your Task: You don't need to read input or print anything. Complete the function recreationalSpot() which takes the array arr[] and its size N as input parameters and returns a boolean value based on whether his building selection was successful or not. Note: The generated output will be "True" or "False".

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

Constraints: 1 ≤ N ≤ 104 1 ≤ arr[i] ≤ 105

Solution

Here is the solution to Day 18 in Python.

class Solution:
    def recreationalSpot(self, arr, n):
        m = float('inf')
        for i in range(n):
            m = min(arr[i],m)
            if i != 0 and i != n-1:
                if arr[i] > arr[i-1] and arr[i] > arr[i+1]:
                    if arr[i+1] > m:
                        return True
        return False

We keep a record of the minimum so far m. Initially set to positive infinity, this variable is needed to see if the third building is taller than the first.

We iterate over each of the heights. The first conditional checks to see that we are not at the edge of the array. Buildings that are possible candidates for the middle of building sites have to have neighbours. Then we check that that middle building fits the valid conditions, those being larger than its neighbours. We then ensure that the third building is larger than the first.

If there is a building that meets all of the conditions, the loop is broken, and we return true since there is a valid building site. If no buildings meet this condition, we simply return false, after the loop has finished.

132 Geeky Buildings

Geeks for Geeks - 30 Days of Code - Day 18

Question

Solution