Buildings With an Ocean View - Leetcode 1762 - Python

NeetCodeIO · Intermediate ·⚡ Algorithms & Data Structures ·1y ago

Key Takeaways

The video demonstrates how to solve the Buildings With an Ocean View problem on Leetcode using a greedy solution and a monotonic stack, with a focus on systems design and algorithm design.

Full Transcript

Hey everyone, welcome back and let's write some more neat code today. So today, let's solve the problem buildings with an ocean view. The idea here is that we are given an array of heights. So this example shows 4, 2, 3, and 1. And they tell us that there's an ocean here on the right side. I'll draw that with like a little bit of blue. And all we want to know is how many or not just how many but which one of these buildings have a view of the ocean. They want us to return them in increasing order. So like the indices. So in this example well we have indices 0 1 2 3. How do we know if any of these buildings have a view of the ocean? Well, only buildings that don't have like an obstructed view. I think it'll make more sense if I just kind of draw them out. So, let's say this is building four. Next, we have building two. Next, we have building three uh with a height of three. And then, lastly, we have building one with a height of one. So, now it becomes kind of clear which one of these buildings have a view of the ocean. First, you could just look at the first building. As long as there isn't any building greater than or equal to the height of this one, then it has a view. So, you kind of just scan through the rest of the array. None of them are equal to or greater than four. So, this one is good. What about this one? Well, straight to the right of it, we have a building with a height of three. So, you can't really see the ocean. So, not this one. What about three? Well, to the right, we have a building of one. That's okay because we can see over that. And yes, we can see the ocean. And lastly, the last building. It doesn't really matter what the height of that is because nothing is in front of it. So, we're always going to be able to see the ocean from there. So, we see that these three buildings are the ones that can see the ocean. And we would return the indexes 0 2 and three in that order. Now, if you notice, I mean, you would always expect that the height of them is going to be in decreasing order. Once we filter out the buildings that can't see it, you would never expect there to be a building over here that's taller than the previous one because then this one would never be able to see the uh building. So, we expect that the heights of the buildings that we return are going to be strictly in decreasing order. They can't be equal because then of course one of them wouldn't be able to see but they should be in decreasing order and that is the case. We have four then three then one. One way to solve this problem is by using a stack and it's kind of a more like niche technique. It's called the monotonic stack and that is a very valid way to solve this problem. I won't be covering that one in this video because there's actually a easier way to do this and I guess you could call it the greedy solution. But you might have an idea of what it is. It's going to involve going through these not from left to right because if we do it left to right then for any given building like this one, we don't know if it can see the ocean unless we look at all the other buildings. And yes, you could do that with a stack, but a better way to do it would be from right to left because we know that this one can see uh the building or the sorry the water. And then we can in some sense just keep track of what's the tallest building we've seen because for any given building, we just want to know what's the tallest building to the right of it because that's what's going to allow us to determine if this building can actually see the water or not. Let's make this a bit more clear. So let's say that this is my array over here. We're going to iterate through this in reverse order. What we're going to do is uh let's say this one starting here. And let's say we have our output array. I'm just going to kind of initialize that like empty. But we're going to actually just initialize that with the last element. I think we're guaranteed that the input is going to be non-MP. So we're safe to do that. Just take the last uh index which is going to be the length minus one. And in this case, it's going to be four, I believe. And then we're just going to take four and initialize our array with that. And then we're going to start here at the second to last building. So from here on out, we're going to check, can this building see the water? Well, we would ask ourselves, what's the max building to the right of it? And in this case, it's two. So four is strictly greater than two. So okay, so this building is good. What do we do? Well, I'm going to take the index and append it here. So, three is going to be added here. Now, this might seem strange to you because we're kind of doing it in reverse order, but that's okay because yes, we are building this in reverse order, but at the end, we can take this and reverse it and then it should be in the order that we want. So, that's good. Now, the other thing to note is now I'm going to be over here. I'm at index 2 and I could be maintaining the max building I've seen before. And in this case, we know that that's four. So what I would say is three is not greater than four. So this building cannot see the ocean. That's fine. We skip it. We do not add the index 2 to our list. But another thing I want to kind of tell you is we don't actually have to maintain the max height separately because we know that the last building that we added to our array should be the max that we've seen so far because sort of like how uh the heights are going to be in strictly a decreasing order when we return them since this is in reverse these heights are going to be in strictly increasing order. And if what I'm saying right now doesn't make 100% sense, just think about it in terms of like the picture over here. We know that like if this building we did end up adding it to the array, we know that this is the max that we've seen so far because it has to be greater than the max that we had seen before that. And it's not. So that's okay. That means that the last one that we added here, three, index 3, is the one that has the max height. So four. Now, this one is not the one that we're going to add. So now we're going to move over here. We're at index one. We're going to compare it to the element at index three. Is five greater than four? Yes, it is. So now we take five or rather the index of five which is one and we add it here. This is the new maximum. The last one that we add here will be the max that we have seen so far running in the reverse direction. Now lastly we'll be here at index zero. Is one greater than the height at index one which is five? It is not. So now we're done. So what we determined is that the element here and here and here, these three can see the ocean. Everything else cannot. And since we're going through this in reverse order, we're collecting the indexes in reverse order. That's not what we want to do. We want to collect the indexes in the other order. So it's as simple as taking this array and reversing it, which is going to give us 1 3 4. And that's what we can return. So this way we can solve this problem in linear time and linear space I guess if you count the output here. But if you don't count it, it is constant space. So let's code this one up now. Okay. So mainly what we want to do is iterate over the input in reverse. So I'm going to say for I in range starting at not the last index but the second to last index length minus 2 going up until zero. So in Python we do negative 1 and iterating in reverse order. So make the incrementer negative 1. Before we even do that we want to initialize our result as an array and the height that we want to add to it is the last one. So we can take the length minus one initialize the result with that. We want to end up returning the result. But before we return it we're going to end up uh reversing it. So we can do that. And now all we have to do is actually fill in this loop here. And what we're going to do is if the current height, so height at index one is greater than the last height. So we can just take our array. We know it's non- empty now. So we take the array. The last index that we added in Python, you can get that with negative one. And so this is the index of that. The actual height is going to be in the heights array. So doing this if it's strictly greater. Don't make this greater than or equal. it has to be strictly greater. Then we can take the current height, the index of the current height and add it to the result. Just like that. So this is the whole code. It's easier than it looks. I just ran it and you can see it works and it's pretty efficient. If you found this helpful, check out neatcode.io for a lot more. Thanks for watching and I'll see you

