Discussion on Jim and the Skyscrapers Challenge

Sort by

recency

|

76 Discussions

|

9 months ago+ 0 comments

def solve(arr):
    def counterAndPaths (n, arr):
        from collections import Counter
        counter = {key: count for key, count in Counter(arr).items() if count > 1}
        n += sum((count * (count - 1)) // 2 for count in counter.values())
        return n

    p = 0
    aux = [arr[0]]

    for a in arr[1:]:
        series = []
        if a > aux[-1]:
            while aux and aux[-1] < a:
                series.append(aux.pop())
        p = counterAndPaths(p, series)
        aux.append(a)

    p = counterAndPaths(p, aux)
    return 2 * p

2 years ago+ 0 comments

O(n) proposal
basically each element is visited ~twice

def solve(arr):
    
    arr += [math.inf]
    A = [math.inf]
    s = 0
    
    i = 0
    while i < len(arr):
        
        if (e:= arr[i]) <= A[-1]:
            A.append(e)
            i += 1
            continue
        
        n = 0
        v = A[-1]
        while A[-1] == v:
            A.pop()
            n+=1
        s += math.perm(n, 2)
        
    return s

2 years ago+ 1 comment

Succint python solution using priority queue and dictionary. O(N) runtime. O(N) space.

    import heapq as hq
    from collections import defaultdict
    pq = []
    d = defaultdict(lambda : 0)
    total = 0
    
    for n in arr:
        if n in d:
            total += 2 * d[n]
        while pq and n>pq[0]:
            d.pop(hq.heappop(pq), None)
        hq.heappush(pq, n)
        d[n] += 1
        
    return total

3 years ago+ 0 comments

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

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
    }
}

4 years ago+ 0 comments

my answer with O(n) time:

static long compute(long a) {
    return a * (a - 1);
  }
	
  public static long solve(List<Integer> arr) {
    long res = 0;
    Deque<long[]> st = new LinkedList<long[]>();
    Iterator<Integer> it = arr.iterator();
    long cur = it.next();
    long cnt = 1;

    while (it.hasNext()) {
      int next = it.next();
      if (next == cur) cnt++;
      else if (next < cur) {
        st.push(new long[] {cur, cnt});
        cur = next;
        cnt = 1;
      } else {
        res += compute(cnt);
        cur = next;
        cnt = 1;
        if (st.isEmpty()) continue;
        while (!st.isEmpty()) {
          long[] pre = st.peek();
          if (pre[0] < next) {
            st.remove();
            res += compute(pre[1]);
          } else if (pre[0] == next) {
            st.remove();
            cur = pre[0];
            cnt = pre[1] + 1;
            break;
          } else break;
        }
      }
    }
		
    res += compute(cnt);
    while (!st.isEmpty()) {
      long[] pre = st.pop();
      res += compute(pre[1]);
    }

    return res;
  }