New answers tagged sorting
1
I believe a hashing approach should give you $O(N)$ time, where $N$ is the length of the longer array (we can relax the constraint that they are the same size).
Simply put all the elements in the first array into a hashset, and then check whether each element in the second array exists in the hashset.
You could even account for duplicates by instead using ...
0
Solving this problem benefits from geometrical intuition. Think that for each index $i$, the pair $(i, A[i])$ represents a point in 2D-space. Also we can think that assigning $A[j]=0$ is the same as removing the point $(j, A[j])$ from this space. Now a query with index i means removing all points that are left and below of point $(i, A[i])$.
Now the set of ...
2
I shall modify the question a bit and answer the following version, which I think is more correct:
Prove that the lower bound of any character-comparing string sorting algorithm is $\Omega(d + n \log n)$, where $d$ is the sum of the lengths of the distinguishing prefixes of all the strings in our set $S$ and $n$ is the cardinality of the strings set $S$. ...
2
The time complexity you indicated is the lower bound of your specific problem. A lower bound is the worst-case running time of the most optimized TM that recognizes membership in the language.
Lover bound for sorting algorithms is $\Omega(n \log n)$ this means that it is not possible to do better than this and all the sorting cases (instances) may have a ...
3
This is algorithm called bucket sort, integer sort, counting sort, or Pigeonhole sort (naming is a bit inconsistent across sources and/or different names refer to slight variations of the same idea).
Its time complexity is $O(m)$ (assuming distinct values) where $m$ is the largest among the $n$ integers you are trying to sort. Your algorithm takes $O(n)$ ...
1
"Being more interesting" is not a transitive property. I can simultaneously find book A more interesting than B, book B more interesting than C, and book C more interesting than A. (On top of that, whether A is more interesting than B might also depend on when you ask me).
I wouldn't use a yes/no decision but let's say a range from -10 to +10, which allows ...
Top 50 recent answers are included
