Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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[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);
}
#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);
}
#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();
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);
}
}
. #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();
});
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();
}
#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][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)