Hot answers tagged

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 ...
Raphael's user avatar
  • 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 -...
nir shahar's user avatar
  • 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 ...
Mario Cervera's user avatar
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.'s user avatar
  • 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 ...
PSPACEhard's user avatar
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 $\...
Yuval Filmus's user avatar
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 ...
fade2black's user avatar
  • 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: ...
Ilmari Karonen's user avatar
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 ...
G. Bach's user avatar
  • 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 ...
reffu's user avatar
  • 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 ...
Tobi Alafin's user avatar
  • 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 ...
Derek Elkins left SE's user avatar
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 ...
Tom van der Zanden's user avatar
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: ...
Vincenzo's user avatar
  • 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 ...
BBrooklyn's user avatar
  • 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 ...
Raphael's user avatar
  • 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 ...
Yuval Filmus's user avatar
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 ...
Massimo Cafaro's user avatar
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. ...
Steven's user avatar
  • 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, ...
Denis Pankratov's user avatar
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$....
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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'...
Veedrac's user avatar
  • 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 ...
John L.'s user avatar
  • 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. ...
templatetypedef's user avatar
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 ...
fade2black's user avatar
  • 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 ...
Navjot Singh's user avatar
  • 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-...
Yuval Filmus's user avatar
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 ...
Andrushenko Alexander's user avatar

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