Skip to main content
6 votes
Accepted

Find two numbers in array $A$ such that $ |x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time

This is an interesting question. Here is a linear-time algorithm. Assum $n\ge1$. Compute the minimum $m$ and the maximum $M$. If $m=M$, return $a_0$ and $a_1$. Otherwise, let $\delta=\frac{M-m}n$. ...
John L.'s user avatar
  • 39k
5 votes

Find two numbers in array $A$ such that $ |x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time

Let $z$ be the median of $A$, and split $A$ into two subarrays $B,C$: the array $B$ consists of all numbers at most $z$ (including $z$), and the array $C$ consists of all number at least $z$ (...
Yuval Filmus's user avatar
4 votes

Compute median in unsorted array in $\mathcal{O}(\log{}n)$ space and $\mathcal{O}(\log{}n)$ passes

The natural algorithm determines the $\log n$ bits of the median, MSB to LSB. Suppose that we have determined the $k$ MSBs of the median, $b_{m-1},\ldots,b_{m-k}$. Determine the number of integers in ...
Yuval Filmus's user avatar
4 votes
Accepted

Finding Median value given a tuple (value, frequency) in O(n) worst case time complexity

I think you can still use the linear time selection algorithm (median of medians) here. Let's call this algorithm $Select$ and let the median position be $m$, which is initially equal to $n/2$.Recall ...
Russel's user avatar
  • 2,780
3 votes

Understanding Randomized Select algorithm

The function Randomized-Partition accepts an array $A[p],\ldots,A[r]$ and partitions it around a pivot. The position $q$ of the pivot is returned. We are guaranteed that $A[p],\ldots,A[q-1] \leq A[q] \...
Yuval Filmus's user avatar
3 votes

Selection over combinatorics that satisfies a distribution

Consider the following special case where for each element $i$ the table contains the constraint $\#i \geq (1/l) \cdot l$. This means we need to select the sets in such a way that each element appears ...
Narek Bojikian's user avatar
3 votes
Accepted

Finding the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time

Let $n$ denote the length of the array. We will find the largest $N$ such that there are at least $N$ elements whose value is at least $N$. Make a pass through the array, counting the number of ...
Yuval Filmus's user avatar
3 votes
Accepted

Median of Medians Recurrence Relation for 3-grouping

You can use the inequality $\log (1+x) < x$ (valid for $x > 0$, where $\log$ is the natural logarithm), which follows from a Taylor expansion, to reason as follows: $$ \log \left(\frac{n'}{3} + ...
Yuval Filmus's user avatar
2 votes
Accepted

Time complexity of a precedence constrained selection problem

If you flip the signs on your costs and reverse edge directions, this is the Closure Problem, also known as the Open-Pit Mining Problem, and it's actually solvable in polynomial time using a rather ...
j_random_hacker's user avatar
2 votes

Finding the half with greatest elements in a set

Proceed in two phases. Determine the median of the input. Partition the input with the median as the pivot (cf. Quicksort). Both steps take worst-case linear time. Note, though, that in practice you'...
Raphael's user avatar
  • 72.6k
2 votes
Accepted

Given a binary min-heap, getting a sorted array of the $\log n$ smallest elements

Consider another min-priority queue $q$. The result will be in array $a$. Push the top of the heap into $q$. For $i$ from $1$ to $\log n$: Set $a_i = \text{pop}(q)$. Push the two sons of $a_i$ in ...
md5's user avatar
  • 646
2 votes
Accepted

How to find kth largest element in (max) priority queue in O(m) time?

You can implement FINDLARGEST recursively: ...
Yuval Filmus's user avatar
2 votes

Name of algorithm: When looking for an optimal element in a list, contionusly adapt the acceptance threshhold

These problems are in the field of optimal stopping theory. There are a large number of approaches to the problem, which can be found using this term. The example about dating appears in Hannah Fry's ...
Kjeld Schmidt's user avatar
2 votes
Accepted

Median of medians: bound on pivot position

You missed the recursive step of this recursive algorithm. For the sake of discussion, assume you want to find the 99th smallest element of the initial 125 elements. Here 99 is just an arbitrary ...
John L.'s user avatar
  • 39k
2 votes
Accepted

How is Rank Selection better than Random selection and RWS?

It's about controlling selection pressure. With roulette wheel selection, there are several scaling issues. If you have two individuals p1 and p2 with fitness values 1 and 2 versus having values 1001 ...
deong's user avatar
  • 1,061
2 votes

Is finding Kth largest element using selection algorithm taking O(n) only if K is fixed?

The algorithm that uses "sort of quicksort" to find the $k$-th smallest (or largest) element is generally called quickselect. Here is the precise meaning of "the average complexity of ...
John L.'s user avatar
  • 39k
2 votes

Is finding Kth largest element using selection algorithm taking O(n) only if K is fixed?

There is no requirement that $k$ be constant, and those StackOverflow comments are misleading or simply incorrect. Obviously $k \le n$ and so $k$ is $O(n)$. Your partial bubblesort algorithm is $O(kn)...
rici's user avatar
  • 12.1k
2 votes

Find m smallest elements in an array of size n where m = n/2

Find the median in $O(n)$ time. Then go over the array and take out all elements smaller than the median.
Yuval Filmus's user avatar
2 votes

Finding the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time

Let $S$ and $\ell$ be a set of input elements (integers) and let $\ell$ be an integer. Consider the problem of finding the maximum cardinality of a subset $S^*$ of $S$ that contains the largest ...
Steven's user avatar
  • 29.5k
2 votes

Findind The n/lgn intermidiate values in an unsorted array with asymptotic run time of $\Theta(n)$ SELECT algorithm

You can find a $k$-th order statistic of an array using a selection algorithm in $\Theta(n)$ time. It means that you can also find the $k$ least (and the $k$ greatest) elements of an array in $\Theta(...
Vladislav Bezhentsev's user avatar
2 votes

Find two numbers in array $A$ such that $ |x-y| \leq \frac{\max(A)-\min(A)}n$ in linear time

Find the minimum m and M; m = M is trivial. For each i, let yi = (xi - m) * n / (M - m), so 0 <= yi <= n. Start with an empty table with entries 0 to n, then for each i record i and yi at entry ...
gnasher729's user avatar
1 vote
Accepted

Algorithm for splitting an array into k sub-arrays

Insert$(x)$ can be implemented in $O(k \log(n/k))$ time. I will use the terms subarray and group interchangeably. Let $n$ be the number of elements in the data structure before the insert operation. ...
Steven's user avatar
  • 29.5k
1 vote

Median-of-Medians proof for time complexity

I am basically just paraphrasing the steps I've outlined here: https://cs.stackexchange.com/a/83650/68251. This is assuming the base case is $T(n) \leq c$ when $n < 5$. Claim $T(n) \leq 10\cdot ...
ryan's user avatar
  • 4,511
1 vote

Median-of-Medians proof for time complexity

Assuming that you got the base covered, here is the inductive step: $$ T(n) \leq T(n/5) + T(7n/10) + cn \leq 10c(n/5) + 10c(7n/10) + cn = 10cn. $$ (Cheating a bit, since $n$ isn't necessarily ...
Yuval Filmus's user avatar
1 vote

Findind The n/lgn intermidiate values in an unsorted array with asymptotic run time of $\Theta(n)$ SELECT algorithm

I think this question is almost the same idea Algorithm to identify top $\log n$ elements in $O(n)$ time So u can combine the idea of the solution there with what was suggested to u here to get a ...
ShAr's user avatar
  • 138
1 vote
Accepted

Minimum number of comparision to find the third largest element in an array of distinct integers?

For the problem of computing the $k$-th rank element, a lower bound of $n-k+\log \binom{n}{k-1}$ can be proven with decision trees. For simplicity this proof assumes that the element set $X$ is of ...
lox's user avatar
  • 1,669
1 vote
Accepted

Lower Bound for Time Complexity of Pairing Problem

This answer uses the convention that the elements of $X$ are $x_1,\ldots,x_n$ (in their original, unsorted order), and similarly the elements of $Y$ are $y_1,\ldots,y_n$. This differs from your ...
Yuval Filmus's user avatar
1 vote

Find m smallest elements in an array of size n where m = n/2

You can create a min heap ($O(n)$) and then perform extract min m times. ($O(mlogn)$). Time complexity will be $O(n) + O(nlogn)$.
simple-sober's user avatar
1 vote

Finding median from given range

It can be done in $O(L \log L)$ time, which is optimal by reduction from sorting. Consider a Red-Black Tree $T$ (or any other self-balancing tree) where each node $v$ is augmented with $s(v)$, the ...
quicksort's user avatar
  • 4,262

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