Q5. The heights of certain Buildings which lie adjacent to each other are given. Light starts falling from left side of the buildings. If there is a building of certain Height, all the buildings to the right side of it having lesser heights cannot see the sun . The task is to find the total number of such buildings that receive light.

Question Link - Click Here to Solve This Problem

Intuition Behind the Algorithm

The "Sunny Buildings" problem presents a scenario where buildings stand adjacent to each other, and sunlight falls from the left. The challenge is to identify how many buildings are not overshadowed by taller buildings to their left. The core intuition here is to realize that a building will receive sunlight if it is taller than all buildings to its left. This leads to a linear scan from left to right, keeping track of the tallest building encountered so far.

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Read the number of test cases
    int t;
    cin >> t;

    // Process each test case
    while(t--) {
        int n; // Number of buildings
        int ans = 0; // Count of buildings receiving sunlight
        int maxh = INT_MIN; // Maximum height encountered so far
        cin >> n;

        // Iterate through each building
        for(int i = 0; i < n; i++) {
            int num; // Height of the current building
            cin >> num;

            // If the current building is taller or equal to the tallest so far,
            // it receives sunlight.
            if(num >= maxh) {
                ans++;
                maxh = num; // Update the tallest building encountered
            }
        }

        // Output the count of buildings receiving sunlight for this test case
        cout << ans << endl;
    }

    return 0;
}

Code Walkthrough

The provided C++ code efficiently solves the problem using a simple linear scan approach.

• Initial Setup: The code begins by reading the number of test cases t. Each test case is processed in the following steps.

• Processing Each Test Case: For each test case, the number of buildings n is read. The variables ans (to store the count of buildings receiving sunlight) and maxh (to keep track of the tallest building encountered so far) are initialized. maxh is set to INT_MIN, representing the smallest possible integer, ensuring that the first building will always be considered as receiving sunlight.

• Iterating Through Buildings: The code then iterates through each building. For each building, its height num is read. If num is greater or equal to maxh, it means this building is taller than all previous buildings and will receive sunlight. ans is incremented, and maxh is updated to num.

• Output: After processing all buildings in a test case, the total count of buildings receiving sunlight (ans) is printed.

Time and Space Complexity Analysis

• Time Complexity: The solution has a time complexity of O(n) for each test case, where n is the number of buildings. This is because it involves a single linear scan through the array of building heights.

• Space Complexity: The space complexity is O(1), as the algorithm uses a fixed amount of additional memory regardless of the input size.

Key Points of the Algorithm

• Linear Scan: The algorithm's strength lies in its simplicity and efficiency, accomplished through a straightforward linear scan.
• No Extra Space: It efficiently uses constant extra space.
• Instantaneous Updates: The solution immediately updates the tallest building encountered, ensuring a swift determination of which buildings receive sunlight.

Conclusion

The provided solution is optimal for the given problem, offering an efficient and straightforward approach to identify buildings that receive sunlight.