I have m lines with values x and y space separated that represent the user ids. This is like a user x follows user y on Facebook or Instagram etc. Now if we have a pair of z and y then since z follows y, as we already have a group [x,y] then we can merge z to form [x,y,z]

Example:

1 2
3 4
5 6
1 5

we can have below groups:

[1 2 5 6] and [3 4], the length of the largest group [1,2,5,6] is 4 will be the answer.

Here is my approach to this:

public int process(int m, int[][] arr) {
    List<Set<Integer>> list = new ArrayList<>();
    
    int ans = 0;
    for(int i=0; i<m; i  ) {
        int x = arr[i][0], y = arr[i][1];
        if(j ==0) {
            Set<Integer> set = new HashSet<>();
            list.add(set);
            set.add(x);
            set.add(y);
            ans = 2;
            continue;
        }
        boolean found = false;
        for(Set<Integer> set : list) {
            if(set.contains(x) || set.contains(y)) {
                set.add(x);
                set.add(y);
                ans = Math.max(ans, set.size());
                found = true;
                break;
            }
        }
        if(!found) {
            Set<Integer> set = new HashSet<>();
            list.add(set);
            set.add(x);
            set.add(y);
        }
    }
    return ans;
} 

My approach itself is wrong as my list generated is not grouping elements correctly. How to solve this problem. Also the input array length can be up to 100 000, so need to solve this in less time complexity.

Constraints:

x and y can range from 1 to 10^5
aray length can be up to 10^6

CodePudding user response：

You can use a disjoint set, starting with each group having size 1 and combining the sizes when merging.

public int process(int m, int[][] arr) {
    class DS {
        static int[] p = new int[100001];
        static int[] size = new int[100001];
        static int find(int x) {
            return x == p[x] ? x : (p[x] = find(p[x]));
        }
        static int merge(int x, int y) {
            int rx = find(x), ry = find(y);
            if (rx != ry) {
                p[rx] = ry;
                size[ry]  = size[rx];
            }
            return size[ry];
        }
        static void init() {
            for (int i = 0; i < p.length; i  ) {
                p[i] = i;
                size[i] = 1;
            }
        }
    }
    DS.init();
    int ans = 0;
    for (int[] pair: arr) 
        ans = Math.max(ans, DS.merge(pair[0], pair[1]));
    return ans;
}

CodePudding user response：

This data can be represented as a Disjointed Graph. And the problem boils down to finding the largest connected component in this graph.

For that, we need to iterate over the Vertices (which would represent Users) of the Graph. And for each vertex that hasn't been yet examined, we need to fire a traversal logic to find the size of the group to which this vertex belongs (for that purpose, DFS algorithm implementation is used in code below).

The time complexity of this approach would be linear O(n) (assuming there are n ids) because every Vertex would be examined only once.

class UserGraph {
    
    private Map<Integer, User> userById = new HashMap<>(); // contains all vertices of the graph
    
    private UserGraph() {} // no way and no need to invoke this constructor from the outside of the class
    
    public static UserGraph getInstance(int[][] arr) {
        UserGraph graph = new UserGraph();
        for (int[] connection: arr) {
            graph.addConnection(connection[0], connection[1]);
        }
        return graph;
    }
    
    public void addConnection(int id1, int id2) { // for simplicity connection would be mutual
        User user1 = userById.computeIfAbsent(id1, User::new);
        User user2 = userById.computeIfAbsent(id2, User::new);
        user1.addFollower(user2);
        user2.addFollower(user1);
    }
    
    public int getLargestGroupSize() {
        Set<User> seen = new HashSet<>();
        int maxSize = 0;
        for (User user: userById.values()) {
            if (seen.add(user)) {
                int groupSize = getGroupSize(seen, user);
                maxSize = Math.max(maxSize, groupSize);
            }
        }
        return maxSize;
    }
    
    public int getGroupSize(Set<User> seen, User user) {
        Deque<User> stack = new ArrayDeque<>();
        stack.add(user);
        int groupSize = 0;
        while (!stack.isEmpty()) {
            User current = stack.pop();
            groupSize  ;
            
            for (User follower: current.getFollowers()) {
                if (seen.add(follower)) stack.push(follower);
            }
        }
        return groupSize;
    }
    
    private static class User {
        private int id;
        private List<User> followers = new ArrayList<>();
        
        public User(int id) {
            this.id = id;
        }
        
        public void addFollower(User user) {
            followers.add(user);
        }
        
        public List<User> getFollowers() {
            return followers;
        }
    }
}

main()

public static void main(String[] args) {
    int[][] arr = {
        {1, 2},
        {3, 4},
        {5, 6},
        {1, 5}
    };
    
    UserGraph graph = UserGraph.getInstance(arr);
    System.out.println(graph.getLargestGroupSize());
}

Output:

4