We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Advanced
  4. Jim and the Skyscrapers
  5. Discussions

Jim and the Skyscrapers

Sort by

recency

|

75 Discussions

|

  • fuzzytruth
     + 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

  • wknb1996
     + 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

  • drdtr
     + 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
    }
}

  • vinctai
     + 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;
  }

  • sumikanth
     + 0 comments

    Here is my code with comments: 

    long long int solve(vector<int> arr) {
int n=arr.size();
int M[n];
long long int sum=0;
M[0]=-1;
//Create an Array M where M[i] is the index of the closest element to the left of arr[i] that is greater than or equal to arr[i]. If there is no such element let M[i]=-1
for(int i=1;i<n;i++){
  if(arr[i-1]>=arr[i])
  M[i]=i-1;
  else {
  int j=i-1;
  while(j>0&&arr[j]<arr[i]&&M[j]!=-1)
  j=M[j];
  M[i]=j;
  }
}
set<int>covered;
for(int i=n-1;i>0;i--){
    //If a particular series of elements have been covered make sure we don't cover the index i again
    if(covered.find(i)!=covered.end())
    continue;
    int j=i;
    long k=1;
    //Find the number of elements (k) where height is same and in between all elements are of lesser height
    while(j>0&&arr[M[j]]==arr[j]){
     k++;
     covered.insert(j);
     j=M[j]; 
    }
    //Add the number of ways of making pairs from k elements multiplied by 2 (bidirectional) to the overall sum
    sum=sum+(k*(k-1));
}
return sum;
}