Reducing the execution time of Online Community-Even Groups challenge

I have a coding problem for which I have attempted to solve with the below coding. However, my program is assessed as too slow in its execution and thus needs to be optimized to reduce the execution time. Please help me in optimizing my program and reducing the execution time.


Problem definition:


People connect with each other in an online community. A connection
between Person I and Person J is represented as C I J.
When two persons belonging to different communities connect, the net
effect is merger of both communities which I and J belonged to.


We are only interested in finding out the communities with the member
count being an even number. Your task is to find out those
communities.


Input:


Input will consist of three parts:

• The total number of people on the social network (N)

-
Queries

• C I J, connect I and J * Q 0 0, print the number of communities

with even member-count




-1 will represent end of input.


Output:


For each query Q, output the number of communities with even
member-count


Sample Input:

5

Q 0 0

C 1 2

Q 0 0

C 2 3

Q 0 0

C 4 5

Q 0 0

-1

Output for above Sample Input:

0

1

0

1

Sample Input/Output Explanation:


For first query there are no members in any of the groups hence answer
is 0. After C 1 2, there is a group (let's take it as G1) with 1 and 2
as members hence total count at this moment is 1.


After C 2 3 total members in G1 will become {1, 2, 3} hence there are
no groups with even count.


After C 4 5 there formed a new group G2 with {4, 5} as members, hence
the total groups with even count is 1

Java Program:

```
import java.util.*;
import java.io.*;

public class OnlineCommunity2 {

/ Your master grid. /
//public List> lout = new ArrayList>();
public Object[] lout;
public int loutn;

/ Your inner grid /
public List lin = new ArrayList();

public static

Okay I understand this is a programming challenge so I won't comment on programming style or variable naming as one does not usually care in this case. But it would be nice if you'd tidy it up enough for us to see what you're doing. I can't quite make out what lout is supposed to be for example.

In any case I'd bet your performance issue comes from these two for loops:

for(int k=0; k) lout[k];
        if(l1.contains(n1))
        {
            flagi=true;
            break;
        }
        i++;
    }
    for(int k=0; k) lout[k];
        if(l1.contains(n2))
        {    
            flagj=true;
            break;
        }
        j++;
    }

The time complexity of List.contains() is linear in the number of elements. As the test progresses you'll end up with at least quadratic time. You need to swap your Lists for something with a quicker .contains(). I would suggest HashSet which has amortized constant time in look-up.

StackExchange Code Review Q#59910, answer score: 5