Python Optimizating the Van sequence

Question

I am writing a code on python for the platform Coding Games . The code is about Van Eck's sequence and i pass 66% of the "tests". Everything is working as expected , the problem is that the process runs out of the time allowed. Yes , the code is slow. I am not a python writer and I would like to ask you if you could do any optimization on the piece of code and if your method is complex ( Complex,meaning if you will be using something along vectorized data ) and not just swap an if (because that is easily understandable) to give a good explanation for your choice . Here is my code for the problem

import sys
import math   

def LastSeen(array):

    startingIndex = 0 
    lastIndex = len(array) - 1 
    closestNum = 0    
    for startingIndex in range(len(array)-1,-1,-1):  
            if array[lastIndex] == array[startingIndex] and startingIndex != lastIndex :
                    closestNum = abs(startingIndex - lastIndex)
                    break

    array.append(closestNum)
    return closestNum


def calculateEck(elementFirst,numSeq):

    number = numSeq
    first = elementFirst
    result = 0
    sequence.append(first)
    sequence.append(0)
    number -= 2
    while number != 0 :
        result = LastSeen(sequence)
        number -= 1
    print(result)


firstElement = int(input())

numSequence = int(input())

sequence = []

calculateEck(firstElement,numSequence)

Answer 1

so here is my code without dictionaries. van_eck contains the sequence in the end. Usually I would use a dict to track the last position of each element to save runtime. Otherwise you would need to iterate over the list to find the last occurence which can take very long.

Instead of a dict, I simply initialized an array of sufficient size and use it like a dict. To determine its size keep in mind that all numbers in the van-eck sequence are either 0 or tell you how far away the last occurrence is. So the first n numbers of the sequence can never be greater than n. Hence, you can just give the array a length equal to the size of the sequence you want to have in the end.

-1 means the element was not there before.

DIGITS = 100

van_eck = [0]
last_pos = [0] + [-1] * DIGITS

for i in range(DIGITS):
    current_element = van_eck[i]
    if last_pos[current_element] == -1:
        van_eck.append(0)
    else:
        van_eck.append(i - last_pos[current_element])
    last_pos[current_element] = i