Leetcode # 2940. Find Building Where Alice and Bob Can Meet

Problem

https://leetcode.com/problems/find-building-where-alice-and-bob-can-meet

Given a, b

1. If a == b, let k = a = b
2. If heights[max(a, b)] > heights[min(a, b)] ⇒ ans = max(a, b)
3. K = set([k for k in range(len(heights)) if k > max(a, b) and heights[k] > max(heights[a], heights[b])])
   If K is ∅, ans = -1
   Otherwise, ans = min(K)

First Try
[Time Limit Exceeded  944 / 952 testcases passed]

class Solution:
  def leftmostBuildingQueries(self, \
      heights: List[int], queries: List[List[int]]) -> List[int]:
    ans = \
        [(max(a, b) \
        if heights[max(a, b)] > heights[min(a, b)] else -1) \
        if a != b else a for a, b in queries]
    meet_conditions = \
        sorted([(max(heights[a], heights[b]), max(a, b), i) \
        for i, (a, b) in enumerate(queries) \
        if ans[i] == -1], reverse=True)

    for i, height in enumerate(heights[1:], 1):
      for j in range(len(meet_conditions) - 1, -1, -1):
        if height <= meet_conditions[j][0]:
          continue
        if i > meet_conditions[j][1]:
          ans[meet_conditions[j][2]] = i
          meet_conditions.pop(j)
        
    return ans

Fixed Code

Line 16: continue break

Time Complexity: O(len(queries) * (log(len(queries)) + len(heights)))
Space Complexity: O(len(queries))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def leftmostBuildingQueries(self, \
      heights: List[int], queries: List[List[int]]) -> List[int]:
    ans = \
        [(max(a, b) \
        if heights[max(a, b)] > heights[min(a, b)] else -1) \
        if a != b else a for a, b in queries]
    meet_conditions = \
        sorted([(max(heights[a], heights[b]), max(a, b), i) \
        for i, (a, b) in enumerate(queries) \
        if ans[i] == -1], reverse=True)

    for i, height in enumerate(heights[1:], 1):
      for j in range(len(meet_conditions) - 1, -1, -1):
        if height <= meet_conditions[j][0]:
          break
        if i > meet_conditions[j][1]:
          ans[meet_conditions[j][2]] = i
          meet_conditions.pop(j)
        
    return ans

Last Updated on 2024/12/22 by A1go