Find Building Where Alice and Bob Can Meet solution and explanation

def findMeetBuilding(heights, queries):
    n = len(heights)
    next_greater = [n] * n
    stack = []

    for i in range(n-1, -1, -1):
        while stack and heights[stack[-1]] <= heights[i]:
            stack.pop()
        if stack:
            next_greater[i] = stack[-1]
        stack.append(i)

    ans = []
    for a, b in queries:
        meet = next_greater[a]
        while meet < n and meet <= b and next_greater[b] != meet:
            meet = next_greater[meet]
        ans.append(meet if meet < n and meet <= b else -1)

    return ans

import java.util.*;

class Solution {
    public int[] findMeetBuilding(int[] heights, int[][] queries) {
        int n = heights.length;
        int[] nextGreater = new int[n];
        Arrays.fill(nextGreater, n);
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = n - 1; i >= 0; --i) {
            while (!stack.isEmpty() && heights[stack.peek()] <= heights[i]) {
                stack.pop();
            }
            if (!stack.isEmpty()) {
                nextGreater[i] = stack.peek();
            }
            stack.push(i);
        }

        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; ++i) {
            int a = queries[i][0], b = queries[i][1];
            int meet = nextGreater[a];
            while (meet < n && meet <= b && nextGreater[b] != meet)
                meet = nextGreater[meet];
            ans[i] = (meet < n && meet <= b) ? meet : -1;
        }
        return ans;
    }
}

#include <vector>
#include <stack>
using namespace std;

vector<int> findMeetBuilding(vector<int>& heights, vector<vector<int>>& queries) {
    int n = heights.size();
    vector<int> nextGreater(n, n);
    stack<int> s;
    for (int i = n - 1; i >= 0; --i) {
        while (!s.empty() && heights[s.top()] <= heights[i]) s.pop();
        if (!s.empty()) nextGreater[i] = s.top();
        s.push(i);
    }
    vector<int> ans;
    for (const auto& q : queries) {
        int a = q[0], b = q[1];
        int meet = nextGreater[a];
        while (meet < n && meet <= b && nextGreater[b] != meet) 
            meet = nextGreater[meet];
        ans.push_back((meet < n && meet <= b) ? meet : -1);
    }
    return ans;
}

function findMeetBuilding(heights, queries) {
    const n = heights.length;
    const nextGreater = Array(n).fill(n);
    const stack = [];

    for (let i = n - 1; i >= 0; i--) {
        while (stack.length && heights[stack[stack.length - 1]] <= heights[i]) {
            stack.pop();
        }
        if (stack.length) {
            nextGreater[i] = stack[stack.length - 1];
        }
        stack.push(i);
    }

    const ans = [];
    for (const [a, b] of queries) {
        let meet = nextGreater[a];
        while (meet < n && meet <= b && nextGreater[b] != meet) {
            meet = nextGreater[meet];
        }
        ans.push(meet < n && meet <= b ? meet : -1);
    }
    return ans;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* findMeetBuilding(int* heights, int heightsSize, int** queries, int queriesRowSize, int* queriesColSize, int* returnSize) {
    *returnSize = queriesRowSize;
    int* ans = (int*)malloc(sizeof(int) * queriesRowSize);
    int* nextGreater = (int*)malloc(sizeof(int) * heightsSize);
    int* stack = (int*)malloc(sizeof(int) * heightsSize);
    int top = -1;

    for (int i = heightsSize - 1; i >= 0; i--) {
        while (top != -1 && heights[stack[top]] <= heights[i]) {
            top--;
        }
        nextGreater[i] = (top == -1) ? heightsSize : stack[top];
        stack[++top] = i;
    }

    for (int i = 0; i < queriesRowSize; ++i) {
        int a = queries[i][0];
        int b = queries[i][1];
        int meet = nextGreater[a];
        while (meet < heightsSize && meet <= b && nextGreater[b] != meet) {
            meet = nextGreater[meet];
        }
        ans[i] = (meet < heightsSize && meet <= b) ? meet : -1;
    }

    free(nextGreater);
    free(stack);
    return ans;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int[] FindMeetBuilding(int[] heights, int[][] queries) {
        int n = heights.Length;
        int[] nextGreater = new int[n];
        Array.Fill(nextGreater, n);
        Stack<int> stack = new Stack<int>();

        for (int i = n - 1; i >= 0; --i) {
            while (stack.Count > 0 && heights[stack.Peek()] <= heights[i]) {
                stack.Pop();
            }
            if (stack.Count > 0) {
                nextGreater[i] = stack.Peek();
            }
            stack.Push(i);
        }

        int[] ans = new int[queries.Length];
        for (int i = 0; i < queries.Length; ++i) {
            int a = queries[i][0], b = queries[i][1];
            int meet = nextGreater[a];
            while (meet < n && meet <= b && nextGreater[b] != meet)
                meet = nextGreater[meet];
            ans[i] = (meet < n && meet <= b) ? meet : -1;
        }
        return ans;
    }
}

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b) {
    return (*(int**)a)[1] - (*(int**)b)[1];
}

