Search code examples
pythonlisttime-complexityspace-complexity

The most time/space efficient way to list all indices in an object


I am looking for 2 algorithms for creating a list of all indices in a string/list/etc.

I am not familiar with how range works. It is my understanding that using range creates an additional list in memory, and this is what I am trying to avoid here.

  • The most time efficient algorithm
  • The most space efficient algorithm

My code for optimal time:

string = 'sentence'
indices = []
for i in range(len(string)):
    indices.append(i)

My code for optimal space:

string = 'sentence'
indices = []
string_len = len(string)
i = 0
while i < string_len:
    indices.append(i)
    i += 1

Solution

  • Optimal time and space:

    string = 'sentence'
    indices = range(len(string))        # Python 2
    indices = list(range(len(string)))  # Python 3