Given an array height representing the heights of buildings. You have to count the buildings that will see the sunrise (Assume the sun rises on the side of the array starting point).
Note: The height of the building should be strictly greater than the height of the buildings left in order to see the sun.
Examples :
Input: height = [7, 4, 8, 2, 9] Output: 3 Explanation: As 7 is the first element, it can see the sunrise. 4 can't see the sunrise as 7 is hiding it. 8 can see. 2 can't see the sunrise. 9 also can see
the sunrise.
Input: height = [2, 3, 4, 5] Output: 4 Explanation: As 2 is the first element, it can see the sunrise. 3 can see the sunrise as 2 is not hiding it. Same for 4 and 5, they also can see the sunrise.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ height.size() ≤ 106
1 ≤ heighti ≤ 108
Approach 01:
-
C++
-
Python
class Solution { public: // Returns the count of buildings that can see sunlight int countBuildings(vector<int>& buildingHeights) { int visibleBuildings = 1; int tallestBuilding = buildingHeights[0]; int totalBuildings = buildingHeights.size(); if (totalBuildings == 1) { return visibleBuildings; } for (int i = 1; i < totalBuildings; ++i) { if (buildingHeights[i] > tallestBuilding) { ++visibleBuildings; tallestBuilding = buildingHeights[i]; } } return visibleBuildings; } };
class Solution: # Returns count of buildings that can see sunlight def countBuildings(self, buildingHeights): visibleBuildings = 1 tallestBuilding = buildingHeights[0] totalBuildings = len(buildingHeights) if totalBuildings == 1: return visibleBuildings for i in range(1, totalBuildings): if buildingHeights[i] > tallestBuilding: visibleBuildings += 1 tallestBuilding = buildingHeights[i] return visibleBuildings
Time Complexity
- Iterating through the buildings:
The function iterates over the `buildingHeights` array exactly once in a for-loop, which takes \(O(n)\), where \(n\) is the number of buildings in the input.
- Overall Time Complexity:
The time complexity is \(O(n)\) since the algorithm processes each building height in linear time.
Space Complexity
- Space for variables:
The function uses a few variables (`visibleBuildings`, `tallestBuilding`, `totalBuildings`), which all take constant space, \(O(1)\).
- Input space:
The input array `buildingHeights` is not modified, so the function does not require extra space proportional to the input size.
- Overall Space Complexity:
The space complexity is \(O(1)\) because no additional data structures are used other than a few integer variables.