Algorithm


Problem Name: Data Structures - Find Maximum Index Product

Problem Link: https://www.hackerrank.com/challenges/find-maximum-index-product/problem?isFullScreen=true

In this HackerRank in Data Structures - Find Maximum Index Product solutions

 

 

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;
}
Copy The Code & Try With Live Editor

#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;
}
Copy The Code & Try With Live Editor

#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;
    }
}
Copy The Code & Try With Live Editor

#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();
}
Copy The Code & Try With Live Editor

#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)
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Mr. X and His Shots solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Array Manipulation in Hackerrank - Hacerrank solution C, C++, java,js, Python