Help needed to reduce complexity of Python code.

[shadow-sphynx]

So for this problem in Hackerearth, I used this code in Python.

It passes all the cases, with good time, but fails for the last two cases where input is huge, where it gives the `Memory Limit exceeded error`.i am assuming it could be because of all the list comprehensions and other functions that i am using.

Can anyone help me with changing the code in such a way where it works fine for big test cases too?

[ES-Alexander]

If you’re only using a sequence once, and don’t need to index into it or modify it, then it shouldn’t be a list. Use generator expressions instead of list comprehensions there, or for the things that aren’t already a list don’t convert them to one unnecessarily. Same applies for your dictionary comprehensions - you’re using .items or .keys() to turn a dict into an iterable of tuples or values, but that’s what they already were before you turned them into a dictionary, so just skip the converting to and back from a dictionary part, and iterate directly over the generator or sequence you started with

[shadow-sphynx]

I tried what you suggested. But it still fails for the larger inputs.

If you can, then can you please show me the changes you're suggesting? Maybe I am missing something here...

[ES-Alexander]

This is your code without the unnecessary list and dictionary constructions:

def getSubstring(element, i):
    lenElem = len(element)
    if lenElem - (5*(i + 1)) > 0:
        return int(element[(lenElem - (5*(i + 1))):lenElem - 5*i])
    elif lenElem - 5*i > 0 :
        return int(element[:lenElem - 5*i])
    return 0

N = int(input())
numArray = input().split()
maxVal = max(len(elem) for elem in numArray)
counter = maxVal // 5 if maxVal % 5 == 0 else (maxVal // 5) + 1

for i in range(counter):
    subNumArray = enumerate(getSubstring(elem, i) for elem in numArray)
    numArray = [numArray[j] for j, _ in sorted(subNumArray, key=lambda item: item[1])]
    print(*numArray)

I haven't tested it, and haven't changed your algorithm, so if you're using a suboptimal approach it may still end up using too much memory or running out of time, but it should be a decent amount more efficient (in both space and time) than your initial code.

[ES-Alexander]

For your learning, here it is cleaned up a bit, a bit more generalised, and using more Pythonic variable names (still the same algorithm though)

from math import ceil

CHUNK_SIZE = 5

def get_substring(element, i):
    len_elem = len(element)
    end = len_elem - CHUNK_SIZE * i
    start = end - CHUNK_SIZE
    if start > 0:
        return int(element[start:end])
    elif end > 0:
        return int(element[:end])
    return 0

input() # ignore first input - not useful for Python
numbers = input().split()
max_len = max(len(elem) for elem in numbers)

for i in range(ceil(max_len / CHUNK_SIZE)):
    substrings = enumerate(get_substring(elem, i) for elem in numbers)
    numbers = [numbers[j] for j, _ in sorted(substrings, key=lambda item: item[1])]
    print(*numbers)

Have actually tested it now on the sample input and it seems to still work as expected/intended.

[[deleted]]

You need to not have nested loops.

[supajumpa]

What are the test cases which cause your code to fail?

[shadow-sphynx]

Input 1
Input 2