Given two snapshots S1 and S2 of N elements, the task is to find the elements which are changing their groups and the ones that never formed groups with other group elements (Though they can break and form a separate subgroup).
Note: The position of a group and the elements inside a group can change. Groups can break into subgroups.
Examples:
Input: S1: {{1, 2, 3, 4}, {5, 6}, {7, 8}}, S2: {{1, 2}, {3}, {4, 5}, {7, 8}, {6}}
Output: {1 2 3 6 7 8}, {1 2 3 4 5 6}
Explanation: Elements in groups [1, 2], [3], [6], [7, 8] have never been
with an element from another group so the answer is [1, 2, 3, 6, 7, 8].
Elements in the group [7, 8] have not changed their group.
Otherwise, all other elements have broken or interchanged the group.Input: S1: {{1, 3, 8}, {2, 5}, {4}, {9, 6}, {7, 10, 11, 12}}, S2: {{1, 3}, {9}, {8}, {12, 11}, {7, 6}, {2, 5}, {4, 10}}
Output:{1 3 9 8 11 12 2 5}, {1 3 9 8 12 11 7 6 4 10}
Explanation: Elements in groups [1, 3], [9], [8], [11, 12], [2, 5] have not been
with an element from another group so answer is [1, 3, 9, 8, 11, 12, 2, 5].
Only [2, 5] have not changed their group.
All other elements have broken or interchanged the group.
Naive Approach: The basic approach to solve the problem as mentioned below:
- Loop through each group in snapshot-1 (group-1).
- Loop through each element in group-1.
- Find the element’s group in snapshot-2 (group-2).
- Check if group2 is a subset of group1 or if both have the same elements.
Time Complexity: O(N * (N + k) * k2) where N is the total number of elements and K is the maximum element in a group
Auxiliary Space: O(1)
Efficient approach: To solve the problem efficiently follow the below idea carefully:
- To find the people who changed their groups: It is easy to find those who didn’t changed their groups: if the group of element is the same in both the snapshots. All other elements have changed the group.
- To find the people who have never interacted outside of their groups: If the final group is a subset or equal to the initial group then its elements have never interacted outside their group.
- Since both of these problems compare the groups in snapshots so we can follow the same approach only difference is between how we compare the groups.
Follow the steps to solve the problem:
- Loop through each group in snapshot-2 (group-2).
- For any one person in group-2.
- Find the person’s group in snapshot-1 (group-1).
- Check if group2 is a subset of group1 or both, having the same people.
Below is the implementation for the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function to print vector elementsvoid printVector(vector<int> vec){ for (auto value : vec) { cout << value << " "; } cout << "\n";}// Function to check if one is subset of other// or they are equalbool isSubsetOrEqual(vector<int> parent, vector<int> child, bool strictEqual){ // Check for size equality if (strictEqual ? child.size() != parent.size() : child.size() > parent.size()) { return false; } // Initializing a hash set set<int> hashset; for (auto item : parent) { hashset.insert(item); } for (auto item : child) { if (hashset.find(item) == hashset.end()) return false; } return true;}// Function to append vectorvoid appendVector(vector<int>& result, vector<int> values){ for (auto value : values) { result.push_back(value); }}// Function to assign the groups of elementsunordered_map<int, int>getPersonToGroupIdxMap(vector<vector<int> > groups){ unordered_map<int, int> personToGroupIdxMap; for (int groupIdx = 0; groupIdx < groups.size(); groupIdx++) { for (auto person : groups[groupIdx]) { personToGroupIdxMap[person] = groupIdx; } } return personToGroupIdxMap;}// Function to find if interaction outside groupvector<int>peoplesInteractionCheck(vector<vector<int> > initialGroups, vector<vector<int> > finalGroups, bool strictEqual){ vector<int> result; unordered_map<int, int> initialPersonToGroupIdxMap = getPersonToGroupIdxMap(initialGroups); for (auto groupInFinal : finalGroups) { int person = groupInFinal[0]; int initialGroupIdx = initialPersonToGroupIdxMap[person]; vector<int> groupInInitial = initialGroups[initialGroupIdx]; bool isSubsetOrEqualResult = isSubsetOrEqual( groupInInitial, groupInFinal, strictEqual); // For equal case, add in result // if groups are not equal. if (strictEqual && !isSubsetOrEqualResult) { appendVector(result, groupInFinal); } // For subset case, add in result // if groups are subset or equal. if (!strictEqual && isSubsetOrEqualResult) { appendVector(result, groupInFinal); } } return result;}// Driver codeint main(){ vector<vector<int> > initialGroups{ { 1, 3, 8 }, { 2, 5 }, { 4 }, { 9, 6 }, { 7, 10, 11, 12 } }; vector<vector<int> > finalGroups{ { 1, 3 }, { 9 }, { 8 }, { 12, 11 }, { 7, 6 }, { 2, 5 }, { 4, 10 } }; vector<int> peopleWithNoOutsideInteractions = peoplesInteractionCheck(initialGroups, finalGroups, false); cout << "Elements with no outside interactions\n"; printVector(peopleWithNoOutsideInteractions); vector<int> peopleWhoSwitchedGroups = peoplesInteractionCheck(initialGroups, finalGroups, true); cout << "Elements that changed their groups\n"; printVector(peopleWhoSwitchedGroups); return 0;} |
Java
// Java code for the above approach:import java.util.*;class Main{ // Driver code public static void main(String[] args) { List<List<Integer> > initialGroups = new ArrayList<>(); initialGroups.add(Arrays.asList(1, 3, 8)); initialGroups.add(Arrays.asList(2, 5)); initialGroups.add(Arrays.asList(4)); initialGroups.add(Arrays.asList(9, 6)); initialGroups.add(Arrays.asList(7, 10, 11, 12)); List<List<Integer> > finalGroups = new ArrayList<>(); finalGroups.add(Arrays.asList(1, 3)); finalGroups.add(Arrays.asList(9)); finalGroups.add(Arrays.asList(8)); finalGroups.add(Arrays.asList(12, 11)); finalGroups.add(Arrays.asList(7, 6)); finalGroups.add(Arrays.asList(2, 5)); finalGroups.add(Arrays.asList(4, 10)); List<Integer> peopleWithNoOutsideInteractions = peoplesInteractionCheck(initialGroups, finalGroups, false); System.out.println( "Elements with no outside interactions"); printVector(peopleWithNoOutsideInteractions); List<Integer> peopleWhoSwitchedGroups = peoplesInteractionCheck(initialGroups, finalGroups, true); System.out.println( "Elements that changed their groups"); printVector(peopleWhoSwitchedGroups); } // Function to print vector elements private static void printVector(List<Integer> vec) { for (int value : vec) { System.out.print(value + " "); } System.out.println(); } // Function to check if one is subset of other // or they are equal private static boolean isSubsetOrEqual(List<Integer> parent, List<Integer> child, boolean strictEqual) { if (strictEqual ? child.size() != parent.size() : child.size() > parent.size()) { return false; } Set<Integer> hashset = new HashSet<>(parent); for (int item : child) { if (!hashset.contains(item)) return false; } return true; } // Function to assign the groups of elements private static Map<Integer, Integer> getPersonToGroupIdxMap(List<List<Integer> > groups) { Map<Integer, Integer> personToGroupIdxMap = new HashMap<>(); int groupIdx = 0; for (List<Integer> group : groups) { for (int person : group) { personToGroupIdxMap.put(person, groupIdx++); } } return personToGroupIdxMap; } // Function to find if interaction outside group private static List<Integer> peoplesInteractionCheck( List<List<Integer> > initialGroups, List<List<Integer> > finalGroups, boolean strictEqual) { List<Integer> result = new ArrayList<>(); Map<Integer, Integer> initialPersonToGroupIdxMap = getPersonToGroupIdxMap(initialGroups); for (List<Integer> groupInFinal : finalGroups) { int person = groupInFinal.get(0); int initialGroupIdx = initialPersonToGroupIdxMap.get(person); List<Integer> groupInInitial = new ArrayList<>(); for (List<Integer> g : initialGroups) { if ((g).contains((person))) groupInInitial = g; } boolean isSubsetOrEqualResult = isSubsetOrEqual( groupInInitial, groupInFinal, strictEqual); if (strictEqual && !isSubsetOrEqualResult) { result.addAll(groupInFinal); } if (!strictEqual && isSubsetOrEqualResult) { result.addAll(groupInFinal); } } return result; }}// This code is contributed by Tapesh(tapeshdua420) |
Python3
# python3 code for the above approach:# Function to print vector elementsdef printVector(vec): for value in vec: print(value, end=" ") print()# Function to check if one is subset of other# or they are equaldef isSubsetOrEqual(parent, child, strictEqual): # Check for size equality if (len(child) != len(parent) if strictEqual else len(child) > len(parent)): return False # Initializing a hash set hashset = set() for item in parent: hashset.add(item) for item in child: if (not(item in hashset)): return False return True# Function to append vectordef appendVector(result, values): for value in values: result.append(value)# Function to assign the groups of elementsdef getPersonToGroupIdxMap(groups): personToGroupIdxMap = {} for groupIdx in range(0, len(groups)): for person in groups[groupIdx]: personToGroupIdxMap[person] = groupIdx return personToGroupIdxMap# Function to find if interaction outside groupdef peoplesInteractionCheck(initialGroups, finalGroups, strictEqual): result = [] initialPersonToGroupIdxMap = getPersonToGroupIdxMap(initialGroups) for groupInFinal in finalGroups: person = groupInFinal[0] initialGroupIdx = initialPersonToGroupIdxMap[person] groupInInitial = initialGroups[initialGroupIdx] isSubsetOrEqualResult = isSubsetOrEqual( groupInInitial, groupInFinal, strictEqual) # For equal case, add in result # if groups are not equal. if (strictEqual and (not isSubsetOrEqualResult)): appendVector(result, groupInFinal) # For subset case, add in result # if groups are subset or equal. if ((not strictEqual) and isSubsetOrEqualResult): appendVector(result, groupInFinal) return result# Driver codeif __name__ == "__main__": initialGroups = [[1, 3, 8], [2, 5], [4], [9, 6], [7, 10, 11, 12]] finalGroups = [[1, 3], [9], [8], [12, 11], [7, 6], [2, 5], [4, 10]] peopleWithNoOutsideInteractions = peoplesInteractionCheck( initialGroups, finalGroups, False) print("Elements with no outside interactions") printVector(peopleWithNoOutsideInteractions) peopleWhoSwitchedGroups = peoplesInteractionCheck( initialGroups, finalGroups, True) print("Elements that changed their groups") printVector(peopleWhoSwitchedGroups) # This code is contributed by rakeshsahni |
C#
// C# code for the above approach:using System;using System.Collections.Generic;class GFG { // Driver code public static void Main(String[] args) { List<List<int> > initialGroups = new List<List<int> >(); initialGroups.Add(new List<int>() { 1, 3, 8 }); initialGroups.Add(new List<int>() { 2, 5 }); initialGroups.Add(new List<int>() { 4 }); initialGroups.Add(new List<int>() { 9, 6 }); initialGroups.Add( new List<int>() { 7, 10, 11, 12 }); List<List<int> > finalGroups = new List<List<int> >(); finalGroups.Add(new List<int>() { 1, 3 }); finalGroups.Add(new List<int>() { 9 }); finalGroups.Add(new List<int>() { 8 }); finalGroups.Add(new List<int>() { 12, 11 }); finalGroups.Add(new List<int>() { 7, 6 }); finalGroups.Add(new List<int>() { 2, 5 }); finalGroups.Add(new List<int>() { 4, 10 }); var peopleWithNoOutsideInteractions = peoplesInteractionCheck(initialGroups, finalGroups, false); Console.WriteLine( "Elements with no outside interactions"); printVector(peopleWithNoOutsideInteractions); var peopleWhoSwitchedGroups = peoplesInteractionCheck(initialGroups, finalGroups, true); Console.WriteLine( "Elements that changed their groups"); printVector(peopleWhoSwitchedGroups); } // Function to print vector elements private static void printVector(List<int> vec) { foreach(var value in vec) Console.Write($"{value} "); Console.WriteLine(); } // Function to check if one is subset of other // or they are equal private static bool isSubsetOrEqual(List<int> parent, List<int> child, bool strictEqual) { if (strictEqual ? child.Count != parent.Count : child.Count > parent.Count) return false; HashSet<int> hashset = new HashSet<int>(parent); foreach( var item in child) if (!hashset .Contains( (item))) return false; return true; } // Function to assign the groups of elements private static Dictionary<int, int> getPersonToGroupIdxMap(List<List<int> > groups) { Dictionary<int, int> personToGroupIdxMap = new Dictionary<int, int>(); int groupIdx = 0; foreach(var group in groups) { foreach(var person in group) { personToGroupIdxMap[person] = groupIdx++; } } return personToGroupIdxMap; } // Function to find if interaction outside group private static List<int> peoplesInteractionCheck(List<List<int> > initialGroups, List<List<int> > finalGroups, bool strictEqual) { var result = new List<int>(); var initialpersonToGroupIdxMap = getPersonToGroupIdxMap(initialGroups); foreach(var groupInFinal in finalGroups) { var person = groupInFinal[0]; var initialGroupIdx = initialpersonToGroupIdxMap[person]; var groupInInitial = new List<int>(); foreach(var g in initialGroups) { if ((g).Contains((person))) groupInInitial = g; } var isSubsetOrEqualResult = isSubsetOrEqual( groupInInitial, groupInFinal, strictEqual); if (strictEqual && !isSubsetOrEqualResult) result.AddRange(groupInFinal); if (!strictEqual && isSubsetOrEqualResult) result.AddRange(groupInFinal); } return result; }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// JavaScript code for the above approach:// Function to print vector elementsfunction printVector(vec){ for (var value of vec) { process.stdout.write(value + " "); } process.stdout.write("\n");}// Function to check if one is subset of other// or they are equalfunction isSubsetOrEqual(parent, child, strictEqual){ // Check for size equality if (strictEqual ? child.length != parent.length : child.length > parent.length) { return false; } // Initializing a hash set let hashset = new Set(); for (var item of parent) { hashset.add(item); } for (var item of child) { if (!hashset.has(item)) return false; } return true;}// Function to append vectorfunction appendVector(result, values){ result.push(...values)}// Function to assign the groups of elementsfunction getPersonToGroupIdxMap(groups){ let personToGroupIdxMap = {}; for (var groupIdx = 0; groupIdx < groups.length; groupIdx++) { for (var person of groups[groupIdx]) { personToGroupIdxMap[person] = groupIdx; } } return personToGroupIdxMap;}// Function to find if interaction outside groupfunction peoplesInteractionCheck(initialGroups, finalGroups, strictEqual){ let result = []; let initialPersonToGroupIdxMap = getPersonToGroupIdxMap(initialGroups); for (var groupInFinal of finalGroups) { let person = groupInFinal[0]; let initialGroupIdx = initialPersonToGroupIdxMap[person]; let groupInInitial = initialGroups[initialGroupIdx]; let isSubsetOrEqualResult = isSubsetOrEqual( groupInInitial, groupInFinal, strictEqual); // For equal case, add in result // if groups are not equal. if (strictEqual && !isSubsetOrEqualResult) { appendVector(result, groupInFinal); } // For subset case, add in result // if groups are subset or equal. if (!strictEqual && isSubsetOrEqualResult) { appendVector(result, groupInFinal); } } return result;}// Driver codelet initialGroups = [ [ 1, 3, 8 ], [ 2, 5 ], [ 4 ], [ 9, 6 ], [ 7, 10, 11, 12 ] ];let finalGroups = [[ 1, 3 ], [ 9 ], [ 8 ], [ 12, 11 ], [ 7, 6 ], [ 2, 5 ], [ 4, 10 ]];let peopleWithNoOutsideInteractions = peoplesInteractionCheck(initialGroups, finalGroups, false);console.log("Elements with no outside interactions"); printVector(peopleWithNoOutsideInteractions);let peopleWhoSwitchedGroups = peoplesInteractionCheck(initialGroups, finalGroups, true);console.log("Elements that changed their groups");printVector(peopleWhoSwitchedGroups);// This code is contributed by phasing17 |
Output
Elements with no outside interactions 1 3 9 8 12 11 2 5 Elements that changed their groups 1 3 9 8 12 11 7 6 4 10
Time complexity: O(N * k)
Auxiliary Space: O(N * k)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
