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 $\...
- 270k
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,632
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'...
- 912
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,632
7
votes
What other involutions are there besides xor?
Roll your own.
Take an arbitrary bijection $f$ from the integers to integers. This is a permutation of the integers.
Then, take the conjugate of XOR ($\oplus$):
$$
g(x,y) = f^{-1}(f(x) \oplus f(...
- 14.2k
6
votes
Check if adding an edge to a DAG results in a cycle
Kahn's algorithm is known for topological sorting, but it can be used to find strongly connected components as well. I use it for cycle checking, where an actual topological sort is not needed. In ...
- 1,254
5
votes
How to find 5 repeated values in O(n) time?
Leaving this as an answer because it needs more space than a comment gives.
You make a mistake in the OP when you suggest a method. Sorting a list and then transversing it $O(n\log n)$ time, not $O(n^...
- 767
5
votes
Chess Knight minimum moves to destination on an infinite board
The easiest way to solve this problem is to greedily move in the best direction until you get within 100 squares or so, and then A* from there.
Figuring out exactly how close you can get before you ...
- 474
5
votes
Chess Knight minimum moves to destination on an infinite board
There is a closed form solution for finding the minimum number of moves the chess knight needs to move a specified displacement on the infinite chess board. Let $g$ be the requisite displacement ...
4
votes
Accepted
Why does linear search have $\frac{n}{2}$ comparisons on average?
It's neither ${(n^2+3n)}/{(2n+2)}$ nor $n/2$. In fact, the question itself doesn't make much sense at all. In order to be able to talk about the average running time of an algorithm, you have to fix a ...
- 4,132
4
votes
pattern search with k-mismatch
Split into segments
One simple approach is to split $P$ into $k+1$ pieces, say $P = P_0 P_1 \cdots P_k$, as @j_random_hacker suggests. You can make each of the $P_i$ be of approximately equal length,...
D.W.♦
- 143k
4
votes
Accepted
range / interval query algorithm
Use an interval tree. It is designed to support exactly this. In particular, the query "find all ranges that contain this value" is known as a stabbing query, and it can be answered in essentially $O(...
D.W.♦
- 143k
4
votes
Understanding Binary Search for Kth Smallest element in an Array
Let me start by recalling the question:
Given an unsorted array of $n$ elements in the range $1,\ldots,m$, find the $k$th smallest element in $O(n\log m)$ time and $O(1)$ case.
Calling the array $...
- 270k
4
votes
Accepted
Proving correctness of search algorithms
The idea of the algorithm is to maintain the following invariant:
If $x$ is in the matrix, then it is in the submatrix whose top right corner is $e$.
The invariant clearly holds in the beginning, ...
- 270k
3
votes
Accepted
Reference/book recommendations for search data structure
I highly recommend MIT course on Advanced Data Structures, I was watching Eric Demaines lectures, he shows multiple examples, here are some of them:
Van Emde Boas tree
Y-fast trie
Here some ...
- 146
3
votes
Accepted
Does this A-Star heuristic already exist?
This idea is called True Distance Heuristics and as you suspected, it can be very efficient.
True Distance Heuristics
True Distance Heuristics (as well as "Pattern Database") is a technique ...
- 146
3
votes
How to find 5 repeated values in O(n) time?
There's an obvious in-place variant of the boolean array technique using the order of the elements as the store (where arr[x] == x for "found" elements). Unlike the ...
- 912
3
votes
Find all pairs (i, j), such that i + (i+1) + (i+2) + ... + j = n
Another algorithm:
Find all factorizations of $2n$ into a product of two integers, say $2n=r \times s$ with $r \le s$. Then find $i,j$ such that $j-i+1=r$ and $i+j=s$, i.e., $i=(s-r+1)/2$ and $j=(s+...
D.W.♦
- 143k
3
votes
Finding one of 2/3 of all array elements in constant expected time
One approach would be to randomly pick a large constant $k$ indices and test them. The exact probability of at least one of them being $A[i] = X$ would be:
$$\begin{align}
P(\text{at least }1\; X) &...
- 4,371
3
votes
Array contains elements that differ by K correctness proof
My line of thought for deriving this algo:
there is well-known Merge algo (part of Merge Sort) combining two sorted arrays
we can modify it to output only equal elements of arrays (i.e. producing ...
- 1,805
2
votes
Accepted
Output cycle found by DFS
When true is returned I can output the cycle by taking the nodes from the stack.
The stack contains the nodes you still have to visit, so they can not be part of the cycle.
There are at least two ...
- 71.1k
2
votes
Accepted
Possible solutions how to find all points (given by lat, long) that are within a radius from main point
You can speed up your search by using a datastructure like a kd-tree or an r-tree. The basic idea is to divide your space into boxes and store the mapping from points to boxes (and back) in a way that ...
- 5,910
2
votes
Accepted
Check if adding an edge to a DAG results in a cycle
KWillets' algorithm
KWillets seems to have the best algorithm. Basically, you iteratively alternate between the following two steps:
For each source (vertex with no outgoing edge), remove the ...
D.W.♦
- 143k
2
votes
Accepted
Algorithm: Finding median in a sorted array with duplicates
Yes. Even with duplicates, the process of finding median is same. See this link - https://math.stackexchange.com/questions/1191119/how-to-find-the-median-of-three-numbers-if-one-of-them-appears-twice
- 36
2
votes
Accepted
Pick matrices such that each partial sum is positive
I'll represent you problem as:
Let $S_1, \dots, S_n$ be sets of $p$ vectors of size $d$. Find a vector $v_i$ in each $S_i$ so that for every $k\le n$, $\displaystyle \sum\limits_{0\le i \le k}v_i$ ...
- 1,227
2
votes
Accepted
Using A* search with different heuristic values
This problem is known as the Target Value Search Problem (TVS) and it can be succintly described as follows:
Given a graph $G(V,E)$, two nodes $s$ and $t$ ($s, t\in V)$ and a target value $T$ find a ...
- 3,383
2
votes
Accepted
Print the number of subarrays of an array having negative sums
An $O(n \log n)$ solution:
Find prefix sums $S[i] = \sum_{k=0}^{i} a[k]$
Set $S[-1] = 0$
Now count the number of inversion pairs in $S[-1], S[0], \dots, S[n-1]$
- 6,151
2
votes
Comparing A* search to Simulated Annealing
"Energy" is just the output of your cost function that you define for the SA problem. You are right that the two algorithms seem to have two different purposes, and in most cases, I would say that is ...
- 121
Only top scored, non community-wiki answers of a minimum length are eligible