LEETCODE 1762 C SOLUTION : BUILDINGS WITH OCEAN VIEW

Welcome to our detailed walkthrough of LeetCode Problem 1762: "Buildings With an Ocean View". In this video, we'll dive deep into understanding the problem, discussing various approaches to solve it, and finally, we'll explore the most efficient algorithm to achieve the solution.
LeetCode Problem 1762 requires us to identify buildings in an array that have an ocean view. The array represents buildings of different heights, and the problem is to find which buildings, when looking towards the right, can see the ocean without any taller or equal-height building blocking the view.
Understanding the Problem
First, let's understand the problem statement in detail. We are given an array of integers where each element represents the height of a building. The task is to return a list of indices of buildings that have an unobstructed ocean view. A building has an ocean view if all the buildings to its right are shorter.
Approaches to Solve the Problem
We will discuss multiple approaches to solve this problem, ranging from the simplest brute-force method to more optimized solutions.
Brute-force Approach
In the brute-force approach, we compare each building with all the buildings to its right. For each building, if there is no taller building to its right, it is considered to have an ocean view. This approach has a time complexity of O(n^2) because we are comparing each building with every other building to its right. Although this approach is simple and straightforward, it is not efficient for large input sizes.
Optimized Approach Using a Stack
A more optimized approach involves using a stack data structure. The idea is to iterate through the array from right to left. We use a stack to keep track of buildings that have an ocean view. As we iterate, we compare the current building's height with the height of the building on top of the stack. If the current building is taller, it has an ocean view, and we add its index to the stack. Otherwise, we continue to the next building. This approach ensures that each building is processed only once, giving us a time complexity of O(n).
Detailed Walkthrough of the Optimized Approach
Let's break down the optimized approach step by step:
Initialization: Start by initializing an empty stack and a result list. The stack will help us keep track of buildings that can see the ocean.
Iterate from Right to Left: Traverse the array from right to left. This allows us to easily manage the buildings' visibility as we move towards the leftmost building.
Comparison and Stack Management: For each building, check if it is taller than the building on top of the stack. If it is, pop the stack until the current building is not taller than the building on the stack. This ensures that all buildings in the stack can see the ocean.
Adding to Result: If the stack is empty or the current building is taller than the top of the stack, add the current building's index to the result list.
Reverse Result: Since we traversed from right to left, the result list will be in reverse order. Reverse the list before returning it to get the correct order.
Example Walkthrough
Let's walk through an example to see how this works in practice.
Consider the array [4, 2, 3, 1]:
Start with an empty stack and an empty result list.
Traverse from right to left:
Building at index 3 (height 1): Stack is empty, so add index 3 to the result.
Building at index 2 (height 3): Current building is taller than the building in the stack, so add index 2 to the result.
Building at index 1 (height 2): Current building is not taller than the building in the stack, so skip it.
Building at index 0 (height 4): Current building is taller than the building in the stack, so add index 0 to the result.
The result list before reversing is [3, 2, 0]. After reversing, the final result is [0, 2, 3].
Conclusion
In this video, we covered the problem statement for LeetCode Problem 1762: "Buildings With an Ocean View". We discussed various approaches to solve the problem, starting with the brute-force method and moving to an optimized solution using a stack. The optimized approach significantly improves the efficiency by reducing the time complexity to O(n).
By the end of this video, you should have a clear understanding of how to approach this problem, how to implement the solution efficiently, and the reasoning behind using a stack for this particular problem. This method can be applied to similar problems where we need to process elements based on certain conditions and maintain a running list of qualified elements.
Thank you for watching! If you found this video helpful, please like and subscribe to our channel for more algorithm and data structure tutorials. Don't forget to hit the bell icon to get notified whenever we upload a new video. If you have any questions or suggestions, feel free to leave them in the comments below. Happy coding