Roof Top

You are given the heights of consecutive buildings. You can move from the roof of a building to the roof of the next adjacent building. You need to find the maximum number of consecutive steps you can put forward such that you gain an increase in altitude with each step.

Examples:

Input: arr[] = [1, 2, 2, 3, 2]
Output: 1
Explanation: 1, 2, or 2, 3 are the only consecutive buildings with increasing heights thus maximum number of consecutive steps with an increase in gain in altitude would be 1 in both cases.

Input: arr[] = [1, 2, 3, 4]
Output: 3
Explanation: 1 to 2 to 3 to 4 is the jump of length 3 to have a maximum number of buildings with increasing heights, so maximum steps with increasing altitude becomes 3.

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

Constraints:
1 <= arr.size() <= 10⁶
1 <= arr[i]<= 10⁵

Approach 01:

class Solution {
public:
    // Function to find the maximum number of consecutive steps
    // where the altitude increases with each step.
    int maxStep(vector<int>& heights) {
        int maxConsecutiveSteps = 0;  // Track the maximum consecutive increasing steps
        int currentConsecutiveSteps = 0;  // Track the current number of consecutive increasing steps
        
        for (int i = 1; i < heights.size(); ++i) {
            // If the current height is greater than the previous height, increment the current step count
            if (heights[i - 1] < heights[i]) {
                currentConsecutiveSteps++;
            } else {
                // Reset the current step count when the sequence breaks
                currentConsecutiveSteps = 0;
            }
            // Update the maximum consecutive steps
            maxConsecutiveSteps = max(maxConsecutiveSteps, currentConsecutiveSteps);
        }
        
        return maxConsecutiveSteps;
    }
};

class Solution:
    # Function to find the maximum number of consecutive steps 
    # where the altitude increases with each step.
    def maxStep(self, heights):
        maxConsecutiveSteps = 0  # Track the maximum consecutive increasing steps
        currentConsecutiveSteps = 0  # Track the current number of consecutive increasing steps
        
        for i in range(1, len(heights)):
            # If the current height is greater than the previous height, increment the current step count
            if heights[i-1] < heights[i]:
                currentConsecutiveSteps += 1
            else:
                # Reset the current step count when the sequence breaks
                currentConsecutiveSteps = 0
            
            # Update the maximum consecutive steps
            maxConsecutiveSteps = max(maxConsecutiveSteps, currentConsecutiveSteps)
        
        return maxConsecutiveSteps

Time Complexity

• Loop Iteration:

  The solution iterates through the array of heights once, comparing each pair of consecutive elements. Since there is a single loop over all elements of the vector, the time complexity is \(O(n)\), where \(n\) is the number of elements in the heights vector.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the size of the heights vector.

Space Complexity

• Auxiliary Space:

  The algorithm uses a constant amount of extra space for variables maxConsecutiveSteps and currentConsecutiveSteps, regardless of the input size. This results in a space complexity of \(O(1)\).

• Input Space:

  The input vector heights is passed by reference, so no additional space is used to store the input.

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), as the space required does not depend on the size of the input.