Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

HackerRank Find Maximum Index Product problem solution

YASH PAL, 31 July 2024

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.

HackerRank Find Maximum Index Product problem solution

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

coding problems solutions

Post navigation

Previous post
Next post
  • Automating Image Format Conversion with Python: A Complete Guide
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes