Programming Challenges


Class 02: Data Structures

11 Jul 2013

Links from class:

There are a number of important features in Java that can help you write smaller, faster, bug-free code. Here are some of my favorites:

Union-Find Disjoint Sets

Section 2.3.2 in Competitive Programming gives a nice description of Union-Find Disjoint Sets. Below is Java code that could be used to solve problem C or any union-find problem in general. This data structure comes up again and again in programming contests.

public class UnionFind {
    int sets[] = new int[100];
    int nextId = 0;
    public void init() {
        for (int i = 0; i < sets.length; i++) {
            sets[i] = i;

    public void union(int s1, int s2) {
        sets[s2] = s1;
    public int find(int index) {
        if (sets[index] == index) {
            return index;
        return sets[index] = find(sets[index]);

    public void run() throws Exception {
        /* Do stuff */
    public static void main(String[] args) throws Exception {
        new UnionFind().run();


For next class

Assigned readings:

  • Programming Challenges: Chapter 2 – skip over Binary Indexed (Fenwick) Trees and Segment Trees

Assigned problems:

Assigned exercise: