23
votes
The fastest way to find one unique value when all other values are the same
Benchmarks!
Benchmarks for lists with a thousand or a million elements, with the unique element in the middle of the array to reflect the "typical"/"average" case. The results are ...
- 3,134
18
votes
Accepted
Check if one string is a permutation of another using Python
Yes, len(str) should be O(1) in Python. (Good question!) Each of your for loops is O(n), so your whole function is O(n).
Your ...
- 144k
18
votes
Accepted
Finding the most popular element with C# given O(1) space complexity requirement
You don't have \$O(1)\$ space complexity at the moment, OrderBy and OrderByDescending (used wrong as pointed out in the other ...
- 20.1k
14
votes
Accepted
Find the total number of ways W, in which a sum S can be reached in N throws of a dice
1. Review
The sum \$s=0\$ can be reached in \$n=0\$ throws in exactly one way, but:
...
- 49.7k
13
votes
The fastest way to find one unique value when all other values are the same
No matter how the array is traversed, the distinguished element can occur at the end of the traversal. Therefore, it is necessary to go through the entire array in the worst case and there does not ...
- 2,331
11
votes
Binary Search written in python with O(n)
It's not really a binary search if it is not O(log(n)).
Binary search only works on sorted inputs and it takes advantage of the fact that it is sorted to achieve ...
- 5,477
10
votes
Finding a max element in an array in Java
Yes, this is O(n), because you visit every element once. You can't possibly do better than O(n), because there is no way to be sure that you have found the maximum value without inspecting every ...
- 144k
10
votes
Accepted
Find the number of K-Complementary pairs in an array
Current algorithm
The time complexity of the current solution is O(N²): for a given array of length N, it needs to loop through its elements from 0 to its length, ...
- 9,233
10
votes
Accepted
Sort an array of 0s, 1s and 2s in Java
Descriptive names
private static void printSortedArr (int[] arr) {
I don't like these names. I would rather write out array if that's what's being said. E....
- 21.7k
10
votes
Accepted
Regular Expression Evaluator
Bug
There is a case that requires NFA instead of simple DFA to recognize string (of course it is possible to convert NFA to DFA):
eval("aaab", "a*ab");
Gives ...
- 9,534
10
votes
Accepted
Time and Space Complexity of Prime factorization
isPrime()
Complexity
This function contains a simple loop that iterates up to Math.sqrt(number) times, so assuming ...
- 33.9k
10
votes
Number Plate Generation Program
General formatting
Keeping code nicely formatted makes it easier to read, and therefore easier to work on. This is especially important when you work on a project with multiple people, where other ...
- 726
10
votes
Longest spell to cast from pages of spellbook
obscure code
c, a, mx, ct, og, mx = 0, 0, 0, [0], [0] * x, 0
Uggh, this is terrible in so many ways.
Please don't write code like that.
Find a classmate.
Show them ...
- 32.5k
9
votes
Accepted
URLify a string using Python
Your complexity analyses look correct to me. I would just say, in short, that this function works in O(n2) time.
Note that this is an awkward exercise to do in Python, or any language in which ...
- 144k
9
votes
9
votes
Accepted
Find the smallest positive integer that is absent from a given array
I then tried putting the array into an arraylist, which reduces big-O since each object is "touched" only once, and I can use .Contains which is more efficient than iteration (not sure if that's true; ...
- 2,919
8
votes
Finding the most popular element with C# given O(1) space complexity requirement
Your solution appears to be correct, although I can't speak to the space complexity of it. Linq makes complex things look easy. There's a lot going on "behind the scenes" here.
Anyway, let's look at ...
- 30.8k
8
votes
Finding the most popular element with C# given O(1) space complexity requirement
One requirement here is also to make the code execute in O(1) space complexity.
That's going to preclude an elegant solution (with or without Linq). In particular, ...
- 24.1k
8
votes
Alone in a Couple implementation in Java
You are using a pretty nice idea here. You store things you've seen once and remove them when you've seen them a second time. To do so you're using a List.
...
- 25.3k
8
votes
"Counter Game" Powers of 2 Game
This can actually be solved with a super efficient 1 line of code, but the explanation is long :)
(and there are a few other things I should point out first)
Your code will fail with any input bigger ...
- 1,122
8
votes
Finding the upper and lower bound using binary search
I am trying to understand what aspect of my code could be made more efficient and faster.
First, the low hanging fruits...
You unnecessarily copy the sequence of integers when passing it to ...
- 956
8
votes
Accepted
Finding unpaired number in an odd length Array of integers
Sorting of the array will take O(n (log n)) in the average case. You can do it in linear time using bitwise operation
...
- 96
8
votes
An array with \$O(\log\ n)\$ time complexity for all operations
Import
import java.util.*;
The class does not need to import the whole java.util package. Instead it only needs:
...
- 2,843
8
votes
Find the smallest positive integer that is absent from a given array
The algorithm provided by the OP presumes that the array is important and preserves the original array. In addition, the displayed algorithm seeks an "instantaneous answer", as if the routine may be ...
- 2,346
8
votes
Are the sum of two numbers desired?
I believe you could reduce it to \$O(n\log{n}+m\log{n}+n m)\$ if you want.
Sort the inputs, then iterate over the tests and for each one, do a two variable iteration over the inputs, where you ...
- 1,446
8
votes
The fastest way to find one unique value when all other values are the same
Another one going only as far as necessary, with O(1) to check whether the first value is the outlier and otherwise simple O(n) to search for the outlier.
...
- 3,134
8
votes
Longest spell to cast from pages of spellbook
One thing that these kinds of sites like to do is generate huge inputs that are trivial when viewed from the right angle.
One "huge" input would be an array such that a[n] = n. This ...
- 12.4k
8
votes
Simplify complexity
appropriate names
const checkArray = (word, arr) => {
This is just a terrible signature,
almost as meaningless as ...
- 32.5k
7
votes
Accepted
Rotate Matrix using Python
You can use much simpler algorithm in python:
Transpose matrix:
zip(*matrix)
Inverse rows in transposed matrix (equals rotation right):
...
- 86
Only top scored, non community-wiki answers of a minimum length are eligible