44
votes
Accepted
Is there an existing data structure that is of fixed size, and will push the oldest/last element out if a new element is inserted?
Fixed-size queues are often implemented using what some people call circular buffers. If you remove the protection against it being full, you get the desired behaviour.
Of course, no actual pushing ...
- 71.9k
39
votes
Accepted
Time complexity $O(m+n)$ Vs $O(n)$
Yes:
$n+m \le n+n=2n$ which is $O(n)$, and thus $O(n+m)=O(n)$
For clarity, this is true only under the assumption that $m\le n$. Without this assumption, $O(n)$ and $O(n+m)$ are two different things -...
- 11.5k
31
votes
Accepted
One element that differs in two arrays. How to find it efficiently?
I see four main ways to solve this problem, with different running times:
$O(n^2)$ solution: this would be the solution that you propose. Note that, since the arrays are unsorted, deletion takes ...
- 3,634
31
votes
Accepted
Array access is O(1) implies a fixed index size, which implies O(1) array traversal?
It's a good question. From a pragmatic perspective, we tend not to worry about it.
From a theoretical perspective, see the transdichotomous model. In particular, a standard assumption is that there ...
D.W.♦
- 154k
29
votes
Accepted
What is the advantage of heaps over sorted arrays?
$\small \texttt{find-min}$ (resp. $\small \texttt{find-max}$), $\small \texttt{delete-min}$ (resp. $\small \texttt{delete-max}$) and $\small \texttt{insert}$ are the three most important operations of ...
- 766
25
votes
How to find 5 repeated values in O(n) time?
The solution in fade2black's answer is the standard one, but it uses $O(n)$ space. You can improve this to $O(1)$ space as follows:
Let the array be $A[1],\ldots,A[n]$. For $d=1,\ldots,5$, compute $\...
- 274k
22
votes
Accepted
How to find 5 repeated values in O(n) time?
You could create an additional array $B$ of size $n$. Initially set all elements of the array to $0$. Then loop through the input array $A$ and increase $B[A[i]]$ by 1 for each $i$. After that you ...
- 9,727
16
votes
One element that differs in two arrays. How to find it efficiently?
The $\Theta(n)$ difference-of-sums solution proposed by Tobi and Mario can in fact be generalized to any other data type for which we can define a (constant-time) binary operation $\oplus$ that is:
...
- 2,090
15
votes
Accepted
Matrix Max in less than O(n)
If you don't know anything about the contents of the matrix (such as some kind of monotonicity property), linear time is the best you can do for a one-off search with a deterministic algorithm by a ...
- 2,009
15
votes
One element that differs in two arrays. How to find it efficiently?
I'd post this as a comment on Tobi's answer, but I don't have the reputation yet.
As an alternative to calculating the sum of each list (especially if they are large lists or contain very large ...
- 411
14
votes
One element that differs in two arrays. How to find it efficiently?
Element = Sum(Array2) - Sum(Array1)
I sincerely doubt this is the most optimum algorithm. But it's another way to solve the problem, and is the simplest way to solve it. Hope it helps.
If the number ...
- 1,607
12
votes
Accepted
Applicative-order languages don't support constant time array writes? If not, why not?
Skiena didn't say "applicative order", just "applicative". This is sometimes used as meaning something like "purely functional", or a language that evaluates via the application of functions as ...
12
votes
Accepted
How can merging two sorted arrays of N items require at least 2N - 1 comparisons in every case?
What is meant by "lower bound" in this case is a lower bound on the worst-case number of comparisons. In this case, it happens to also be an upper bound.
The lower bound has to be something that is ...
- 13.1k
11
votes
Accepted
Find a point shared by maximum segments
Let's use $+$ to denote the start of a segment and $-$ to denote the end. For each segment, create two pairs, one for each endpoint:
...
- 3,252
11
votes
Time complexity $O(m+n)$ Vs $O(n)$
Yes, since $n + m \leq 2n$ the algorithm is $O(n)$. However, you may wish to write $O(m + n)$ because it clearly shows which variables the algorithm depends on, and what each variable does to the ...
- 211
10
votes
How to measure "sortedness"
Mannila [1] axiomatizes presortedness (with a focus on comparison-based algorithms) as follows (paraphrasing).
Let $\Sigma$ a totally ordered set. Then a mapping $m$ from $\Sigma^{\star}$ (the ...
- 71.9k
10
votes
Accepted
From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?
Let's assume that adding two strings of lengths $a,b$ takes time $a+b$. Consider the following strategy to convert a list of $n$ characters into a list:
Read the list in chunks of $k$, convert them ...
- 274k
10
votes
Accepted
Find a weighted median for unsorted array in linear time
Let $A$ be an input array containing $n$ elements, $a_i$ the $i$-th element and $w_i$ its corresponding weight. You can determine the weighted median in worst case linear time as follows. If the array ...
- 4,112
10
votes
Accepted
Why does the order of the nested loops matter when solving the Coin Change problem?
In the second solution you are overcounting the number of combinations.
In fact you are counting the of ways to choose an ordered list of coins that sums to sum.
...
- 27.4k
9
votes
Accepted
Why does merging two sorted arrays take 2N - 1 comparisons?
The question asks to show the lower bound on the number of comparisons in merging two sorted arrays of length $N$. Therefore, you need to argue that no matter what comparison-based algorithm you use, ...
- 1,473
9
votes
Why shuffling by picking random position in all array instead of a part is not correct
Suppose that the array has length $n$. Since you are making $n$ random choices of numbers from 1 to $n$, the probability to obtain any specific permutation is of the form $A/n^n$, for some integer $A$....
- 274k
8
votes
Accepted
What is a partially sorted array?
The definition you quote is rather meaningless. More accurately, a sequence of arrays, one of each length $n$, is partially sorted if for some constant $c$, the number of inversions of the array of ...
- 274k
8
votes
Complexity of algorithm to find number of elements > element index i in an array
Your problem is very related to that of computing the number of inversions in a permutation, or (equivalently) the Kendall tau distance between two permutations; this is the sum of your vector. In ...
- 274k
8
votes
How to find 5 repeated values in O(n) time?
There's also a linear time and constant space algorithm based on partitioning, which may be more flexible if you're trying to apply this to variants of the problem that the mathematical approach doesn'...
- 942
8
votes
Accepted
Sorting a large list of test scores
This is a very easy question, assuming all scores are integers.
Here is the simplest algorithm in plain words. We will initiate count, an integer array of 100 ...
- 38.5k
7
votes
How do I find the max and min value of an array in 3n/2−2 comparisons?
Imagine having a tournament made of the array elements. Group the array elements into pairs, then compare each pair. Put the larger numbers into one group and the smallers number into another group. ...
- 9,027
7
votes
Accepted
How to prove that average complexity is N/2 for linear search in the unsorted array
First assume input is uniformly distributed. More precisely it is $\frac{n+1}{2}$. When you search for a particular element $x$ in an array of size $n$, that element may be located at the position ...
- 9,727
7
votes
Accepted
what is actually a circular array and representation
Circular array is just a fixed size array. We call it circular just because we define the operations on the array in such a manner that its limited size can be utilized again and again and it ...
- 1,195
7
votes
Is it possible to solve this problem in less than n^2 time without using additional space?
Let’s use $a_i$ for the array. You are interested in
$$
\begin{align*}
\max_{i,j} a_i + a_j + |i-j| &= \max_{i,j} a_i + a_j + \max(i-j,j-i) \\ &=
\max_{i,j} \max((a_i+i)+(a_j-j), (a_j+j)+(a_i-...
- 274k
6
votes
How to measure "sortedness"
I have my own definition of "sortedness" of a sequence.
Given any sequence [a,b,c,…] we compare it with the sorted sequence containing the same elements, count number of matches and divide it by the ...
Only top scored, non community-wiki answers of a minimum length are eligible