# Tag Info

### 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
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
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
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

### 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

### 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

### 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
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
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
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
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

### 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

### 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
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

...
• 44.3k
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

### 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

### 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

### 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

### "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

### 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
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

### 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

### 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

### 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

### 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

### 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

### Simplify complexity

appropriate names const checkArray = (word, arr) => { This is just a terrible signature, almost as meaningless as ...
• 32.5k