HackerRank Find Maximum Index Product problem solution

In this HackerRank Find Maximum Index Product problem solution you are given a list of N numbers. we need to find out the maximum indexProduct(i) among all the products.

Problem solution in 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)  

Problem solution in 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;
    }
}

Problem solution in 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;
}

Problem solution in 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("0n");
    } 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=%dn",current,leftPos,right);
		                #endif
		                long int prod=leftPos*right;
		                if(prod>maxProd) maxProd=prod;
					}
                }
                current--;
            }
        }
        printf("%ldn",maxProd);
    }
    return 0;
}

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