CareerCup

Simple to find the disjoint sets present in a graph.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class FriendZone {

	public static void main(String[] args) {
		boolean[][] input = {{true,true,false},{true,true,true},{false,true,true}};
		System.out.println(find(input));
	}
	
	public static int find(boolean[][] input){
		int length = input.length;
		List<Set> list = new ArrayList<Set>();
		int totalNumberOfSets = length;
		for(int i=0;i<length;i++){
			HashSet<Integer> set = new HashSet<>();
			set.add(i);
			list.add(set);
		}
		for(int i=0;i<length;i++){
			for(int j=i+1;j<length;j++){
				if(input[i][j]){
					Set set0 = list.get(i);
					Set set1 = list.get(j);
					set0.addAll(set1);
					set1.clear();
					list.set(j, set0);
					totalNumberOfSets--;
				}
			}
		}
		return totalNumberOfSets;
	}

}

function solution(M){
let original = JSON.parse(M);
let result = [];
let done = [];
for(let i=0; i<original.length; i++){
if(done.indexOf(i) !== -1){
continue;
}

let row = original[i];

let newRow = [];
for(let j =0; j<row.length; j++){

if(row[j] || newRow,indexOf(j) !== -1){

mergeFriends(newRow.original[j])
done.push(j);
}
}
result[i] = newRow;

}


let output = '';
for(let i=0; i<result.length; i++){
let row = result[i];
if(row){
for(let j=0; j<row.length; j++){
output += row[j]+',';
}
output = output.substring(0,output.length-1);
output += '|';




}

}

output = output.substring(0,output.length-1);
return output;
}

function mergeFriends(row,friends){
for(let i =0; i<friends.length; i++){
let friend = friends[i];
if(friend && row.indexOf(i)<= -1){
row.push(i);
}
return row;
}
}

var solution = function(M) {
M = JSON.parse(M);
if(M.length === 0) {
return 0;
}

let len = M.length;
let result = [];
let nestedRes = [];

for(let i = 0; i < len; i++) {
for(let j = 0; j < len; j++) {
if(M[i][j] === 1) {
nestedRes.push(j);
M[i][j] = M[j][i] = '#';
}
}
if(!isSameSubset(result, nestedRes)) {
result.push(nestedRes);
}
nestedRes = [];
}
return result.join('|');
}

function isSameSubset(nestedArr, arr) {
if(nestedArr.length) {
for(var i=0; i<arr.length; i++) {
if(nestedArr.flat().indexOf(arr[i]) > -1){
return true;
}
}
} else {
return false;
}

}

solution("[[1,1,0],[1,1,0],[0,0,1]]")

var solution = function(M) {
M = JSON.parse(M);
if(M.length === 0) {
return 0;
}

let len = M.length;
let result = [];
let nestedRes = [];

for(let i = 0; i < len; i++) {
for(let j = 0; j < len; j++) {
if(M[i][j] === 1) {
nestedRes.push(j);
M[i][j] = M[j][i] = '#';
}
}
if(!isSameSubset(result, nestedRes)) {
result.push(nestedRes);
}
nestedRes = [];
}
return result.join('|');
}

function isSameSubset(nestedArr, arr) {
if(nestedArr.length) {
for(var i=0; i<arr.length; i++) {
if(nestedArr.flat().indexOf(arr[i]) > -1){
return true;
}
}
} else {
return false;
}

}

solution("[[1,1,0],[1,1,0],[0,0,1]]")

var solution = function(M) {
    M = JSON.parse(M);
    if(M.length === 0) {
        return 0;
    }
    
    let len = M.length;
    let result = [];
    let nestedRes = [];
    
    for(let i = 0; i < len; i++) {
        for(let j = 0; j < len; j++) {
            if(M[i][j] === 1) {
                nestedRes.push(j);
                M[i][j] = M[j][i] = '#';
            }
        }
        if(!isSameSubset(result, nestedRes)) {
             result.push(nestedRes);
        }
        nestedRes = [];
    }
    return result.join('|');
}

function isSameSubset(nestedArr, arr) {
    if(nestedArr.length) {
      for(var i=0; i<arr.length; i++) {
            if(nestedArr.flat().indexOf(arr[i]) > -1){
                return true;
            }
        }  
    } else {
        return false;
    }
    
}

solution("[[1,1,0],[1,1,0],[0,0,1]]")