# Finding max of two elements in linear time with restriction

I have a matrix in the following form:

ID | # Counts for ID | ID's Within Range.
1  | 5               | 1,2,3
2  | 3               | 1,2
3  | 2               | 1,3
....


The idea is that I want to find the 2 id's that when you sum the have the highest count. However, you must first exclude the pairs that overlap. For instance, id's 1 and 2 have the highest count but you can't use them since 1 has 2 within range and 2 has 1 within range. Thus from the table above you would use 2,3 as the sum since they don't overlap.

I would like to do this in O(n) or O(nlogn) time and O(n) storage. It's trivial to do if I first make all ID pairs but that gives me O(n^2). I can also do 2 forloops after sorting the list but that would also be at worst O(n^2) although usually much faster... Any help would be greatly appreciated! THanks!

• Is $n$ the number of IDs or the number of overlaps? If it's the number of IDs, you can't even read the entire input in $O(n)$ time. Apr 23 '13 at 17:38
• If there are n rows, why would it not take O(n) to read it? Each row is read at some constant. Thus it takes c per row, cn total -> O(n). You can assume the matrix is already constructed and you don't need to figure out the overlaps. You can just read them in. Apr 23 '13 at 18:14
• Because, before your comment, you hadn't said "word RAM" or anything to that effect. $\hspace{.62 in}$ What "Range"s are you referring to? $\:$
– user6973
Apr 23 '13 at 22:14
• it's not even about word RAM, the problem is how long is the list of IDs within range for each ID. The time to read the input is the total length of all these lists. Apr 24 '13 at 3:33
• Specifically: As you've described the problem, each of the $n$ IDs could overlap $n-1$ other IDs. So you cannot read each row in constant time. Apr 24 '13 at 15:19

Ok, so as I understand it, you are given as input an undirected graph (representing the "within range" restrictions) with weights on its vertices, and you want to find a non-adjacent pair of vertices that has maximum total weight. I'm going to interpret linear time as being linear in the number of edges in the input graph, not just the number of vertices, because otherwise it doesn't make sense — you need to have enough time to be able to look at the whole input.

Here's an $O(m+n)$ time solution (simplifying an earlier solution I posted here):

• Assume for simplicity that $n$ is a power of two (if not round up).

• Find the median of the vertex weights, the median of the highest $n/2$ vertex weights, the median of the highest $n/4$ vertex weights, etc. These median computations take a total of $O(n)$ time, and once completed they give you the set of $2^i$ largest weights for every choice of an integer $i$

• For each vertex $v$ with degree $d_v$, let $i_v=\lceil\log_2(d_v+1)\rceil$. Form the pairs $(v,w)$ where $w$ is in the set of $2^{i_v}$ largest vertex weights found during the median calculations.

• From the sets of pairs found in the previous step, remove the pairs that correspond to adjacent pairs of vertices (either by using a hash table of edges for fast adjacency lookup, or by using two passes of bucket sort to make a sorted list of both pairs and input edges).

• The remaining pairs for each vertex $v$ necessarily include the heaviest nonadjacent neighbor of $v$. In particular the heaviest nonadjacent pair in the whole graph is somewhere in this list of pairs. Compute the weight for each pair and choose the max.