Find Buildings With an Ocean View
Given a list of n buildings in a line, each building’s height is given in heights[] array. Find and return the indices (0-indexed) of buildings with an unobstructed “ocean view,” meaning they can see the ocean without taller buildings blocking their view to the right. The task is to return the indices (0-indexed) of the buildings that have an ocean view, sorted in increasing order.
Example:
Input: heights = {4,2,3,1}
Output: {0,2,3}Input: heights = {4,3,2,1}
Output: {0,1,2,3}
Approach:
The idea is to use a right-to-left approach, starting from the rightmost building and moving towards the left. Maintains a variable tallestBuildingSoFar or maxx to keep track of the tallest building encountered so far. For each building, checks if its height is greater than maxx. If it is, the building has an ocean view and its index is added to the result vector. The maxx is then updated to the current building’s height if it’s greater. After iterating through all the buildings, the result[] array contains the indices of the buildings with an ocean view in descending order. Therefore, the vector is reversed to get the indices in ascending order.
Steps-by-step approach:
- Create a variable tallestBuildingSoFar to keep track of the tallest building encountered from the right, starting with a minimum integer value.
- Iterate over the heights array from right to left using a for loop.
- For each building, check if it is taller than the tallest building encountered so far.
- If the current building is taller, add its index to the result[] array and update the tallestBuildingSoFar value.
- For each building, check if it is taller than the tallest building encountered so far.
- After iterating through all buildings, reverse the result[] array to get the indices in ascending order.
- Return the result[] array containing the indices of buildings with an ocean view.
Below are the implementation of the above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to find the buildings with an ocean view
vector<int> findOceanViewBuildings(vector<int>& heights)
{
// To store the indices of buildings with an ocean view
vector<int> result;
// Number of buildings
int n = heights.size();
// To keep track of the tallest building encountered so
// far from the right
int tallestBuildingSoFar = INT_MIN;
// Iterate over the heights array from right to left
for (int i = n - 1; i >= 0; i--) {
// If the current building is taller than the
// tallest building encountered so far
if (heights[i] > tallestBuildingSoFar) {
// Add the index of the current building to the
// result vector
result.push_back(i);
// Update the tallestBuildingSoFar
tallestBuildingSoFar
= max(tallestBuildingSoFar, heights[i]);
}
}
// The result vector contains the indices in descending
// order So, reverse the vector to get the indices in
// ascending order
reverse(result.begin(), result.end());
// Return the result vector
return result;
}
// Driver code
int main()
{
// Input array
vector<int> heights = { 1, 2, 3, -1, 2 };
// Number of buildings with an ocean view
int k = 3;
// Call the findOceanViewBuildings function and store
// the result
vector<int> result = findOceanViewBuildings(heights);
// Print the result
for (int i : result) {
cout << i << " ";
}
return 0;
}
import java.util.*;
public class Main {
// Function to find the buildings with an ocean view
public static List<Integer> findOceanViewBuildings(int[] heights) {
// To store the indices of buildings with an ocean view
List<Integer> result = new ArrayList<>();
// Number of buildings
int n = heights.length;
// To keep track of the tallest building encountered so
// far from the right
int tallestBuildingSoFar = Integer.MIN_VALUE;
// Iterate over the heights array from right to left
for (int i = n - 1; i >= 0; i--) {
// If the current building is taller than the
// tallest building encountered so far
if (heights[i] > tallestBuildingSoFar) {
// Add the index of the current building to the
// result list
result.add(i);
// Update the tallestBuildingSoFar
tallestBuildingSoFar = Math.max(tallestBuildingSoFar, heights[i]);
}
}
// The result list contains the indices in descending
// order So, reverse the list to get the indices in
// ascending order
Collections.reverse(result);
// Return the result list
return result;
}
// Driver code
public static void main(String[] args) {
// Input array
int[] heights = { 1, 2, 3, -1, 2 };
// Call the findOceanViewBuildings function and store
// the result
List<Integer> result = findOceanViewBuildings(heights);
// Print the result
for (int i : result) {
System.out.print(i + " ");
}
}
}
# Function to find the buildings with an ocean view
def findOceanViewBuildings(heights):
# To store the indices of buildings with an ocean view
result = []
# Number of buildings
n = len(heights)
# To keep track of the tallest building encountered so far from the right
tallestBuildingSoFar = float('-inf')
# Iterate over the heights array from right to left
for i in range(n - 1, -1, -1):
# If the current building is taller than the tallest building encountered so far
if heights[i] > tallestBuildingSoFar:
# Add the index of the current building to the result list
result.append(i)
# Update the tallestBuildingSoFar
tallestBuildingSoFar = max(tallestBuildingSoFar, heights[i])
# The result list contains the indices in descending order
# So, reverse the list to get the indices in ascending order
result.reverse()
# Return the result list
return result
# Driver code
if __name__ == "__main__":
# Input array
heights = [1, 2, 3, -1, 2]
# Call the findOceanViewBuildings function and store the result
result = findOceanViewBuildings(heights)
# Print the result
for i in result:
print(i, end=" ")
// Function to find the buildings with an ocean view
function findOceanViewBuildings(heights) {
// To store the indices of buildings with an ocean view
let result = [];
// To keep track of the tallest building encountered so far from the right
let tallestBuildingSoFar = Number.MIN_SAFE_INTEGER;
// Iterate over the heights array from right to left
for (let i = heights.length - 1; i >= 0; i--) {
// If the current building is taller than the tallest building encountered so far
if (heights[i] > tallestBuildingSoFar) {
// Add the index of the current building to the result list
result.push(i);
// Update the tallestBuildingSoFar
tallestBuildingSoFar = Math.max(tallestBuildingSoFar, heights[i]);
}
}
// The result list contains the indices in descending order
// So, reverse the list to get the indices in ascending order
result.reverse();
// Return the result list
return result;
}
// Driver code
function main() {
// Input array
const heights = [1, 2, 3, -1, 2];
// Call the findOceanViewBuildings function and store the result
const result = findOceanViewBuildings(heights);
// Print the result
console.log(result.join(" "));
}
// Invoke the main function
main();
Output
2 4
Time Complexity: O(n), where n is the number of buildings.
Auxililary Space: O(n)