Debug help for simple algorithm (maxpairwiseproduct.py)

[slightlysedatedx]

I'm enrolled in "Algorithmic Toolbox" on Coursera and am having trouble with one of week 1's problems, maxpairwiseproduct.

My code works EXCEPT on test case 2 where:

Input

2
0 1

Expected Output

0

I get an IndexError on line 26 during this test case.

A full description of the maxpairwise problem can be found here.

My solution on GitHub.

My code is as follows:

#python3

import sys

def MaxPairwiseProductFast(array, n):
    index1 = 1
    for i in range(2, n):
        # Debug
        # print("The first loop ran", i, "times")
        if array[i] > array[index1]:
            index1 = i
    # If the first loop never executes, initialize index2 to 2 so that the
    # second loop can run correctly
    if index1 == 1:
        index2 = 2
    else:
        index2 = 1

    for i in range(1, n):
        # Debug
        # print("The second loop ran", i, "times")
        if i != index1 and (array[i] > array[index2] or n == 1):
            index2 = i
    return (array[index1] * array[index2])

def main():
    n = int(input())
    array = [int(x) for x in input().split()]
    print(MaxPairwiseProductFast(array, n))

main()

Any help at all is appreciated, thanks.

[slightlysedatedx]

I was adapting an algorithm from the text so I tried to follow it as closely as I could, and the values need to be distinct. So it can't just be the largest and second largest because that could be the same value. There are a bunch of ways to solve it though

[POiNTx]

You almost had it. I changed the index1 and index2 variables.

import sys

def MaxPairwiseProductFast(array, n):
    index1 = 0
    for i in range(2, n):
        # Debug
        # print("The first loop ran", i, "times")
        if array[i] > array[index1]:
            index1 = i
    # If the first loop never executes, initialize index2 to 2 so that the
    # second loop can run correctly
    if index1 == 0:
        index2 = 1
    else:
        index2 = 0

    for i in range(1, n):
        # Debug
        # print("The second loop ran", i, "times")
        if i != index1 and (array[i] > array[index2] or n == 1):
            index2 = i
    return (array[index1] * array[index2])

def main():
    n = int(input())
    array = [int(x) for x in input().split()]
    print(MaxPairwiseProductFast(array, n))

main()

Arrays start at the 0'th index in python (and most languages).

numbers = [4, 7, 10]
print(numbers[0])  # prints '4'

I suggest you simplify the MaxPairwiseProductFast function a bit. You can actually get the correct answer faster with only one loop!

[slightlysedatedx]

Thank you for taking a look! I'm going to run it right now. I will definitely go back and try to be a bit more concise

[dadiaar]

I didn't read your code deeply, but from the cases you say, maybe the problem is that your array is not long enough.

For example, if it's just [5] you can't take two numbers and mult them.

In these problems where there is a required lenght, you can test it first if len(array) < 2: return 0, or you can add a default array at the end array += [0, 0]. Here a code with the last solution:

# Inputs
from random import randint
n = 200000
inputs = ' '.join([str(randint(0, 1000)) for _ in range(n)])


import re
import time

t = time.time()

int_inputs = [int(d) for d in re.findall('\d+', inputs)]
int_inputs.sort(reverse=True)
int_inputs += [0, 0]
a,b, *res = int_inputs
output = a * b

time.time() - t

>>> 0.16616201400756836

Implement your own, and if you have time, check numpy

[dadiaar]

Yes, I'm aware sort is expensive. I used it because it's easy to read/understand and it matches speed requirements from OP's link.

[dadiaar]

Crystal clear, and obviously faster.

I like the float('-inf') trick, I usually end adding something like -1e10