Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

New answers tagged

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