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 $\...
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 ...
user avatar
  • 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'...
user avatar
  • 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 ...
user avatar
  • 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(...
user avatar
  • 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 ...
user avatar
  • 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^...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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,...
user avatar
  • 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(...
user avatar
  • 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 $...
user avatar
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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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+...
user avatar
  • 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) &...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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
user avatar
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$ ...
user avatar
  • 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 ...
user avatar
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]$
user avatar
  • 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 ...
user avatar
  • 121

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