Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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
  • 72.5k
40 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.6k
31 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
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
  • 160k
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,837
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

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,617
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,302
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
11 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
  • 29.5k
10 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
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

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
  • 72.5k
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

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
  • 962
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
  • 39k
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,837
7 votes
Accepted

Name of this rearranging/sorting problem?

Note: It is a hardness proof, and I think there are practical algorithms like integer programming, etc. Given a BIN_PACKING instance where you want to pack $K$ numbers $n_1,\ldots,n_K$ into $L$ bins ...
Wei Zhan's user avatar
  • 1,183
7 votes

What is the time complexity of memory allocation assumed to be?

what would the worst-case complexity be if it didn't have to copy over $n$ items? If it only needed to allocate a buffer with size $O(n)$ when resizing, would that be considered to run $O(1)$ or $O(n)$...
Tom van der Zanden's user avatar
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,215
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
6 votes
Accepted

Complexity of algorithm to find number of elements > element index i in an array

TL;DR: There is a simple algorithm that runs in time $O(n \log n)$ and finds the inversion vector of a given array. Furthermore, there is a time lower bound of $ \Omega (n \log n) $ for any comparison-...
Itay Hazan's user avatar
6 votes

What is the advantage of heaps over sorted arrays?

To answer your questions, you have to define which different actions you will perform and how often, and you have to evaluate the time complexity of each action. Which method is performing better ...
gnasher729's user avatar
  • 30.4k

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