Last Updated: 29 Nov, 2021
Minimum Elevator
Moderate
Asked in companies
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.
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
Approaches
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'.
Approach: In the Brute force approach, we see that its left-steps and right-steps are calculated for each building 'x'. Here the optimization is that if the height of (x-1)'th building is less than x-th building, then left-steps of x-th building becomes [1 + left-steps of (x-1)'th building]. The same is applied on right-steps of (x+1)'th building.
To achieve this, we need to store left-steps and right-steps for each building and reuse them, by which the inner loop (from brute force) can be skipped.
Algorithm:
- Create two arrays, 'left-steps' and 'right-steps', each of size 'N'.
- Initialize all the elements of both arrays with 1, as at least one elevator is a must.
- Iterate a loop, i = 2 to N, to fill the 'left-steps' array.
- If the height of i-th building is greater than (i-1)'th building, left-steps[i] will be (1 + left-steps[i-1]).
- Iterate a reverse loop, i = N-1 to 1, to fill the 'right-steps' array.
- If the height of the i-th building is greater than (i+1)'th building, right-steps[i] will be (1 + right-steps[i+1]).
- Initialize 'ans' with 0.
- Iterate a loop, i = 1 to N.
- Take the maximum among 'left-steps' and 'right-steps' for building 'i', and add into 'ans'.
- Return 'ans'.
Similar problems