int binarySearch(int** buildings, int size, int start, int height) {
    int left = start, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (buildings[mid][1] > height) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int* findMeetBuilding(int* heights, int heightsSize, int** queries, int queriesRowSize, int* queriesColSize, int* returnSize) {
    *returnSize = queriesRowSize;
    int* ans = (int*)malloc(sizeof(int) * queriesRowSize);
    int** buildings = (int**)malloc(heightsSize * sizeof(int*));
    for (int i = 0; i < heightsSize; i++) {
        buildings[i] = (int*)malloc(2 * sizeof(int));
        buildings[i][0] = i; // index
        buildings[i][1] = heights[i]; // height
    }

    qsort(buildings, heightsSize, sizeof(int*), compare);

    for (int i = 0; i < queriesRowSize; ++i) {
        int a = queries[i][0];
        int b = queries[i][1];
        int posA = binarySearch(buildings, heightsSize, a+1, heights[a]);
        int posB = binarySearch(buildings, heightsSize, b+1, heights[b]);
        if (posA < heightsSize && posB < heightsSize && posA == posB && buildings[posA][0] > b) {
            ans[i] = buildings[posA][0];
        } else {
            ans[i] = -1;
        }
    }

    for (int i = 0; i < heightsSize; i++) {
        free(buildings[i]);
    }
    free(buildings);
    return ans;
}

class BinaryIndexedTree {
    private n: number;
    private c: number[];
    private inf: number = 1 << 30;

    constructor(n: number) {
        this.n = n;
        this.c = Array(n + 1).fill(this.inf);
    }

    update(x: number, v: number): void {
        while (x <= this.n) {
            this.c[x] = Math.min(this.c[x], v);
            x += x & -x;
        }
    }

    query(x: number): number {
        let mi = this.inf;
        while (x > 0) {
            mi = Math.min(mi, this.c[x]);
            x -= x & -x;
        }
        return mi === this.inf ? -1 : mi;
    }
}

function leftmostBuildingQueries(heights: number[], queries: number[][]): number[] {
    const n = heights.length;
    const m = queries.length;
    for (const q of queries) {
        if (q[0] > q[1]) {
            [q[0], q[1]] = [q[1], q[0]];
        }
    }
    const idx: number[] = Array(m)
        .fill(0)
        .map((_, i) => i);
    idx.sort((i, j) => queries[j][1] - queries[i][1]);
    const tree = new BinaryIndexedTree(n);
    const ans: number[] = Array(m).fill(-1);
    const s = [...heights];
    s.sort((a, b) => a - b);
    const search = (x: number) => {
        let [l, r] = [0, n];
        while (l < r) {
            const mid = (l + r) >> 1;
            if (s[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    };
    let j = n - 1;
    for (const i of idx) {
        const [l, r] = queries[i];
        while (j > r) {
            const k = n - search(heights[j]) + 1;
            tree.update(k, j);
            --j;
        }
        if (l === r || heights[l] < heights[r]) {
            ans[i] = r;
        } else {
            const k = n - search(heights[l]);
            ans[i] = tree.query(k);
        }
    }
    return ans;
}

const inf int = 1 << 30

type BinaryIndexedTree struct {
	n int
	c []int
}

func NewBinaryIndexedTree(n int) BinaryIndexedTree {
	c := make([]int, n+1)
	for i := range c {
		c[i] = inf
	}
	return BinaryIndexedTree{n: n, c: c}
}

func (bit *BinaryIndexedTree) update(x, v int) {
	for x <= bit.n {
		bit.c[x] = min(bit.c[x], v)
		x += x & -x
	}
}

func (bit *BinaryIndexedTree) query(x int) int {
	mi := inf
	for x > 0 {
		mi = min(mi, bit.c[x])
		x -= x & -x
	}
	if mi == inf {
		return -1
	}
	return mi
}

func leftmostBuildingQueries(heights []int, queries [][]int) []int {
	n, m := len(heights), len(queries)
	for _, q := range queries {
		if q[0] > q[1] {
			q[0], q[1] = q[1], q[0]
		}
	}
	idx := make([]int, m)
	for i := range idx {
		idx[i] = i
	}
	sort.Slice(idx, func(i, j int) bool { return queries[idx[j]][1] < queries[idx[i]][1] })
	s := make([]int, n)
	copy(s, heights)
	sort.Ints(s)
	ans := make([]int, m)
	tree := NewBinaryIndexedTree(n)
	j := n - 1
	for _, i := range idx {
		l, r := queries[i][0], queries[i][1]
		for ; j > r; j-- {
			k := n - sort.SearchInts(s, heights[j]) + 1
			tree.update(k, j)
		}
		if l == r || heights[l] < heights[r] {
			ans[i] = r
		} else {
			k := n - sort.SearchInts(s, heights[l])
			ans[i] = tree.query(k)
		}
	}
	return ans
}