Skip to main content
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 ...
Kelly Bundy's user avatar
  • 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 ...
200_success's user avatar
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 ...
Der Kommissar's user avatar
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: ...
Gareth Rees's user avatar
  • 49.6k
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 ...
GZ0's user avatar
  • 2,331
12 votes
Accepted

Finding Pythagorean triplet in array

A couple of notes on your code before going into alternative solutions. In your findTriplet method, you are doing: ...
Tunaki's user avatar
  • 9,243
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 ...
slepic's user avatar
  • 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 ...
200_success's user avatar
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, ...
Tunaki's user avatar
  • 9,243
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....
mdfst13's user avatar
  • 21.6k
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 ...
Incomputable's user avatar
  • 9,484
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 ...
AJNeufeld's user avatar
  • 33.6k
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 ...
MJ713's user avatar
  • 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 ...
J_H's user avatar
  • 25.6k
9 votes

Find maximum difference between values in an array

What does this algorithm do? It finds the smallest and greatest number in an array and creates the difference of them. Nope. Consider {5, 2, 1}. The pseudo code returns 5 - 1 = 4 which happens to be ...
Taemyr's user avatar
  • 1,020
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 ...
200_success's user avatar
9 votes

Finding the most popular element with C# given O(1) space complexity requirement

...
t3chb0t's user avatar
  • 44.3k
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; ...
JAD's user avatar
  • 2,909
8 votes
Accepted

Function to check truth value of a specific statement

Make the function return True or False. You can use all and a generator comprehension ...
Peilonrayz's user avatar
  • 43.3k
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 ...
RubberDuck's user avatar
  • 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, ...
Peter Taylor's user avatar
  • 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. ...
Vogel612's user avatar
  • 25.2k
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 ...
potato's user avatar
  • 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 ...
lubgr's user avatar
  • 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 ...
Vikas's user avatar
  • 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: ...
Roman's user avatar
  • 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 ...
AJD's user avatar
  • 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 ...
David G.'s user avatar
  • 1,333
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. ...
Kelly Bundy's user avatar
  • 3,134

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