Quite readable solution in Kotlin, with detailed explanation.

Problem

Given an array of heights of skyscrapers, you can fly from a skyscraper i to a skyscrapers j != i iff heights[i] == heights[j] and heights[i] > heights[k] for all k in [i + 1..j - 1].

Find the number of direct flying paths from skyscraper i to j, counting both cases i < j and i > j.

Solution

We use a monotonic queue/stack, see

• Monotonic Queue Summary
• Monotonic Queue Algorithms

Idea

• we traverse the array and store the numbers together with their frequency in a monotonic stack, observing the invariant that the numbers on the stack are strictly decreasing, with the smallest on top
• for each new array element ni = heights[i]:
  • we remove all elements on the stack that are smaller, until only elements greater than or equal ni remained on the stack, or the stack is empty.
  • if the stack is not empty and the peek element is equal to ni, then we can fly from the corresponding preceding skyscrapers to i so we increase the resulting path count by the count of occurrences of ni stored on the stack. We then also increase the count of occurrences of ni, because we just encountered another one.
  • if the peek element is larger, then we simply add ni with the initial occurrence count 1.
• After having counted all pairs, we double the result, because for every pair (i, j) we need to count both the forward path with i < j and the backward path with i > j.

Runtime

The runtime is O(n):

• each element ni of the input array would be considered only a constant number of times:
  • when processing it while traversing the array: we either add it to the stack, or modify its occurrence count on the stack. Also, there will be at most 1 peek operation on the stack.
  • considering the stack itself, we will have at most n pushes (at most 1 for each array element), and thus at most n removals.

Kotlin implementation

class JimAndSkyscrapers {
    fun countFlyingPaths(heights: Array<Int>): Long = calcNumPairsOrdered(heights) * 2

    private data class NumCount(val num: Int, var count: Int = 1)

    private fun calcNumPairsOrdered(nums: Array<Int>): Long {
        var count = 0L

        val monoStack = ArrayDeque<NumCount>()
        for (i in nums.indices) {
            val num = nums[i]
            while (monoStack.isNotEmpty() && monoStack.peek().num < num) monoStack.pop()

            val peek = monoStack.peek()
            if (peek != null && peek.num == num) {
                count += peek.count
                peek.count++
            } else {
                monoStack.push(NumCount(num))
            }
        }

        return count
    }
}