Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int findLeft(const int value,const int start,const int end,const int v[]) {
int result=start;
while(v[result] < =value && result>end) result--;
return result;
}
int findRight(const int value,const int start,const int v[]) {
int result=start;
while(v[result] < =value) result++;
return result;
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n; scanf("%d",&n);
if(n<3) {
// no need to compute anything, result is zero
printf("0\n");
} else {
// read the values
int v[n+1],l[n+1],leftMax=0;
for(int i=0;i < n;) {
scanf("%d ",&v[++i]>;
l[i]=leftMax; if(v[i]>leftMax) leftMax=v[i];
}
long int maxProd=0; // the current max product
long int rightPos,current; // actual start from right, current position
int rightMax=v[n]; // actual value of start right
current=n-1;
while(current>2 && v[current]>=rightMax) {
rightMax=v[current--];
}
rightPos=current+1;
if(current>=2) {
if(v[current]<l[current]) {
long int leftPos=findLeft(v[current],current-1,leftPos,v>;
long int prod=leftPos*rightPos;
if(prod>maxProd) maxProd=prod;
}
current--;
while(current>1 && (current-1)*rightPos>maxProd) {
int value=v[current];
if(value>=rightMax) {
// no right
rightMax=value; rightPos=current;
} else {
if(value<l[current]) {
long int right=findRight(value,current+1,v);
long int leftPos=findLeft(value,current-1,leftPos,v);
#ifdef DEBUG
printf("current=%d,left=%d,right=%d\n",current,leftPos,right>;
#endif
long int prod=leftPos*right;
if(prod>maxProd) maxProd=prod;
}
}
current--;
}
}
printf("%ld\n",maxProd);
}
return 0;
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair < int,int> pii;
double PI = acos(-1);
double EPS = 1e-7;
int INF = 1000000000;
LL INFLL = 1000000000000000000LL;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define input(in) freopen(in,"r",stdin)
#define output(out) freopen(out,"w",stdout)
#define MIN(a, b) (a) = min((a), (b))
#define MAX(a, b) (a) = max((a), (b))
#define RESET(a, b) memset(a,b,sizeof(a))
#define ALL(a) (a).begin(), (a).end()
#define SIZE(a) (int)a.size()
#define SORT(a) sort(ALL(a))
#define UNIQUE(a) (a).erase( unique( ALL(a) ), (a).end() )
#define FOR(a, b, c) for (int (a)=(b); (a) < =(c); (a)++)
#define FORD(a, b, c) for (int (a)=(b); (a)>=(c); (a)--)
#define FORIT(a, b) for (__typeof((b).begin()) a=(b).begin(); a!=(b).end(); a++)
int mx[8] = {-1,1,0,0,-1,-1,1,1};
int my[8] = {0,0,-1,1,-1,1,-1,1};
// ----- //
int x[100005];
int fl[100005];
int fr[100005];
int main()
{
int n;
scanf("%d",&n);
FOR(a,1,n)
{
scanf("%d",&x[a]);
}
x[0] = INF+1;
vector<int> stk;
stk.pb(0);
FOR(a,1,n) {
while(x[stk.back()] < = x[a]) {
stk.pop_back();
}
fl[a] = stk.back();
stk.pb(a);
}
stk.clear();
stk.pb(0);
FORD(a,n,1) {
while(x[stk.back()] < = x[a]) {
stk.pop_back();
}
fr[a] = stk.back();
stk.pb(a);
}
long long ans = 0;
FOR(a,1,n) {
MAX(ans,(LL)fl[a]*fr[a]);
}
cout << ans << endl;
}
#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 s = new Scanner(System.in);
int[] vals = Read(s);
int[] left = GetBounds(vals, -1);
int[] right = GetBounds(vals, 1);
long max = 0, prod;
for (int i = 0; i < vals.length; i++) {
prod = (long)left[i] * right[i];
if (prod > max) {
max = prod;
}
}
System.out.println(max);
}
public static int[] Read(Scanner s) {
int numVals = s.nextInt();
int[] vals = new int[numVals];
for (int i = 0; i < numVals; i++) {
vals[i] = s.nextInt();
}
return vals;
}
public static int[] GetBounds(int[] vals, int dir) {
int start, end, inc;
int[] bounds = new int[vals.length];
if (dir == 1) {
start = 0; end = vals.length; inc = 1;
} else {
start = vals.length - 1; end = -1; inc = -1;
}
Stack < Integer> bigger = new Stack<>();
for (int i = start; i != end; i += inc) {
while (!bigger.empty() && vals[bigger.peek()] < vals[i]) {
bounds[bigger.pop()] = i + 1;
}
bigger.push(i);
}
return bounds;
}
}
#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(arr) {
const left = new Array(arr.length).fill(0);
const right = new Array(arr.length).fill(0);
let stack = [];
for (let i = 0; i < arr.length; i += 1) {
while (stack.length) {
const index = stack.pop();
if (arr[i] < arr[index]) {
left[i] = index + 1;
stack.push(index);
break;
}
}
stack.push(i);
}
stack = [];
for (let i = arr.length - 1; i >= 0; i -= 1) {
while (stack.length) {
const index = stack.pop();
if (arr[i] < arr[index]) {
right[i] = index + 1;
stack.push(index);
break;
}
}
stack.push(i);
}
let max = 0;
for (let i = 0; i < arr.length; i += 1) {
max = Math.max(max, left[i] * right[i]);
}
return max;
}
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())
a=list(map(int,input().split()))
a.insert(0,None)
left={}
right={}
left[1]=0
right[n]=0
for i in range(2,n+1):
if a[i]==a[i-1]:
left[i]=left[i-1]
elif a[i] < a[i-1]:
left[i]=i-1
else:
if left[i-1]==0:
left[i]=0
else:
counter=i-1
while True:
leftNumber=a[left[counter]]
if left[counter]==1:
if a[1]>a[i]:
left[i]=1
else:
left[i]=0
break
if leftNumber==a[i]:
left[i]=left[left[counter]]
break
elif leftNumber>a[i]:
left[i]=left[counter]
break
else:
if left[left[counter]]==0:
left[i]=0
break
else:
counter=left[counter]
for i in range(n-1,0,-1):
if a[i]==a[i+1]:
right[i]=right[i+1]
elif a[i] < a[i+1]:
right[i]=i+1
else:
if right[i+1]==0:
right[i]=0
else:
counter=i+1
while True:
rightNumber=a[right[counter]]
if right[counter]==n:
if a[n]>a[i]:
right[i]=n
else:
right[i]=0
break
if rightNumber==a[i]:
right[i]=right[right[counter]]
break
elif rightNumber>a[i]:
right[i]=right[counter]
break
else:
if right[right[counter]]==0:
right[i]=0
break
else:
counter=right[counter]
maxProduct=0
for i in range(1,n):
product=left[i]*right[i]
if maxProduct < product:
maxProduct=product
print(maxProduct)