Original Description

🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews 🧑‍💼 LinkedIn: https://www.linkedin.com/in/navdeep-singh-3aaa14161/ 🐦 Twitter: https://twitter.com/neetcode1 ⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf Problem Link: https://neetcode.io/problems/buildings-with-an-ocean-view 0:00 - Read the problem 0:30 - Drawing Explanation 7:30 - Coding Explanation leetcode 1762 #neetcode #leetcode #python
Watch on YouTube ↗ (saves to browser)
Sign in to unlock AI tutor explanation · ⚡30

Playlist

Uploads from NeetCodeIO · NeetCodeIO · 0 of 60

← Previous Next →
1 Leetcode 149 - Maximum Points on a Line - Python
Leetcode 149 - Maximum Points on a Line - Python
NeetCodeIO
 2 Design Linked List - Leetcode 707 - Python
Design Linked List - Leetcode 707 - Python
NeetCodeIO
 3 Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
NeetCodeIO
 4 Design Browser History - Leetcode 1472 - Python
Design Browser History - Leetcode 1472 - Python
NeetCodeIO
 5 Number of Good Paths - Leetcode 2421 - Python
Number of Good Paths - Leetcode 2421 - Python
NeetCodeIO
 6 Flip String to Monotone Increasing - Leetcode 926 - Python
Flip String to Monotone Increasing - Leetcode 926 - Python
NeetCodeIO
 7 Maximum Sum Circular Subarray - Leetcode 918 - Python
Maximum Sum Circular Subarray - Leetcode 918 - Python
NeetCodeIO
 8 Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
NeetCodeIO
 9 Concatenated Words - Leetcode 472 - Python
Concatenated Words - Leetcode 472 - Python
NeetCodeIO
 10 Data Stream as Disjoint Intervals - Leetcode 352 - Python
