Last active
September 16, 2023 14:48
-
-
Save lingpri/07d4df91ac3d3a077344e2aee514d8c5 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/bin/python3 | |
''' | |
Given the element [86, 74, 8, 74, 92, 44, 24] for the first pass, we find the element to the left of 86, which is empty, so we add 0 (-1 + 1 = 0) as the index to the left stack. | |
Given the element [86, 74, 8, 74, 92, 44, 24] for the second pass, we find the closest element to the left of 74, which is greater than 74, so we push index 1 with a value of 86 (0 + 1 = 1) to the left stack. | |
Given the element [86, 74, 8, 74, 92, 44, 24] for the third pass, we find the closest element to the left of 8, which is greater than 8, so we push index 2 (1 + 1 = 2) with value 74 as the index to the left stack. | |
Given the element [86, 74, 8, 74, 92, 44, 24] for the fourth pass, we find the closest element to the left of 74, which is greater than 74, so we push the index 0 with a value of 86 (0 + 1 =1) to the left stack. | |
Given the element [86, 74, 8, 74, 92, 44, 24] for the fifth pass, we find the closest element to the left of 92, which is greater than 92, so we push the index -1 with a value of None (-1 + 1 =0) to the left stack. | |
Given the element [86, 74, 8, 74, 92, 44, 24] for the sixth pass, we find the closest element to the left of 44, which is greater than 44, so we push the index 4 with a value of 92 (4 + 1 =5) to the left stack. | |
Given the element [86, 74, 8, 74, 92, 44, 24] for the seventh pass, we find the closest element to the left of 24, which is greater than 24, so we push the index 5 with a value of 44 (5 + 1 =6) to the left stack. | |
items compared on the left side of each stack [86, 74, 8, 74, 92, 44, 24]] | |
Elements of the left stack are [0, 1, 2, 1, 0, 5, 6] | |
values of the left stack are [None, 86, 74, 86, None, 92, 44] | |
''' | |
''' | |
2500100000 which is two billion five hundred million one hundred thousand. | |
Time Complexity: | |
, | |
also acceptable | |
Required Knowledge: Sparse Table and Binary Search OR Stacks | |
''' | |
import math | |
import os | |
import random | |
import re | |
import sys | |
def split_array(n, index): | |
left_array, right_array = [],[] | |
left_array = n[0:index] | |
right_array = n[index+1:len(n)] | |
return left_array,right_array | |
def get_left_closest_max_value(array, element): | |
for index, item in reversed(list(enumerate(array))): | |
if (item > element): | |
return index + 1 | |
return 0 | |
def get_right_closest_max_value(array, element,offset): | |
for index, item in enumerate(array): | |
if (item > element): | |
return index + offset + 2 | |
return 0 | |
def get_right_stack(randarr): | |
rightstack = [] | |
for i,item in enumerate(randarr): | |
left_array, right_array = split_array(randarr,i) | |
rightpos = get_right_closest_max_value(right_array,item,len(left_array)) | |
rightstack.append(rightpos) | |
return rightstack | |
def get_left_stack(randarr): | |
leftstack = [] | |
for i,item in enumerate(randarr): | |
left_array, right_array = split_array(randarr,i) | |
leftpos = get_left_closest_max_value(left_array, item) | |
leftstack.append(leftpos) | |
return leftstack | |
def solve(arr): | |
leftstack = get_left_stack(arr) | |
rightstack = get_right_stack(arr) | |
multiplied = list(map(lambda x, y: x * y, leftstack, rightstack)) | |
return max(multiplied) | |
if __name__ == '__main__': | |
fptr = open(os.environ['OUTPUT_PATH'], 'w') | |
arr_count = int(input().strip()) | |
arr = list(map(int, input().rstrip().split())) | |
print(arr) | |
result = solve(arr) | |
fptr.write(str(result) + '\n') | |
fptr.close() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Find Maximum Index Product has failed a few testcases 0, 5, 11 and 12 in hacker rank. I wonder how to optimize the code.
The problem is a preparation for a interview question https://www.hackerrank.com/challenges/find-maximum-index-product/problem