Skip to main content
Code Review

Return to Answer

replaced http://codereview.stackexchange.com/ with https://codereview.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

Time limit exceeded

When a solution is too slow, it's typically because the algorithm is one or more orders of magnitude worse than intended for the challenges. So take a hard look at the time complexity of the implementation.

In your implementation, it all comes down to this expression:

sorted(set(x+"%d"%(k.count(x)) for x in k))

  • k.count(x) : the centerpiece of the expression, to find the count of some value in a list. The count function does this by iterating over all elements k, and checking each for equality with x. Time complexity: \$O(N)\$, where N is the number of items in k

  • ... for x in k : do something for each item in k. Again, \$O(N)\$, where N is the number of items in k

  • set(...) : probably \$O(N)\$

  • sorted(...) : probably \$O(N\log(N))\$

In total that gives: \$O(N^2) + O(N) + O(N\log(N))\$

Can this be better?

  • You need to sort, that's for sure. That's fast enough.

  • Do you really need a set? You used a set because the previous operations generate a list with duplicates. Using a set to remove duplicates is fine, but I would question why are duplicates at all in the first place.

  • The previous two items actually don't even matter. It's the slowest operation in the \$O(N^2) + O(N) + O(N\log(N))\$ that will drag everything down, the \$O(N^2)\$, so that's what you really need to optimize.

Instead of iterating over every account number for each account number, you could iterate only once, building a dictionary with counts along the way:

def print_sorted_with_count(accounts):
    counts = {}
    for account in accounts:
        counts[account] = counts.get(account, 0) + 1
    for account, count in sorted(counts.items()):
        print('{} {}'.format(account, count))

This implementation reduces the time complexity from \$O(N^2)\$ to \$O(N)\$, and also gets rid of an \$O(N)\$ operation (no more need for the set.)

UPDATE

As @abarnert@abarnert pointed out, the dictionary of counts can be created with a single expression using collections.Counter, so the above code can become simply:

from collections import Counter


def print_sorted_with_count(accounts):
    counts = Counter(accounts)
    for account, count in sorted(counts.items()):
        print('{} {}'.format(account, count))

Naming

The variable names in the posted code are horrible, and it makes it very hard to read. Avoid single-letter variable names, try to use descriptive names.

Coding style

I suggest to follow the recommendations of PEP8.

Time limit exceeded

When a solution is too slow, it's typically because the algorithm is one or more orders of magnitude worse than intended for the challenges. So take a hard look at the time complexity of the implementation.

In your implementation, it all comes down to this expression:

sorted(set(x+"%d"%(k.count(x)) for x in k))

  • k.count(x) : the centerpiece of the expression, to find the count of some value in a list. The count function does this by iterating over all elements k, and checking each for equality with x. Time complexity: \$O(N)\$, where N is the number of items in k

  • ... for x in k : do something for each item in k. Again, \$O(N)\$, where N is the number of items in k

  • set(...) : probably \$O(N)\$

  • sorted(...) : probably \$O(N\log(N))\$

In total that gives: \$O(N^2) + O(N) + O(N\log(N))\$

Can this be better?

  • You need to sort, that's for sure. That's fast enough.

  • Do you really need a set? You used a set because the previous operations generate a list with duplicates. Using a set to remove duplicates is fine, but I would question why are duplicates at all in the first place.

  • The previous two items actually don't even matter. It's the slowest operation in the \$O(N^2) + O(N) + O(N\log(N))\$ that will drag everything down, the \$O(N^2)\$, so that's what you really need to optimize.

Instead of iterating over every account number for each account number, you could iterate only once, building a dictionary with counts along the way:

def print_sorted_with_count(accounts):
    counts = {}
    for account in accounts:
        counts[account] = counts.get(account, 0) + 1
    for account, count in sorted(counts.items()):
        print('{} {}'.format(account, count))

This implementation reduces the time complexity from \$O(N^2)\$ to \$O(N)\$, and also gets rid of an \$O(N)\$ operation (no more need for the set.)

UPDATE

As @abarnert pointed out, the dictionary of counts can be created with a single expression using collections.Counter, so the above code can become simply:

from collections import Counter


def print_sorted_with_count(accounts):
    counts = Counter(accounts)
    for account, count in sorted(counts.items()):
        print('{} {}'.format(account, count))

Naming

The variable names in the posted code are horrible, and it makes it very hard to read. Avoid single-letter variable names, try to use descriptive names.

Coding style

I suggest to follow the recommendations of PEP8.

Time limit exceeded

When a solution is too slow, it's typically because the algorithm is one or more orders of magnitude worse than intended for the challenges. So take a hard look at the time complexity of the implementation.

In your implementation, it all comes down to this expression:

sorted(set(x+"%d"%(k.count(x)) for x in k))

  • k.count(x) : the centerpiece of the expression, to find the count of some value in a list. The count function does this by iterating over all elements k, and checking each for equality with x. Time complexity: \$O(N)\$, where N is the number of items in k

  • ... for x in k : do something for each item in k. Again, \$O(N)\$, where N is the number of items in k

  • set(...) : probably \$O(N)\$

  • sorted(...) : probably \$O(N\log(N))\$

In total that gives: \$O(N^2) + O(N) + O(N\log(N))\$

Can this be better?

  • You need to sort, that's for sure. That's fast enough.

  • Do you really need a set? You used a set because the previous operations generate a list with duplicates. Using a set to remove duplicates is fine, but I would question why are duplicates at all in the first place.

  • The previous two items actually don't even matter. It's the slowest operation in the \$O(N^2) + O(N) + O(N\log(N))\$ that will drag everything down, the \$O(N^2)\$, so that's what you really need to optimize.

Instead of iterating over every account number for each account number, you could iterate only once, building a dictionary with counts along the way:

def print_sorted_with_count(accounts):
    counts = {}
    for account in accounts:
        counts[account] = counts.get(account, 0) + 1
    for account, count in sorted(counts.items()):
        print('{} {}'.format(account, count))

This implementation reduces the time complexity from \$O(N^2)\$ to \$O(N)\$, and also gets rid of an \$O(N)\$ operation (no more need for the set.)

UPDATE

As @abarnert pointed out, the dictionary of counts can be created with a single expression using collections.Counter, so the above code can become simply:

from collections import Counter


def print_sorted_with_count(accounts):
    counts = Counter(accounts)
    for account, count in sorted(counts.items()):
        print('{} {}'.format(account, count))

Naming

The variable names in the posted code are horrible, and it makes it very hard to read. Avoid single-letter variable names, try to use descriptive names.

Coding style

I suggest to follow the recommendations of PEP8.

added 1208 characters in body
Source Link
janos
janos
  • 111.7k
  • 15
  • 152
  • 391

Time limit exceeded

When a solution is too slow, it's typically because the algorithm is one or more orders of magnitude worse than intended for the challenges. So take a hard look at the time complexity of the implementation.

In your implementation, it all comes down to this expression:

sorted(set(x+"%d"%(k.count(x)) for x in k))

  • k.count(x) : the centerpiece of the expression, to find the count of some value in a list. The count function does this by iterating over all elements k, and checking each for equality with x. Time complexity: \$O(N)\$, where N is the number of items in k

  • ... for x in k : do something for each item in k. Again, \$O(N)\$, where N is the number of items in k

  • set(...) : probably \$O(N)\$

  • sorted(...) : probably \$O(N\log(N))\$

In total that gives: \$O(N^2) + O(N) + O(N\log(N))\$

Can this be better?

  • You need to sort, that's for sure. That's fast enough.

  • Do you really need a set? You used a set because the previous operations generate a list with duplicates. Using a set to remove duplicates is fine, but I would question why are duplicates at all in the first place.

  • The previous two items actually don't even matter. It's the slowest operation in the \$O(N^2) + O(N) + O(N\log(N))\$ that will drag everything down, the \$O(N^2)\$, so that's what you really need to optimize.

Instead of iterating over every account number for each account number, you could iterate only once, building a dictionary with counts along the way:

def print_sorted_with_count(accounts):
    counts = {}
    for account in accounts:
        counts[account] = counts.get(account, 0) + 1
    for account, count in sorted(counts.items()):
        print('{} {}'.format(account, count))

This implementation reduces the time complexity from \$O(N^2)\$ to \$O(N)\$, and also gets rid of an \$O(N)\$ operation (no more need for the set.)

UPDATE

As @abarnert pointed out, the dictionary of counts can be created with a single expression using collections.Counter, so the above code can become simply:

from collections import Counter


def print_sorted_with_count(accounts):
    counts = Counter(accounts)
    for account, count in sorted(counts.items()):
        print('{} {}'.format(account, count))

Naming

The variable names in the posted code are horrible, and it makes it very hard to read. Avoid single-letter variable names, try to use descriptive names.

Coding style

I suggest to follow the recommendations of PEP8.

Time limit exceeded

When a solution is too slow, it's typically because the algorithm is one or more orders of magnitude worse than intended for the challenges. So take a hard look at the time complexity of the implementation.

In your implementation, it all comes down to this expression:

sorted(set(x+"%d"%(k.count(x)) for x in k))

  • k.count(x) : the centerpiece of the expression, to find the count of some value in a list. The count function does this by iterating over all elements k, and checking each for equality with x. Time complexity: \$O(N)\$, where N is the number of items in k

  • ... for x in k : do something for each item in k. Again, \$O(N)\$, where N is the number of items in k

  • set(...) : probably \$O(N)\$

  • sorted(...) : probably \$O(N\log(N))\$

In total that gives: \$O(N^2) + O(N) + O(N\log(N))\$

Can this be better?

  • You need to sort, that's for sure. That's fast enough.

  • Do you really need a set? You used a set because the previous operations generate a list with duplicates. Using a set to remove duplicates is fine, but I would question why are duplicates at all in the first place.

  • The previous two items actually don't even matter. It's the slowest operation in the \$O(N^2) + O(N) + O(N\log(N))\$ that will drag everything down, the \$O(N^2)\$, so that's what you really need to optimize.

Instead of iterating over every account number for each account number, you could iterate only once, building a dictionary with counts along the way:

def print_sorted_with_count(accounts):
    counts = {}
    for account in accounts:
        counts[account] = counts.get(account, 0) + 1
    for account, count in sorted(counts.items()):
        print('{} {}'.format(account, count))

This implementation reduces the time complexity from \$O(N^2)\$ to \$O(N)\$, and also gets rid of an \$O(N)\$ operation (no more need for the set.)

Naming

The variable names in the posted code are horrible, and it makes it very hard to read. Avoid single-letter variable names, try to use descriptive names.

Coding style

I suggest to follow the recommendations of PEP8.

Time limit exceeded

When a solution is too slow, it's typically because the algorithm is one or more orders of magnitude worse than intended for the challenges. So take a hard look at the time complexity of the implementation.

In your implementation, it all comes down to this expression:

sorted(set(x+"%d"%(k.count(x)) for x in k))

  • k.count(x) : the centerpiece of the expression, to find the count of some value in a list. The count function does this by iterating over all elements k, and checking each for equality with x. Time complexity: \$O(N)\$, where N is the number of items in k

  • ... for x in k : do something for each item in k. Again, \$O(N)\$, where N is the number of items in k

  • set(...) : probably \$O(N)\$

  • sorted(...) : probably \$O(N\log(N))\$

In total that gives: \$O(N^2) + O(N) + O(N\log(N))\$

Can this be better?

  • You need to sort, that's for sure. That's fast enough.

  • Do you really need a set? You used a set because the previous operations generate a list with duplicates. Using a set to remove duplicates is fine, but I would question why are duplicates at all in the first place.

  • The previous two items actually don't even matter. It's the slowest operation in the \$O(N^2) + O(N) + O(N\log(N))\$ that will drag everything down, the \$O(N^2)\$, so that's what you really need to optimize.

Instead of iterating over every account number for each account number, you could iterate only once, building a dictionary with counts along the way:

def print_sorted_with_count(accounts):
    counts = {}
    for account in accounts:
        counts[account] = counts.get(account, 0) + 1
    for account, count in sorted(counts.items()):
        print('{} {}'.format(account, count))

This implementation reduces the time complexity from \$O(N^2)\$ to \$O(N)\$, and also gets rid of an \$O(N)\$ operation (no more need for the set.)

UPDATE

As @abarnert pointed out, the dictionary of counts can be created with a single expression using collections.Counter, so the above code can become simply:

from collections import Counter


def print_sorted_with_count(accounts):
    counts = Counter(accounts)
    for account, count in sorted(counts.items()):
        print('{} {}'.format(account, count))

Naming

The variable names in the posted code are horrible, and it makes it very hard to read. Avoid single-letter variable names, try to use descriptive names.

Coding style

I suggest to follow the recommendations of PEP8.

added 1208 characters in body
Source Link
janos
janos
  • 111.7k
  • 15
  • 152
  • 391

Improving the time-complexityTime limit exceeded

What do you thinkWhen a solution is too slow, it's typically because the complexityalgorithm is one or more orders of somelist.count(value)? The count function has to compare allmagnitude worse than intended for the elements withchallenges. So take a hard look at the target valuetime complexity of the implementation.

If you call somelist.count(value) for every value in that listIn your implementation, what will be the complexity of it all comes down to this expression:

