Roof Top

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Find maximum number of consecutive steps that can be climbed going uphill (arr[i+1] > arr[i]).

Algorithm

1Track current run of increasing steps. Reset on decrease. Track maximum run.

Common Pitfalls

•Simple linear scan. Reset counter when arr[i] >= arr[i+1]. Maximum consecutive increasing steps.

Roof Top.java

Java

// Approach: Greedy. Count the number of consecutive ascending steps from the start.
// Time: O(n) Space: O(1)
class Solution {
    // Function to find maximum number of consecutive steps
    // to gain an increase in altitude with each step.
    public int maxStep(int arr[]) {
        int res = 0, count = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i - 1] < arr[i]) {
                count++;
            } else {
                count = 0;
            }
            res = Math.max(res, count);
        }
        return res;
    }
}

Was this solution helpful?