HackerRank Jim and the Skyscrapers problem solution

In this HackerRank Jim and the Skyscrapers problem, the first line contains the number of skyscrapers. The next line contains space-separated integers representing the heights of the skyscrapers. print an integer that denotes the number of valid routes.

Problem solution in Python programming.

N = int(input())
heights = [int(x) for x in input().split()]

assert len(heights) == N

stack = []

result = 0

for h in heights:
    while len(stack) > 0 and stack[-1][0] < h:
        stack.pop()
    if len(stack) > 0 and stack[-1][0] == h:
        result += stack[-1][1]
        stack[-1] = (stack[-1][0], stack[-1][1] + 1) 
    else:
        stack.append((h, 1))
        
print(2 * result)
        

Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] arr = new int[n];
	for(int i=0; i < n;i++)
		arr[i] = sc.nextInt();
	
	Stack<Integer> stack = new Stack<Integer>();
	stack.add(0);
	long[] store = new long[n];
	long count =0;
	for(int i=1; i < n;i++){
		while(! stack.isEmpty() && arr[stack.peek()] < arr[i]){
			stack.pop();
		}
		if(! stack.isEmpty() && arr[stack.peek()] == arr[i]){
			store[i] = store[stack.pop()]+1;
			count += store[i];
		}
		stack.push(i);
	}
	System.out.println(count*2); 
    }
}

Problem solution in C++ programming.

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

const int NMAX = 300010, CMAX = 1000010;

int N, V[NMAX], Right[NMAX];
stack<int> S;
vector<int> Val[CMAX];
long long Ans;

int main()
{

    scanf("%i", &N);
    for(int i = 1; i <= N; ++ i)
    {
        scanf("%i", &V[i]);
        Val[V[i]].push_back(i);
    }

    V[N + 1] = CMAX;

    S.push(N + 1);
    for(int i = N; i; -- i)
    {
        while(!S.empty() && V[S.top()] <= V[i]) S.pop();
        Right[i] = S.top();
        S.push(i);
    }

    for(int i = CMAX - 1; i >= 1; -- i)
    {
        int Ptr = 0;
        for(int j = 0; j < Val[i].size(); )
        {
            while(Ptr < Val[i].size() && Val[i][Ptr] <= Right[ Val[i][j] ]) Ptr ++;
            int Len = Ptr - j;
            Ans += 1LL * Len * (Len - 1);
            j = Ptr;
        }
    }

    printf("%lld", Ans);
}

Problem solution in C programming.

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>

enum {
  size = 300000,
};

struct group {
  int height;
  int count;
};

struct group reachable[size];
int num_reachable;

int main() {
  int n;
  scanf("%d", &n);
  assert(n > 0);
  long long num_backwards = 0;
  scanf("%d", &reachable[0].height);
  reachable[0].count = 1;
  num_reachable = 1;
  for (int i = 1; i < n; i++) {
    int h;
    scanf("%d", &h);
    
    int a = 0, b = num_reachable;
    while (a < b) {
      const int m = a + (b - a) / 2;
      struct group* r = &reachable[m];
      if (r->height == h) {
       
        a = b = m;
      } else if (r->height > h) {
        
        a = m + 1;
      } else if (r->height < h) {
        
        b = m;
      }
    }
    struct group* g = &reachable[a];
    const bool found = a < num_reachable && g->height == h;
    if (found) {
      assert(g->height == h);
      
      num_backwards += g->count;
      
      g->count++;
    } else {
      
      assert(a == num_reachable || g->height < h);
      *g = (struct group){
        .height = h,
        .count = 1,
      };
    }
    num_reachable = a + 1;
  }
  printf("%lld\n", 2 * num_backwards);
}

Problem solution in JavaScript programming.

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

// Complete the solve function below.
function solve(nums) {
  const stack = [];
  let p = 0;

  for (const num of nums) {
    while (stack.length && stack[stack.length-1][0] < num) stack.pop();
    //console.log(stack)
    if (stack.length && stack[stack.length-1][0] === num) {

      p+=stack[stack.length-1][1];
      stack[stack.length-1][1]+=1;
    } else {
      stack.push([num,1])
    }
    //console.log(stack)
  }

  return p*2;

}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const arrCount = parseInt(readLine(), 10);

    const arr = readLine().split(' ').map(arrTemp => parseInt(arrTemp, 10));

    let result = solve(arr);

    ws.write(result + "\n");

    ws.end();
}