## Algorithm

Problem Name: Data Structures - Jim and the Skyscrapers

In this HackerRank in Data Structures - Jim and the Skyscrapers solutions

Jim has invented a new flying object called HZ42. HZ42 is like a broom and can only fly horizontally, independent of the environment. One day, Jim started his flight from Dubai's highest skyscraper, traveled some distance and landed on another skyscraper of same height! So much fun! But unfortunately, new skyscrapers have been built recently.

Let us describe the problem in one dimensional space. We have in total N skyscrapers aligned from left to right. The ith skyscraper has a height of hi. A flying route can be described as (i,j) with i not= j, which means, Jim starts his HZ42 at the top of the skyscraper i and lands on the skyscraper j. Since HZ42 can only fly horizontally, Jim will remain at the height hi only. Thus the path  (i,j) can be valid, only if each of the skyscrapers i, i + 1,...., j -1,j is not strictly greater than hi  and if the height of the skyscraper he starts from and arrives on have the same height.

Input Format

The first line contains N the number of skyscrapers. The next line contains N space separated integers representing the heights of the skyscrapers.

Output Format

Print an integer that denotes the number of valid routes.

Constraints

1 <= n <= 3 * 10 **5 and no skyscraper will have height greater than 10**6 and less than 1.

Sample Input #00

``````6
3 2 1 2 3 3
``````

Sample Output #00

``````8
``````

Sample Input #01

``````3
1 1000 1
``````

Sample Output #01

``````0
``````

Explanation

First testcase: (1, 5), (1, 6) (5, 6) and (2, 4) and the routes in the opposite directions are the only valid routes.

Second testcase: (1, 3) and (3, 1) could have been valid, if there wasn't a big skyscraper with height 1000 between them.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include
#include
#include

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.height);
reachable.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);
}
``````
Copy The Code &

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include
#include
#include
#include
using namespace std;

const int NMAX = 300010, CMAX = 1000010;

int N, V[NMAX], Right[NMAX];
stack S;
vector 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);
}
``````
Copy The Code &

### #3 Code Example with Java Programming

```Code - 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 stack = new Stack();
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);
}
}
.``````
Copy The Code &

### #4 Code Example with Javascript Programming

```Code - 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();
});

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] < num) stack.pop();
//console.log(stack)
if (stack.length && stack[stack.length-1] === num) {

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

return p*2;

}

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

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

let result = solve(arr);

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

ws.end();
}
``````
Copy The Code &

### #5 Code Example with Python Programming

```Code - 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] < h:
stack.pop()
if len(stack) > 0 and stack[-1] == h:
result += stack[-1]
stack[-1] = (stack[-1], stack[-1] + 1)
else:
stack.append((h, 1))

print(2 * result)
``````
Copy The Code &