Data Stream as Disjoint Intervals - Leetcode 352 - Python
NeetCodeIO
 11 LFU Cache - Leetcode 460 - Python
LFU Cache - Leetcode 460 - Python
NeetCodeIO
 12 N-th Tribonacci Number - Leetcode 1137
N-th Tribonacci Number - Leetcode 1137
NeetCodeIO
 13 Best Team with no Conflicts - Leetcode 1626 - Python
Best Team with no Conflicts - Leetcode 1626 - Python
NeetCodeIO
 14 Greatest Common Divisor of Strings - Leetcode 1071 - Python
Greatest Common Divisor of Strings - Leetcode 1071 - Python
NeetCodeIO
 15 Shortest Path in a Binary Matrix - Leetcode 1091 - Python
Shortest Path in a Binary Matrix - Leetcode 1091 - Python
NeetCodeIO
 16 Insert into a Binary Search Tree - Leetcode 701 - Python
Insert into a Binary Search Tree - Leetcode 701 - Python
NeetCodeIO
 17 Delete Node in a BST - Leetcode 450 - Python
Delete Node in a BST - Leetcode 450 - Python
NeetCodeIO
 18 Shuffle the Array (Constant Space) - Leetcode 1470 - Python
Shuffle the Array (Constant Space) - Leetcode 1470 - Python
NeetCodeIO
 19 Fruits into Basket - Leetcode 904 - Python
Fruits into Basket - Leetcode 904 - Python
NeetCodeIO
 20 Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
NeetCodeIO
 21 Naming a Company - Leetcode 2306 - Python
Naming a Company - Leetcode 2306 - Python
NeetCodeIO
 22 As Far from Land as Possible - Leetcode 1162 - Python
As Far from Land as Possible - Leetcode 1162 - Python
NeetCodeIO
 23 Shortest Path with Alternating Colors - Leetcode 1129 - Python
Shortest Path with Alternating Colors - Leetcode 1129 - Python
NeetCodeIO
 24 Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
NeetCodeIO
 25 Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
NeetCodeIO
 26 Contains Duplicate II - Leetcode 219 - Python
Contains Duplicate II - Leetcode 219 - Python
NeetCodeIO
 27 Path with Maximum Probability - Leetcode 1514 - Python
Path with Maximum Probability - Leetcode 1514 - Python
NeetCodeIO
 28 Add to Array-Form of Integer - Leetcode 989 - Python
Add to Array-Form of Integer - Leetcode 989 - Python
NeetCodeIO
 29 Unique Paths II - Leetcode 63 - Python
Unique Paths II - Leetcode 63 - Python
NeetCodeIO
 30 Minimum Distance between BST Nodes - Leetcode 783 - Python
Minimum Distance between BST Nodes - Leetcode 783 - Python
NeetCodeIO
 31 Design Hashmap - Leetcode 706 - Python
Design Hashmap - Leetcode 706 - Python
NeetCodeIO
 32 Range Sum Query Immutable - Leetcode 303 - Python
Range Sum Query Immutable - Leetcode 303 - Python
NeetCodeIO
 33 Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
NeetCodeIO
 34 Middle of the Linked List - Leetcode 876 - Python
Middle of the Linked List - Leetcode 876 - Python
NeetCodeIO
 35 Course Schedule IV - Leetcode 1462 - Python
Course Schedule IV - Leetcode 1462 - Python
NeetCodeIO
 36 Single Element in a Sorted Array - Leetcode 540 - Python
Single Element in a Sorted Array - Leetcode 540 - Python
NeetCodeIO
 37 Capacity to Ship Packages - Leetcode 1011 - Python
Capacity to Ship Packages - Leetcode 1011 - Python
NeetCodeIO
 38 IPO - Leetcode 502 - Python
IPO - Leetcode 502 - Python
NeetCodeIO
 39 Minimize Deviation in Array - Leetcode 1675 - Python
Minimize Deviation in Array - Leetcode 1675 - Python
NeetCodeIO
 40 Longest Turbulent Array - Leetcode 978 - Python
Longest Turbulent Array - Leetcode 978 - Python
NeetCodeIO
 41 Last Stone Weight II - Leetcode 1049 - Python
