Katkat
Back

Solve three string/stack/backtracking problems

TikTokSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use a monotonic stack to determine visibility in a 2D line and backtracking to generate valid structural sequences.

Part 1: Buildings with View

Given an array heights of size n, representing buildings in a line, a building can see the ocean (to the right) if all buildings to its right are strictly shorter than it. Return the indices of all buildings that have an ocean view, in increasing order.

Example: Input: heights = [4, 2, 3, 1] Output: [0, 2, 3] Explanation: Building at index 0 (height 4) sees the ocean. Building at index 2 (height 3) sees it. Building at index 3 (height 1) sees it.

Part 2: Balanced Combinations

Given an integer n, generate all combinations of n pairs of balanced parentheses.

Example: Input: n = 2 Output: ["(())", "()()"]

Constraints

  • 1 <= n <= 10 for parentheses.
  • 1 <= heights.length <= 10^5.
  • heights[i] are positive integers.
  • Time complexity should be O(n) for the first part and O(4^n / sqrt(n)) for the second.

Hints

Hint 1

For the first problem, consider iterating from right to left while maintaining the maximum height seen so far.

Hint 2

For the parentheses problem, use a recursive backtracking approach to track the count of open and closed brackets placed so far.

Hint 3

Ensure that at any point in your recursive function, the number of closed brackets never exceeds the number of open brackets.

Follow-up questions

  • How would you modify the visibility problem if buildings could only see the ocean if they were strictly taller than the sum of all buildings to their right?
  • Can you solve the parentheses problem using an iterative approach instead of recursion?
  • What is the space complexity of your backtracking solution, and can you optimize it?