sorted(set(x+"%d"%(k.count(x)) for x in k))

  • k.count(x) : the centerpiece of the expression, to find the count of some value in a list. The count function does this by iterating over all elements k, and checking each for equality with x. Time complexity: \$O(N)\$, where N is the number of items in k

  • ... for x in k : do something for each item in k. Again, \$O(N)\$, where N is the number of items in k

  • set(...) : probably \$O(N)\$

  • sorted(...) : probably \$O(N\log(N))\$

In total that gives: \$O(N^2) + O(N) + O(N\log(N))\$

Can this be better?

  • You need to sort, that's for sure. That's fast enough.

  • Do you really need a set? You used a set because the previous operations generate a list with duplicates. Using a set to remove duplicates is fine, but I would question why are duplicates at all in the first place.

  • The previous two items actually don't even matter. It's the slowest operation in the \$O(N^2) + O(N) + O(N\log(N))\$ that will drag everything down, the \$O(N^2)\$, so that's what you really need to optimize.

A more efficient solution is possible, without traversing the listInstead of iterating over every account numbers so many times. You couldnumber for example build a map of counts using a dictionaryeach account number, and traversing the listyou could iterate only once., building a dictionary with counts along the way:

def print_sorted_with_count(accounts):
    counts = {}
    for account in accounts:
        counts[account] = counts.get(account, 0) + 1
    for account, count in sorted(counts.keysitems()):
        print('{} {}'.format(account, counts[account]count))

This implementation reduces the time complexity from \$O(N^2)\$ to \$O(N)\$, and also gets rid of an \$O(N)\$ operation (no more need for the set.)

Naming

The variable names in the posted code are horrible, and it makes it very hard to read. Avoid single-letter variable names, try to use descriptive names.

Coding style

I suggest to follow the recommendations of PEP8.

Improving the time-complexity

What do you think is the complexity of somelist.count(value)? The count function has to compare all the elements with the target value.

If you call somelist.count(value) for every value in that list, what will be the complexity of that?

A more efficient solution is possible, without traversing the list of account numbers so many times. You could for example build a map of counts using a dictionary, and traversing the list only once.

def print_sorted_with_count(accounts):
    counts = {}
    for account in accounts:
        counts[account] = counts.get(account, 0) + 1
    for account in sorted(counts.keys()):
        print('{} {}'.format(account, counts[account]))

Naming

The variable names in the posted code are horrible, and it makes it very hard to read. Avoid single-letter variable names, try to use descriptive names.

Coding style

I suggest to follow the recommendations of PEP8.

Time limit exceeded

When a solution is too slow, it's typically because the algorithm is one or more orders of magnitude worse than intended for the challenges. So take a hard look at the time complexity of the implementation.

In your implementation, it all comes down to this expression:

sorted(set(x+"%d"%(k.count(x)) for x in k))

  • k.count(x) : the centerpiece of the expression, to find the count of some value in a list. The count function does this by iterating over all elements k, and checking each for equality with x. Time complexity: \$O(N)\$, where N is the number of items in k

  • ... for x in k : do something for each item in k. Again, \$O(N)\$, where N is the number of items in k

  • set(...) : probably \$O(N)\$

  • sorted(...) : probably \$O(N\log(N))\$

In total that gives: \$O(N^2) + O(N) + O(N\log(N))\$

Can this be better?

  • You need to sort, that's for sure. That's fast enough.

  • Do you really need a set? You used a set because the previous operations generate a list with duplicates. Using a set to remove duplicates is fine, but I would question why are duplicates at all in the first place.

  • The previous two items actually don't even matter. It's the slowest operation in the \$O(N^2) + O(N) + O(N\log(N))\$ that will drag everything down, the \$O(N^2)\$, so that's what you really need to optimize.

Instead of iterating over every account number for each account number, you could iterate only once, building a dictionary with counts along the way:

def print_sorted_with_count(accounts):
    counts = {}
    for account in accounts:
        counts[account] = counts.get(account, 0) + 1
    for account, count in sorted(counts.items()):
        print('{} {}'.format(account, count))

This implementation reduces the time complexity from \$O(N^2)\$ to \$O(N)\$, and also gets rid of an \$O(N)\$ operation (no more need for the set.)

Naming

The variable names in the posted code are horrible, and it makes it very hard to read. Avoid single-letter variable names, try to use descriptive names.

Coding style

I suggest to follow the recommendations of PEP8.

Source Link
janos
janos
  • 111.7k
  • 15
  • 152
  • 391