Last Stone Weight II - Leetcode 1049 - Python
NeetCodeIO
 42 Construct Quad Tree - Leetcode 427 - Python
Construct Quad Tree - Leetcode 427 - Python
NeetCodeIO
 43 Find Duplicate Subtrees - Leetcode 652 - Python
Find Duplicate Subtrees - Leetcode 652 - Python
NeetCodeIO
 44 Sort an Array - Leetcode 912 - Python
Sort an Array - Leetcode 912 - Python
NeetCodeIO
 45 Ones and Zeroes - Leetcode 474 - Python
Ones and Zeroes - Leetcode 474 - Python
NeetCodeIO
 46 Remove Duplicates from Sorted Array II - Leetcode 80 - Python
Remove Duplicates from Sorted Array II - Leetcode 80 - Python
NeetCodeIO
 47 Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
NeetCodeIO
 48 Concatenation of Array - Leetcode 1929 - Python
Concatenation of Array - Leetcode 1929 - Python
NeetCodeIO
 49 Symmetric Tree - Leetcode 101 - Python
Symmetric Tree - Leetcode 101 - Python
NeetCodeIO
 50 Check Completeness of a Binary Tree - Leetcode 958 - Python
Check Completeness of a Binary Tree - Leetcode 958 - Python
NeetCodeIO
 51 Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
NeetCodeIO
 52 Find Peak Element - Leetcode 162 - Python
Find Peak Element - Leetcode 162 - Python
NeetCodeIO
 53 Accounts Merge - Leetcode 721 - Python
Accounts Merge - Leetcode 721 - Python
NeetCodeIO
 54 Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
NeetCodeIO
 55 Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
NeetCodeIO
 56 Number of Zero-Filled Subarrays - Leetcode 2348 - Python
Number of Zero-Filled Subarrays - Leetcode 2348 - Python
NeetCodeIO
 57 Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
NeetCodeIO
 58 Sqrt(x) - Leetcode 69 - Python
Sqrt(x) - Leetcode 69 - Python
NeetCodeIO
 59 Successful Pairs of Spells and Potions - Leetcode 2300 - Python
Successful Pairs of Spells and Potions - Leetcode 2300 - Python
NeetCodeIO
 60 Optimal Partition of String - Leetcode 2405 - Python
Optimal Partition of String - Leetcode 2405 - Python
NeetCodeIO

This video teaches how to solve the Buildings With an Ocean View problem on Leetcode using a greedy solution and a monotonic stack, with a focus on systems design and algorithm design. The problem involves determining which buildings can see the ocean based on their heights and the height of buildings to their right. The video provides a step-by-step solution to the problem, including iterating through the array of heights in reverse order and keeping track of the tallest building seen so far.

Key Takeaways
  1. Iterate through the array of heights in reverse order
  2. Keep track of the tallest building seen so far
  3. Determine if a building can see the ocean based on the height of the tallest building to its right
  4. Initialize result array with last height
  5. Fill in loop to add current height if greater than last height
  6. Reverse result array before returning
💡 The problem can be solved using a greedy solution by iterating through the array of heights in reverse order and keeping track of the tallest building seen so far.

Related AI Lessons

⚡
Bloom Filters, Explained Properly
Learn how Bloom filters work and their benefits, including tiny memory and blazing speed, in exchange for potential false positives.
Dev.to · Daksh Gargas
 ⚡
Prefix Sums: The Preprocessing Trick That Makes Range Queries Instant
Learn how prefix sums enable instant range queries in arrays, boosting performance in various applications
Medium · Programming
 ⚡
I Thought I Was Ready for the Interview — Then One Simple Math Question Destroyed Me
A simple math question can destroy a developer's interview, highlighting the importance of being prepared for unexpected questions
Medium · Programming
 ⚡
Week 2(Day 10): LeetCode Two Pointers(slow & fast): Remove Duplicates from Sorted Array (Brute…
Learn to remove duplicates from a sorted array using the two pointers technique, improving from brute force to optimized solutions
Medium · Python

Chapters (3)

Read the problem
0:30 Drawing Explanation
7:30 Coding Explanation
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →