8

As others have mentioned, your program runs slowly because it is doing a lot of membership tests against fairly large lists, which is expensive. If you replace your lists with sets, that alone should improve performance by quite a bit. Creating a set from the input list of words is also important to ensure the correctness of your algorithm. As @Tweakimp ...


7

PEP 8 The Style Guide for Python Code lists many recommendations: variables & functions should be snake_case commas should be followed by a space binary operators should be surrounded by a space (eg, l == r instead of l==r, and r + 1 instead of r+1) Some of the function/variable names may be dictated to you by the coding challenge, but for all others ...


7

Bug Your function does not filter out duplicate pairs. >>> words = ["test", "tset", "test", "tset"] >>> find_opposites(words) [('test', 'tset'), ('test', 'tset')] Improvements Comprehension: # This part opposites = [] # contains all words backwards (except palindromes) result = [] for word in lst: ...


5

The part if word in lst basically uses a for-loop to check the entire list again, which takes on average 11000/2=5500 tries. So you'll have 11000*5500 = 60.500.000 pairwise checks. That shouldn't take ages but still isn't efficient. There's also the checking of the result, which is a growing list so that takes longer after every result. If you used a ...


4

It’s \$ O(n * m) \$ because of badNumbers.count(i), n and m being the lengths of badNumbers and the range from left to right. You could reduce this to \$ O(n + m) \$ if you cast badNumbers to a set and check if i is in the set. You’re doing a lot of unnecessary things in the function. You only need to keep track of the current amount and the largest amount ...


4

Instead of searching for the value that belongs at Queue[i] to swap it there, just swap the value that is there to where that belongs: def MinimumSwaps(Queue): MinSwaps = 0 for i in range(len(Queue) - 1): while Queue[i] != i + 1: j = Queue[i] - 1 Queue[i], Queue[j] = Queue[j], Queue[i] MinSwaps += 1 ...


3

PEP 8 You are violating several Style Guide for Python Code rules: commas should be followed by a space, variables should be snake_case, always surround binary operators with one space Never called ex1() is never called by your mainline. Declare variables closer to where they are used subsequences is declared 7 lines earlier than it needs to be. Separate I/...


3

I assume you refer to https://cses.fi/problemset/task/1071/ . Your Algorithm itself is fine as far is i can tell. The Problem is the large amount of inputs that need to need to be read(Testcases=100000), which Scanner cant provide within the 1s time limit. A BufferedReader should offer the performance needed for this.(See https://www.geeksforgeeks.org/fast-...


3

The problem here isn't with generating the permutations, it is with memory management. One way to visually see this is to replace the \n at the end of your output with std::endl so you see the results of each iteration at the end of the loop. The delay between the output of the last line and the program ending is all due to freeing memory. One way to address ...


3

This code is fast and simple. It takes around 5ms to find 15-odd pairs in 10,000 words. The speed comes from using a set lookup and comprehensions. def find_opposites_set1(words): reversed_words = [word[::-1] for word in words] unique_reversed_words = set(reversed_words) return [ (word, reversed_word) for word, reversed_word ...


2

The problem We are given an NxN chessboard with one cell designated as the origin and all others being open or blocked. One of the open cells is designated as the destination. If a knight begins at the origin, we wish to find the smallest number of moves among empty cells required for it to reach the destination. Specifically, we are be given an array board ...


2

You can simplify the loop in main. flag is unnecessary. Just use an infinite loop with a break statement. Also, because you know that any number with a zero as the last digit won't be a palindrome, you can skip those. Putting those together, you get: for (;;) { reversenum = reverse_num(n); if (reversenum == n) break; ++n; if (n % 10 == 0) ++n;...


1

Your question made me want to give it a shot, too. The solution ended up pretty much like the pseudo-code suggested by @Marc , and Python is of course pretty close in readability anyway. The below code passes on the site and runs (there is some deviation between runs) faster than c. 95% and at with less memory usage than c. 75% of solutions. The code ...


1

My suggestion about your current solution: def max_area(height) -> int: areas = [] coords = {x: (x, y) for x, y in enumerate(height)} for x in coords: higher = [k for k in coords if coords[k][1] >= coords[x][1]] area = max(abs(coords[j][0] - coords[x][0]) for j in higher) * coords[x][1] areas.append(area) return ...


1

Your code is \$O(n^2)\$ because of the inner loop. for j in range(i+1,len(Queue)): if Queue[j] == i+1: # inner We can change this to be \$O(1)\$ by making a lookup table of where \$i\$'s location is. We can build a dictionary to store these lookups. indexes = {value: index for index, value in enumerate(Queue) We can then just swap these indexes ...


1

You could simply compare the word and its reverse with word < word[::-1] in order to avoid palindromes and duplicate entries. If words is a set containing all the possible words, you can create a set of results directly: mirror_words = {w for w in words if w < w[::-1] and w[::-1] in words} After initializing words with: with open('/usr/share/dict/...


1

Naming The question starts off talking about N and K. Your code begins with reading in z and d. The question text is ready-made documentation for your code; use the same names for the variables! n, k = map(int, input().split()) Guilty, I said N and K but used n and k. PEP 8, the Style Guide for Python Code recommends using snake_case for variables. So we ...


Only top voted, non community-wiki answers of a minimum length are eligible