(tl;dr: linked lists via array; 50 ms for 1 million items; code at end of article)
The chosen approach is well suited to the task, and on the conceptual level it is very clean and lean. The equivalence relations are represented as edges in a graph, and connected component discovery efficiently identifies the sets of equivalent items and tags their members.
It is just on the practical level that things get just as messy as they would be if one chose to model sets directly:
public Graph(int v) {
// ...
adj = new ArrayList<ArrayList<Integer>>();
// ...
for (int i = 0; i < v; i++) {
adj.add(new ArrayList<Integer>());
}
}
Therein lies a major issue - you are creating up to 10^6 lists just in case they might be needed, and this can eat up a big chunk of your allotted time.
Moreover, a maliciously crafted input file can contain up to 10^6 equivalences (assuming that you don't want to slow things down by essentially superfluous checks), so that changing the logic to creating the adjacency lists on demand does not change worst-case behaviour.
This is essentially the same problem one would face when choosing to model sets directly via the set-like structures offered by one's language libraries. Also, for good programming challenge sites it can be taken as given that all major types of problematic inputs will actually occur.
Hence it is best to implement the adjacency lists as linked lists here. During the input phase this gives you O(1) insertion (since you simply prepend to whatever is already there), and during the sweep you walk the list element by element anyway.
With modern runtimes it should be efficient enough to simply new
the nodes, so that no extra effort for efficient allocation would be needed. This is different from C/C++, where one would probably allocate a big array of them at the start of a test case and dole them out incrementally, so that all of them can be discarded afterwards en bloc with a single free()
or delete[]
. If this approach were chosen in Java or C# then it would be imperative to keep the blocks of nodes small enough that they do not get classified as 'large objects', which would cause problems with the garbage collector. This might be less of a concern for a programming challenge but in long-running code it could get nasty.
I concur with all respondents who recommended an iterative sweep instead of recursive function calls. Above-mentioned input file would likely blow the call stack to smithereens. Use an explicit stack or ArrayList<>
for storing nodes to be visited later while you are chasing the links of a given list.
There is no need to have separate fields for component id and a 'visited' flag, if you check the 'emptiness' of a component id during the sweep before assigning it. The key to speed and simplicity is slimming the code via measures like this, to reduce it to its essentials.
Note: Emily's advice to use an array of structs instead of a struct of arrays is sound, because it often leads to cleaner code that is easier to understand.
However, when performance is critical then it can be better to have separate arrays. This can have a major performance impact, since Java does not have value-type structs yet; in the present case you can achieve a five-fold speedup by using a two-dimensional array (which is poor man's array of value-type structs) or two separate arrays, instead of stuffing class references into an array as suggested by Emily.
Sometimes it can be beneficial to have separate arrays for reasons of CPU cache performance, especially if different phases of processing have markedly different access frequencies and patterns. In the present case that is unlikely to cause marked speed differences, unless one were coding in assembler or C/C++.
In the light of the comments it seems indicated to explain the linked list angle in a bit more detail. For easier benchmarking I've factored out the code that computes the equivalence classes (a.k.a. 'connected component ids') from the pairs of equal items. I'm showing the code in a hashish language because I don't have a Java environment handy but I don't want to post code that is not fully tested. I've removed all production-quality noise like assertions and nulling of unused references, in order to make the code more readable.
First, the Node class:
class Node
{
public int target;
public Node next;
public Node (int target, Node next)
{
this.target = target;
this.next = next;
}
}
And now the code for computing the equivalence classes. Apart from the use of linked lists and iterative sweeping with an explicit stack instead of recursive function calls it is based on the same algorithm as Santosh's solution. It is just packaged differently.
static int[] equivalence_classes_for_pairs (IEnumerable<Tuple<int,int>> pairs, int max_n)
{
var list_heads = new Node[max_n + 1]; // +1 because of index base 0
foreach (var pair in pairs)
{
list_heads[pair.Item1] = new Node(pair.Item2, list_heads[pair.Item1]);
list_heads[pair.Item2] = new Node(pair.Item1, list_heads[pair.Item2]);
}
var equivalence_classes = new int[list_heads.Length]; // equivalence class for i, or 0 if unknown
var more_chains = new Stack<Node>();
int class_count = 0;
Trace.Assert(list_heads[0] == null);
for (int i = 1; i <= max_n; ++i)
{
Node node = list_heads[i];
if (node == null || equivalence_classes[i] != 0)
continue; // nothing there, or already visited
int current_class = ++class_
equivalence_classes[i] = current_class;
while (true)
{
for ( ; node != null; node = node.next)
{
if (equivalence_classes[node.target] == 0) // not visited yet
{
equivalence_classes[node.target] = current_class;
more_chains.Push(list_heads[node.target]);
}
}
if (more_chains.Count == 0)
break;
node = more_chains.Pop();
}
}
for (int i = 1; i <= max_n; ++i)
if (equivalence_classes[i] == 0)
equivalence_classes[i] = ++class_count;
return equivalence_classes;
}
On my machine this takes about 250 ms for 10^6 pairs. Separate measurements show that the bulk of that time is spent in new Node()
; creating 2 million nodes took about 200 ms whereas pulling them from a free list took only 5 ms. This suggests a possible improvement if the cost of creating the nodes can be amortised over several test cases. I cooked up a few functions that could be used as drop-in replacements in the above code:
static Node free_list = create_free_list(2 * MAX_N);
static Node create_free_list (int n)
{
Node head = null;
for (int i = 0; i < n; ++i)
head = new Node(0, head);
return head;
}
static Node new_Node (int target, Node next)
{
Node node = free_list;
free_list = node.next;
node.target = target;
node.next = next;
return node;
}
static Node free_and_get_next (Node node)
{
Node next = node.next;
node.next = free_list;
free_list = node;
return next;
}
With this, the changes in the earlier functions are limited to replacing new Node
with new_Node
, and node = node.next
with node = free_and_get_next(node)
. However, I'm not showing the code here because the final code that implements linked lists by indexing into an array is so much simpler, cleaner, and even slightly faster.
Using preallocation via a free list reduces the running time from 250 ms to 50 ms. For a single call the 200 ms for creating the free list with 2 million nodes would have to be added, resulting in a net change of zero, but if there is more than one call then the cost of node creation is spread and overall time taken is reduced. A similar argument can be made for ArrayList
, where creation is roughly five times as costly as clearing.
However, the task description gives 10^6 as the total limit over all test cases in an input file (up to 10 per file). This makes it less likely that the cost of creating 2 million nodes can be be spread enough to result in a major improvement.
An alternative that is worth exploring is to use an array to achieve fast and efficient allocation. I.e. nodes[i, 0]
would be equivalent to Node.target
and nodes[i, 1]
would be equivalent to Node.next
. An alternative would be to have separate targets[]
and links[]
arrays, for a slight improvement in readability. In any case an allocated
counter would be initialised to 0 at the beginning of the procedure and henceforth always point at the next free slot. No freeing of slots ('list nodes') is necessary.
The time for a million pairs is 50 ms, and the code is actually a bit simpler than the code using pointers (since the allocation management overhead consists only of incrementing a counter, no free list management is necessary). This makes the array variant of linked lists the overall winner, and 50 ms looks fairly good for Java/C#.
Here's a rendering that uses a value-type struct instead of separate array dimensions, for readability. In Java only two 'plain' array versions are applicable but the principle remains the same; the struct definition won't be needed there but in exchange the function body gets a bit more verbose.
struct ListNode
{
public int target;
public int next;
public ListNode (int target, int next)
{
this.target = target;
this.next = next;
}
}
Note: since ListNode
is a value-type, operator new
does not allocate anything on the heap. The compiler simply puts an anonymous variable on the stack and initialises the structure fields as dictated by the constructor. On the native code level this should be virtually the same as code that uses separate array dimenions (at most a teeny bit less efficient). The version show here simply gives readable names to the two array dimensions, in a manner of speaking, and it minimises the number of array indexings.
static int[] equivalence_classes_for_pairs_v7 (IEnumerable<Tuple<int,int>> pairs, int max_n)
{
var list_heads = new int[max_n + 1]; // +1 because of index base 0
var list_nodes = new ListNode[1 + 2 * pairs.Count()];
int allocated = 1; // slot 0 is used as sentinel, and slot index 0 signifies 'empty'
foreach (var pair in pairs)
{
list_nodes[allocated] = new ListNode(pair.Item2, list_heads[pair.Item1]);
list_heads[pair.Item1] = allocated++;
list_nodes[allocated] = new ListNode(pair.Item1, list_heads[pair.Item2]);
list_heads[pair.Item2] = allocated++;
}
var equivalence_classes = new int[list_heads.Length]; // 0 if not assigned yet
int class_count = 0;
var more_chains = new Stack<int>();
for (int i = 1; i <= max_n; ++i)
{
if (equivalence_classes[i] != 0)
continue;
int current_class = ++class_count;
equivalence_classes[i] = current_class;
more_chains.Push(0); // sentinel
for (int p = list_heads[i]; p != 0; p = more_chains.Pop())
{
while (p != 0)
{
ListNode node = list_nodes[p];
if (equivalence_classes[node.target] == 0) // not visited yet
{
equivalence_classes[node.target] = current_class;
more_chains.Push(list_heads[node.target]);
}
p = node.next;
}
}
}
return equivalence_classes;
}
P.S.: Thanks to Santosh for bringing this nice problem to our attention - it taught me a lot about sets, linked lists, and efficient bulk allocation in Java/C#. Plus, it is always a pleasure in itself to take a solution idea for a well-confined problem, to strip it to its essentials and then make the code sing. Apologies to Emily for any unnecessary rudeness on my part - her advice is sound and important. At first glance, style and maintainability might seem a non-issue for the throw-away code of a coding challenge submission. However, we all do these challenges to learn something that stays, and at the end of the day Emily's lessons are bound to be much more generally applicable than aspects of my particular solution to this particular problem.