Thomas Ngo

Software Engineer

3 minute read

Problem Statement

problem

Brute Force [TLE]

class Solution:
    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
        N = len(heights)
        res = []
        for alice, bob in queries:
            if alice > bob:
                alice, bob = bob, alice
            for left in range(bob, N):
                if alice == bob or heights[alice] < heights[bob]:
                    res.append(bob)
                    break
                if heights[left] > heights[alice] and heights[left] >= heights[bob]:
                    res.append(left)
                    break
            else:
                res.append(-1)
        return res

Editorial Solution

Approach 1: Monotonic Stack

  1. Prepare for Queries:

    • Initialize a stack (mono_stack) to keep track of building heights in decreasing order.
    • Create a result array initialized with -1 to store the answers for each query.
    • Group queries by their “b” value to process efficiently.

  2. Handle Simple Cases:

    • For each query, if the height of building “b” is greater than building “a” (or if they are the same), directly assign b as the result.

  3. Process Complex Cases with Monotonic Stack:

    • Traverse the heights array from right to left.
    • For each height, check pending queries:
      • Use binary search (search method) on the monotonic stack to find the appropriate leftmost building index for the current query.
    • Maintain the stack by removing heights smaller than the current height, ensuring it remains in decreasing order.

  4. Binary Search Helper:

    • The search method is used to find the leftmost building taller than the given height using binary search on the stack.

Complexity

  • Time Complexity:
    \(O(n + q \cdot \log(n))\)
    Where n is the number of buildings and q is the number of queries.
  • Space Complexity:
    \(O(n + q)\)
    For storing the stack and grouped queries.
class Solution:
    def leftmostBuildingQueries(self, heights, queries):
        mono_stack = []
        result = [-1 for _ in range(len(queries))]
        new_queries = [[] for _ in range(len(heights))]
        for i in range(len(queries)):
            a = queries[i][0]
            b = queries[i][1]
            if a > b:
                a, b = b, a
            if heights[b] > heights[a] or a == b:
                result[i] = b
            else:
                new_queries[b].append((heights[a], i))

        for i in range(len(heights) - 1, -1, -1):
            mono_stack_size = len(mono_stack)
            for a, b in new_queries[i]:
                position = self.search(a, mono_stack)
                if position < mono_stack_size and position >= 0:
                    result[b] = mono_stack[position][1]
            while mono_stack and mono_stack[-1][0] <= heights[i]:
                mono_stack.pop()
            mono_stack.append((heights[i], i))
        return result

    def search(self, height, mono_stack):
        left = 0
        right = len(mono_stack) - 1
        ans = -1
        while left <= right:
            mid = (left + right) // 2
            if mono_stack[mid][0] > height:
                ans = max(ans, mid)
                left = mid + 1
            else:
                right = mid - 1
        return ans

Approach 2: Priority Queue

  1. Initialization:

    • max_idx: A min-heap (priority queue) to store queries for efficient processing.
    • results: A list initialized with -1 to store the result for each query.
    • store_queries: A list of lists, where each inner list stores queries associated with a specific building index.

  2. Preprocessing Queries:

    • Iterate over each query (a, b):
      • If one building’s height is strictly less than the other and the order is satisfied (heights[a] < heights[b] or vice versa), directly assign the result.
      • If the heights are equal or no immediate result can be determined, store the query in store_queries based on the larger index of a or b.

  3. Processing Heights:

    • Traverse the heights list:
      • Resolve Pending Queries:
        • While the smallest height in the heap (max_idx[0]) is less than the current building’s height, it means the current building satisfies that query.
        • Pop such queries from the heap and assign the current index to the corresponding result in results.
      • Add New Queries:
        • Push queries from store_queries[idx] (associated with the current index) into the heap. Store them as tuples (max(height_a, height_b), query_index) for efficient processing.

  4. Return Results:

    • After processing all heights and queries, return the results list.
class Solution:
    def leftmostBuildingQueries(self, heights, queries):
        max_idx = []  # Min-heap to simulate priority queue
        results = [-1] * len(queries)
        store_queries = [[] for _ in heights]

        # Store the mappings for all queries in store_queries.
        for idx, query in enumerate(queries):
            a, b = query
            if a < b and heights[a] < heights[b]:
                results[idx] = b
            elif a > b and heights[a] > heights[b]:
                results[idx] = a
            elif a == b:
                results[idx] = a
            else:
                store_queries[max(a, b)].append(
                    (max(heights[a], heights[b]), idx)
                )

        for idx, height in enumerate(heights):
            # If the heap's smallest value is less than the current height, it is an answer to the query.
            while max_idx and max_idx[0][0] < height:
                _, q_idx = heapq.heappop(max_idx)
                results[q_idx] = idx
            # Push the queries with their maximum index as the current index into the heap.
            for element in store_queries[idx]:
                heapq.heappush(max_idx, element)

        return results

You may also enjoy