In this blog post, we’ll explore three different approaches to solving LeetCode Problem #1762, Buildings With an Ocean View. We’ll start with a brute-force method, then move to an optimized approach using a monotonic stack, and finally end with a clean and optimized linear traversal solution.

Problem Statement

Given an array heights where each element represents the height of a building in a row, return the indices of buildings that have an unobstructed view of the ocean. A building has an ocean view if all the buildings to its right are shorter. You must return the indices in left-to-right order.

Example

Input: heights = [4, 2, 3, 1]

Output: [0, 2, 3]

Explanation:

• Building 0 has a height of 4 and has an ocean view because there are no taller buildings to its right.
• Building 2 has a height of 3 and is taller than the building to its right (1).
• Building 3 has a height of 1 and is the last building, so it has an ocean view.

Approach 1: Brute-Force Solution

Strategy

For each building, check if all buildings to its right are shorter. If so, it has an ocean view. This requires a nested loop to compare the current building with every building on its right.

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int[] findBuildings(int[] heights) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < heights.length; i++) {
            boolean hasOceanView = true;
            for (int j = i + 1; j < heights.length; j++) {
                if (heights[j] >= heights[i]) {
                    hasOceanView = false;
                    break;
                }
            }
            if (hasOceanView) {
                result.add(i);
            }
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

Time Complexity

• O(n²), where n is the number of buildings. Each building is compared with every other building to its right.

Space Complexity

• O(1) (excluding the output list), as we only use a few extra variables.

Pros and Cons

• Pros: Straightforward and easy to understand.
• Cons: Inefficient for large inputs due to the quadratic time complexity.

Approach 2: Using a Monotonic Stack

Strategy

Instead of comparing each building to every other building on its right, we can use a monotonic decreasing stack. We traverse the array from right to left, pushing indices onto the stack. If a building is taller than the building represented by the top of the stack, it has an ocean view.

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {
            public int[] findBuildings(int[] heights) {
            Stack<Integer> stack = new Stack<>();
 // Traverse buildings from right to left
            for (int i = heights.length - 1; i >= 0; i--) {
      // If current building is taller than any building in the stack
                if (stack.isEmpty() || heights[i] > heights[stack.peek()]) {
                    stack.add(i);
                }
            }
            Collections.reverse(stack);
            return stack.stream().mapToInt(Integer::intValue).toArray();
        }
}

Time Complexity

• O(n), where n is the number of buildings. Each building is processed at most once.

Space Complexity

• O(n), as we use a stack to store the indices of buildings with an ocean view.

Pros and Cons

• Pros: Efficient with linear time complexity.
• Cons: Slightly more complex to implement and understand compared to brute force.

Approach 3: Optimized Linear Traversal

Strategy

We can solve this problem even more efficiently by traversing the array once from right to left while keeping track of the maximum height encountered so far. If the current building is taller than the maximum height, it has an ocean view.

Code

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    public int[] findBuildings(int[] heights) {
        List<Integer> result = new ArrayList<>();
        int maxHeight = 0;
// Traverse buildings from right to left
        for (int i = heights.length - 1; i >= 0; i--) {
            // If the current building is taller than all to its right
            if (heights[i] > maxHeight) {
                result.add(i);
                maxHeight = heights[i];
            }
        }
// Reverse the result list to get indices in left-to-right order
        Collections.reverse(result);
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

Time Complexity

• O(n), where n is the number of buildings. Each building is traversed exactly once.

Space Complexity

• O(1) (excluding the output array), since only a few variables are used.

Pros and Cons

• Pros: Clean, efficient, and easy to implement.
• Cons: No significant cons for this specific problem.

Comparison of the Three Approaches

Conclusion

For LeetCode Problem 1762, the optimized linear traversal is the best solution due to its simplicity and efficiency. However, understanding the brute-force and monotonic stack approaches is essential as they provide valuable insights into tackling similar problems.

If you found this post helpful, consider sharing it with others who are preparing for coding interviews!

Happy coding! 😊 Please Like , Comment
🤖 ProTip

Important to understand the pattern and core syntax and use of monotonic stack

( A monotonic stack is a special type of stack data structure that maintains its elements in a specific order—either increasing or decreasing. The primary use of a monotonic stack is to efficiently find the next or previous greater/smaller element in a list, making it a powerful tool for problems related to array traversal and maintaining a dynamic order of elements.)
Using Monotonic stack you can solve below problems:

1. Next Greater Element Problem: Find the next element that is greater than each element in an array.
2. Trapping Rain Water Problem: Calculate trapped water in an elevation map using a stack to store heights.
3. Buildings With an Ocean View: Identify buildings that have a clear view by keeping track of visible buildings using a decreasing stack.
4. Stock Span Problem: Determine the number of consecutive days a stock price was less than or equal to the current day’s price.