LeetCode in Kotlin

2940. Find Building Where Alice and Bob Can Meet

Hard

You are given a 0-indexed array heights of positive integers, where heights[i] represents the height of the i^th building.

If a person is in building i, they can move to any other building j if and only if i < j and heights[i] < heights[j].

You are also given another array queries where queries[i] = [a_i, b_i]. On the i^th query, Alice is in building a_i while Bob is in building b_i.

Return an array ans where ans[i] is the index of the leftmost building where Alice and Bob can meet on the i^th query. If Alice and Bob cannot move to a common building on query i, set ans[i] to -1.

Example 1:

Input: heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]

Output: [2,5,-1,5,2]

Explanation: In the first query, Alice and Bob can move to building 2 since heights[0] < heights[2] and heights[1] < heights[2].

In the second query, Alice and Bob can move to building 5 since heights[0] < heights[5] and heights[3] < heights[5].

In the third query, Alice cannot meet Bob since Alice cannot move to any other building.

In the fourth query, Alice and Bob can move to building 5 since heights[3] < heights[5] and heights[4] < heights[5].

In the fifth query, Alice and Bob are already in the same building.

For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet.

For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.

Example 2:

Input: heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]

Output: [7,6,-1,4,6]

Explanation: In the first query, Alice can directly move to Bob’s building since heights[0] < heights[7].

In the second query, Alice and Bob can move to building 6 since heights[3] < heights[6] and heights[5] < heights[6].

In the third query, Alice cannot meet Bob since Bob cannot move to any other building.

In the fourth query, Alice and Bob can move to building 4 since heights[3] < heights[4] and heights[0] < heights[4].

In the fifth query, Alice can directly move to Bob’s building since heights[1] < heights[6].

For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet.

For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.

Constraints:

1 <= heights.length <= 5 * 10⁴
1 <= heights[i] <= 10⁹
1 <= queries.length <= 5 * 10⁴
queries[i] = [a_i, b_i]
0 <= a_i, b_i <= heights.length - 1

Solution

import java.util.LinkedList
import kotlin.math.max

class Solution {
    fun leftmostBuildingQueries(heights: IntArray, queries: Array<IntArray>): IntArray {
        val n = heights.size
        val gr = IntArray(n)
        val l = LinkedList<Int>()
        l.offer(n - 1)
        gr[n - 1] = -1
        for (i in n - 2 downTo 0) {
            while (l.isNotEmpty() && heights[i] > heights[l.peek()]) {
                l.pop()
            }
            if (l.isNotEmpty()) {
                gr[i] = l.peek()
            } else {
                gr[i] = -1
            }
            l.push(i)
        }
        val ans = IntArray(queries.size)
        var i = 0
        for (a in queries) {
            val x = gr[a[0]]
            val y = gr[a[1]]
            if (a[0] == a[1]) {
                ans[i++] = a[0]
            } else if (a[0] < a[1] && heights[a[0]] < heights[a[1]]) {
                ans[i++] = a[1]
            } else if (a[1] < a[0] && heights[a[1]] < heights[a[0]]) {
                ans[i++] = a[0]
            } else if (x == -1 || y == -1) {
                ans[i++] = -1
            } else {
                var m = max(a[0], a[1])
                while (m < heights.size && m != -1 && (heights[m] <= heights[a[0]] || heights[m] <= heights[a[1]])) {
                    m = gr[m]
                }
                if (m >= heights.size || m == -1) {
                    ans[i++] = -1
                } else {
                    ans[i++] = m
                }
            }
        }
        return ans
    }
}

This site is open source. Improve this page.