Minimum Elevator

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
1 upvote
Asked in companies
MicrosoftGoogle inc

Problem statement

There are 'N' buildings in a straight line, and their heights are given. Your task is to install elevators in all the buildings such that if the height of a building 'x' is greater than any of its adjacent buildings, then the number of elevators in 'x' must be strictly greater than that adjacent building.

E.g: let given heights of buildings be [4, 3, 6, 2]. Then the number of elevators installed in the first building must be greater than in the second building. And the number of elevators in the third building must be greater than in the second and fourth buildings.

If two adjacent buildings have the same heights, then the number of elevators in them may be the same or different.

Find the minimum number of elevators required if it’s mandatory to install at least one elevator in each building.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains 'T', denoting the number of tests.
For each Test :
    The first line contains an integer 'N', denoting the number of buildings.
    The second line contains an array 'A' of length 'N', denoting the heights of buildings.
Output Format: 
For each test, print an integer, denoting the minimum number of elevators required.
Note: 
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints - 
1 <= 'T' <= 10
1 <= 'N' <= 10^5
1 <= A[i] <= 10^9  i ∈  (1, N)
Note - Sum of 'N' over all test cases does not exceed 10^5.

Time Limit: 1 sec

Sample Input 1:
2
6
1 4 3 6 2 1
3
1 2 2
Sample Output 1:
10
4
Explanation for Sample Input 1:
For case 1:
To fulfill all the requirements, the optimal number of elevators are [1, 2, 1, 3, 2, 1], which in total are 10 elevators.

For Case 2:
Optimal number of elevators are [1, 2, 1]. Second and third buildings may have the same or different number of elevators, but installing different ones gives the optimal answer.
Sample Input 2:
2
3
1 1 1
4
3 2 1 3
Sample Output 2:
3
8
Hint

Fix a building and find the number of buildings affecting its number of elevators.

Approaches (2)
Brute Force

Approach: Run a loop to select each building one by one. For a building 'x', move in its left until building height is decreasing from current height, the number of moves will be the number of elevators in 'x' by left neighbours. Repeat the same process on the right side, and take maximum steps among the left and right.

The number of elevators in building 'x' will be [maximum steps on any side + 1].


 

Algorithm:

  • Initialize 'ans' with 0.
  • Iterate a loop, i = 1 to N, to select the buildings.
    • Initialize 'left-steps' with 0.
    • Iterate a reverse loop, j = i-1 to 1.
      • If the height of j-th building is strictly less than (j+1)'th building, increment the number of left-steps.
      • Else, break the loop.
    • Initialize 'right-steps' with 0.
    • Iterate a loop, j = i+1 to N.
      • If the height of j-th building is strictly less than (j-1)' th building, increment the number of right-steps.
      • Else, break the loop.
    • The number of elevators in the i-th building will be [1 + maximum among left-steps and right-steps].
    • Add the number into 'ans'.
  • Return 'ans'.
Time Complexity

O(N ^ 2), where 'N' is the number of buildings.

We run two nested loops. Hence, overall time complexity becomes O(N ^ 2).

Space Complexity

O(1).

We are using constant space. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Minimum Elevator
Full screen
Console