It is a cloudy day in the Twin Cities of Minneapolis and St. Paul. Today I woke up around 05:00 AM. Read for about 45 minutes and then headed to the kitchen to prepare breakfast.
It is all over the news that most (never say all) states have started updating the stay home orders in order to give people more freedom to do the things we are used to. I fully agree that the economy needs to get back to what it was before the COVID-19 pandemic started. That said, we need to move slowly making sure that there are enough ICU beds for all people that requires them. If such quotas cannot be met, then we need to go back to a full quarantine. This type of cycle is well known and will come in the form of 
multiple waves.
In particular, in the State of Minnesota, the Mall of America and casinos (e.g., Mystic Lake Casino) are opening. My wife and I do not go to casinos. During the long winter months we go to the Mall of America early mornings before stores open to walk. At that time there are very few people. When we shop at the mall we visit Nordstrom and Macy’s.
I have been checking the number of COVID-19 deaths in Dakota Country which is where we live. The number of deaths appears to be going up. Today’s death count is 31. Not sure what will happen two to three weeks into the month of June. I guess it will be in the hundreds.
Some friends and family are not able to accept staying at home. They are waiting for stores, restaurants and bars to open to be with people. I rather keep my distance for a few more months until vaccines, treatments and enough ICU beds are readily available. That said, my son will meet us again at Costco in Minneapolis to stock up on some groceries (i.e., milk, yogurt, veggies) for three weeks. The store opens at 07:00 AM so not too many people are willing to be there at that time.
Please keep safe as much as possible. Science indicates that the second wave of the COVID-19 pandemic is starting.
The purpose of this post is to solve the Components in a graph problem. To be honest, after reading the description, noticing the missing figure and the 
incomplete Java code, I had second thoughts on solving the problem.
The problem is a candidate to be solved using a disjoint union set data structure. In my Disjoint Union Set post I implemented such data structure. As we will see in this post, the data structure and methods have been simplified. As usual, for the latest source code please visit my GitHub repository JohnCanessa/ComponentsInAGraph.
I created a GitHub repository. In the repo I edited a short and simple README.md file. I will add the link to this post after I publish this post in my WordPress site.
# **** **** C:\Users\johnc>dir 05/05/2020 01:51 PM <DIR> . 05/05/2020 01:51 PM <DIR> .. 09/22/2019 08:00 AM <DIR> .eclipse 03/15/2020 08:38 AM 59 .gitconfig 04/23/2020 11:11 AM <DIR> .p2 05/07/2020 08:11 AM 1,005,502 .pipwin 04/21/2020 08:07 AM <DIR> .pylint.d 09/22/2019 08:00 AM <DIR> .tooling 03/10/2020 03:53 PM <DIR> .vscode 03/10/2020 04:43 PM <DIR> 3D Objects 03/10/2020 04:43 PM <DIR> Contacts 04/08/2020 07:59 AM <DIR> ContainsCloseNums 02/17/2020 03:52 PM <DIR> Documents 05/07/2020 12:28 PM <DIR> Downloads 09/22/2019 07:57 AM <DIR> eclipse 09/22/2019 07:59 AM <DIR> eclipse-workspace_0 03/10/2020 04:43 PM <DIR> Favorites 03/10/2020 04:44 PM <DIR> Links 03/10/2020 04:43 PM <DIR> Music 09/12/2019 04:36 PM <DIR> NCH Software Suite 05/11/2020 07:22 AM <DIR> OneDrive 05/04/2020 03:42 PM <DIR> pipwin 03/10/2020 04:43 PM <DIR> Saved Games 03/10/2020 04:43 PM <DIR> Searches 03/10/2020 04:43 PM <DIR> Videos 05/05/2020 01:30 PM <DIR> vimfiles 05/08/2020 12:02 PM <DIR> workspace0 05/05/2020 01:51 PM 3,281 _viminfo # **** **** C:\Users\johnc>cd workspace0 # **** **** C:\Users\johnc\workspace0>dir 05/08/2020 12:02 PM <DIR> . 05/08/2020 12:02 PM <DIR> .. 04/01/2020 08:57 AM <DIR> BST-Search 04/27/2020 08:46 AM <DIR> ClassesInPython 04/10/2020 11:34 AM <DIR> ComposeRanges 04/08/2020 08:04 AM <DIR> ContainsCloseNums 05/08/2020 12:01 PM <DIR> CS50Python 05/07/2020 02:44 PM <DIR> DownToZeroII 04/05/2020 08:32 AM <DIR> GraphBFS 04/21/2020 07:46 AM <DIR> Knights 04/24/2020 08:33 AM <DIR> Minesweeper 04/17/2020 03:41 PM <DIR> MissingNumber 03/29/2020 08:30 AM <DIR> ORCost 04/23/2020 11:13 AM <DIR> Python-Tutorial-CS50 04/22/2020 04:37 PM <DIR> PythonTutorial 04/19/2020 07:46 AM <DIR> RobotInAGrid 03/10/2020 04:24 PM <DIR> SortOnFrequency 04/29/2020 02:47 PM <DIR> UsingWithPython 04/28/2020 02:52 PM <DIR> WorkingWithFiles # **** **** C:\Users\johnc\workspace0>git clone https://github.com/JohnCanessa/ComponentsInAGraph.git Cloning into 'ComponentsInAGraph'... remote: Enumerating objects: 3, done. remote: Counting objects: 100% (3/3), done. remote: Compressing objects: 100% (2/2), done. remote: Total 3 (delta 0), reused 0 (delta 0), pack-reused 0 Unpacking objects: 100% (3/3), 827 bytes | 9.00 KiB/s, done. # **** **** C:\Users\johnc\workspace0>dir 05/11/2020 12:13 PM <DIR> . 05/11/2020 12:13 PM <DIR> .. 04/01/2020 08:57 AM <DIR> BST-Search 04/27/2020 08:46 AM <DIR> ClassesInPython 05/11/2020 12:13 PM <DIR> ComponentsInAGraph 04/10/2020 11:34 AM <DIR> ComposeRanges 04/08/2020 08:04 AM <DIR> ContainsCloseNums 05/08/2020 12:01 PM <DIR> CS50Python 05/07/2020 02:44 PM <DIR> DownToZeroII 04/05/2020 08:32 AM <DIR> GraphBFS 04/21/2020 07:46 AM <DIR> Knights 04/24/2020 08:33 AM <DIR> Minesweeper 04/17/2020 03:41 PM <DIR> MissingNumber 03/29/2020 08:30 AM <DIR> ORCost 04/23/2020 11:13 AM <DIR> Python-Tutorial-CS50 04/22/2020 04:37 PM <DIR> PythonTutorial 04/19/2020 07:46 AM <DIR> RobotInAGrid 03/10/2020 04:24 PM <DIR> SortOnFrequency 04/29/2020 02:47 PM <DIR> UsingWithPython 04/28/2020 02:52 PM <DIR> WorkingWithFiles # **** **** C:\Users\johnc\workspace0>cd ComponentsInAGraph # **** **** C:\Users\johnc\workspace0\ComponentsInAGraph>dir 05/11/2020 12:13 PM 385 README.md # **** **** C:\Users\johnc\workspace0\ComponentsInAGraph>type README.md # ComponentsInAGraph HackerRank problem Attempt to solve the HackerRank problem at the following URI: https://www.hackerrank.com/challenges/components-in-graph/problem?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=24-hour-campaign using Java. To get my insights into the problem please visit the following post in my blog: T.B.D. Enjoy; John
After creating the GitHub repository I cloned it to one of my Windows 10 machines.
5
1 6
2 7
3 8
4 9
2 6
main <<< totalNodes: 20
union <<< high: 6 low: 1
componentsInGraph <<< 1 <-> 6
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
union <<< high: 7 low: 2
componentsInGraph <<< 2 <-> 7
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 2, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
union <<< high: 8 low: 3
componentsInGraph <<< 3 <-> 8
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 2, 3, 0, 0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
union <<< high: 9 low: 4
componentsInGraph <<< 4 <-> 9
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
union <<< high: 2 low: 1
componentsInGraph <<< 2 <-> 6
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 1, 3, 4, 0, 1, 1, 3, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
minAndMax <<< item: 1 freq: 4
minAndMax <<< item: 1 freq: 4
minAndMax <<< item: 3 freq: 2
minAndMax <<< item: 4 freq: 2
minAndMax <<< item: 1 freq: 4
minAndMax <<< item: 1 freq: 4
minAndMax <<< item: 3 freq: 2
minAndMax <<< item: 4 freq: 2
componentsInGraph <<< minAndMax: 2 4
componentsInGraph <<< maxAndMin: 2 4
2 4
This screen capture illustrates the only example for the problem. We start by taking in the number of edges expressed and pairs of nodes. In this example we have five pair.
By making a simple drawing we can observe the following relations and associated number of nodes:
| Relation | Edges | Node Counts |
| R1 | 1 <-> 2 <-> 6 <-> 7 | 4 |
| R2 | 3 <-> 8 | 2 |
| R3 | 4 <->9 | 2 |
The result for the minimum should be 2 and 4 for the maximum.
Now that we understand what the answer should be let’s get into the debug statements that I added to allow us to follow the process used to arrive to a solution.
The total number of nodes is set to 20. If you read the problem description, the number of nodes seems to be N * 2. In the example we should only consider positive natural numbers for nodes / vertices. The 2 in the N * 2 represents the total number of numbers in the two sets.
We use an array of integers to represent the parents of the nodes. Each node has a representative which is the node with the small value in a set. Initially all sets contain a single node with an integer value.
We will use the union method which we will implement shortly, to join the elements into a set. The set will be identified by the representative.
The first pair of numbers “1 6”, which represents our first edge modifies the parents array by setting position 1 to a 1 and position 6 to a 1. This means that parents[1] is the representative for the set and parents[6] is part of the set which at this time has two nodes.
We then process “2 7”. The parents array is updated in the union method. The parents[2] entry is set to 2 to indicate this is the representative for this new set and parents[7] is set to 2 to point to its representative.
The process repeats for “8 3” and “4 9”.
Now we reach the pair “2 6”. We modify the parent[2] and set it to 1 to indicate that the representative for parent[2] is parent[1].
If we look at the last update of the parents array, we can determine that values 1, 2, 5 and 7 belong to the same set with representative parent[1]. We can also observe that values 3 and 8 belong to a different set with representative parents[3]. Finally values 4 and 9 are in a different set with representative parent[4]. These observations match the previous table.
It seems that we have a minAndMax method which is used to get the frequencies of the counts. This seems to allow us to compute and return the set with a minimum and maximum number of elements which is exactly what is required by the problem.
6
0 1
1 3
2 5
2 8
9 4
6 9
main <<< totalNodes: 20
componentsInGraph <<< 0, 1
componentsInGraph <<< dus:
n: 20
parents: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 1, 3
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 2, 5
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 2, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 2, 8
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 2, 1, 0, 2, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 9, 4
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 2, 1, 4, 2, 0, 0, 2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 6, 9
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 2, 1, 4, 2, 4, 0, 2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
2 3
A different example with six pairs of integers.
6
0 1
1 2
3 4
6 7
7 8
8 9
main <<< totalNodes: 20
componentsInGraph <<< 0, 1
componentsInGraph <<< dus:
n: 20
parents: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 1, 2
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 3, 4
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 1, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 6, 7
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 1, 3, 3, 0, 6, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 7, 8
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 1, 3, 3, 0, 6, 6, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 8, 9
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 1, 3, 3, 0, 6, 6, 6, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
2 4
One additional example also with six pairs of integers.
3
0 2
4 2
3 1
main <<< totalNodes: 10
componentsInGraph <<< 0, 2
componentsInGraph <<< dus:
n: 10
parents: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 4, 2
componentsInGraph <<< dus:
n: 10
parents: [0, 0, 2, 0, 2, 0, 0, 0, 0, 0]
componentsInGraph <<< 3, 1
componentsInGraph <<< dus:
n: 10
parents: [0, 1, 2, 1, 2, 0, 0, 0, 0, 0]
2 2
An example with only three pairs of numbers.
8
0 2
2 4
4 6
6 8
1 3
3 5
5 7
7 9
main <<< totalNodes: 20
componentsInGraph <<< 0, 2
componentsInGraph <<< dus:
n: 20
parents: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 2, 4
componentsInGraph <<< dus:
n: 20
parents: [0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 4, 6
componentsInGraph <<< dus:
n: 20
parents: [0, 0, 2, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 6, 8
componentsInGraph <<< dus:
n: 20
parents: [0, 0, 2, 0, 2, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 1, 3
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 2, 1, 2, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 3, 5
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 2, 1, 2, 1, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 5, 7
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 2, 1, 2, 1, 2, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
componentsInGraph <<< 7, 9
componentsInGraph <<< dus:
n: 20
parents: [0, 1, 2, 1, 2, 1, 2, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
4 5
This final example contains a set of eight pairs of numbers. Sorry if I went overboard with examples. I did this to help you understand the process without using your computer. That said, I strongly recommend to fire up your computer and experiment with the code to make sure you fully understand (not memorize) it.
// **** number of total nodes in the graph (can go up to (15000 + 1) * 2) ****
static int totalNodes = 0;
// **** open scanner ****
private static final Scanner sc = new Scanner(System.in);
/**
* Test scaffolding.
*/
public static void main(String[] args) throws IOException {
// **** open buffered writer ****
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
// **** get the number of relations ****
int n = Integer.parseInt(sc.nextLine().trim());
// **** relations ****
int[][] gb = new int[n][2];
// **** read the relations and load the gb array ****
for (int gbRowItr = 0; gbRowItr < n; gbRowItr++) {
// **** read and split the values for this relation ****
String[] gbRowItems = sc.nextLine().split(" ");
// **** set the values in the gb array ****
for (int gbColumnItr = 0; gbColumnItr < 2; gbColumnItr++) {
// **** ****
int gbItem = Integer.parseInt(gbRowItems[gbColumnItr].trim());
gb[gbRowItr][gbColumnItr] = gbItem;
// **** update the number of nodes ****
totalNodes = Math.max(totalNodes, gbItem);
}
}
// **** finalize the total number of nodes ****
totalNodes = (totalNodes + 1) * 2;
// ???? ????
System.out.println("main <<< totalNodes: " + totalNodes);
// **** close scanner ****
sc.close();
// **** compute result ****
int[] result = componentsInGraph(gb);
// **** display result ****
String s = "" + result[0] + " " + result[1];
bufferedWriter.write(s, 0, s.length());
// **** write new line ****
bufferedWriter.newLine();
// **** close buffered writter ****
bufferedWriter.close();
}
We start with the test scaffolding. The one provided by HackerRank might work on their site, but does not on my computer. It seems like there are undefined objects.
We initialize the total number of nodes and then open a scanner to read the values. The use of the variable totalNodes will become clear later.
We read the number of pairs. We load an array of pairs. While we are loading the pair values we update the totalNodes variable with the maximum value for a node. After we are done with the loop we update the value of the totalNodes variable. If you have read the requirements for the problem in HackerRank you should have an idea for the purpose of this variable.
We then process the pair of nodes. The method componentsInGraph also returns the min and max values we need to comply with the requirements.
/**
* Complete the componentsInGraph function below.
*/
static int[] componentsInGraph(int[][] gb) {
// **** maximum number of nodes ****
// final int MAX_ELEMENTS = ((15000 + 1) * 2);
// **** instantiate the class ****
// DisjointUnionSets dus = new DisjointUnionSets(MAX_ELEMENTS);
DisjointUnionSets dus = new DisjointUnionSets(totalNodes);
// **** populate unions ****
for (int i = 0; i < gb.length; i++) {
// **** update union ****
dus.union(gb[i][0], gb[i][1]);
// ???? ????
System.out.println("componentsInGraph <<< " + gb[i][0] + ", " + gb[i][1]);
System.out.println("componentsInGraph <<< dus: " + dus.toString() + "\n");
}
// **** compute the min and max values ****
int[] results = dus.minAndMax();
// **** return results ****
return results;
}
This last code snippet illustrates the implementation of the componentsInGraph method. Instead of using the maximum number of elements required in the parents array, we will reduce it by using the totalNodes value.
We then loop through the pairs. On each pass we perform a union. Some information is displayed.
When done with the loop we make a call to the minAndMax method which will compute and return the min and max numbers we are required. The values are then returned in an array.
/**
* Disjoint Union Sets class
*/
class DisjointUnionSets {
// **** class members ****
int n;
int[] parents;
/**
* Constructor.
*/
public DisjointUnionSets(int n) {
this.n = n;
this.parents = new int[n];
}
/**
* Get the counts of the sets with min and max number of elements: O(n^2)
*/
int[] minAndMax() {
// **** declare and populate array of Integers with the values of the parents O(n) ****
Integer[] arr = new Integer[this.parents.length];
int i = 0;
for (int val : this.parents)
arr[i++] = val;
// **** create a list with the values in the parents ****
List<Integer> al = Arrays.asList(arr);
// **** initialize the min and max values ****
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
// **** traverse the array arr: O(n^2) ****
for (int item : arr) {
if (item != 0) {
// **** get the frequency of item in the list: O(n) ****
int freq = Collections.frequency(al, item);
// ???? ????
System.out.println("minAndMax <<< item: " + item + " freq: " + freq);
// **** update the min and max values ****
min = Math.min(min, freq);
max = Math.max(max, freq);
}
}
// **** package results ****
int[] result = { min, max };
// **** return results ****
return result;
}
/**
* Alternate approach to compute the min and max: O(n)
*/
int[] maxAndMin() {
// **** ****
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
// **** traverse parrents array inserting into hashmap: O(n) ****
for (int val : this.parents) {
hm.put(val, hm.getOrDefault(val, 0) + 1);
}
// ???? ????
// System.out.println("maxAndMin <<< hm: " + hm.toString());
// **** initialize the min and max values ****
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
// **** traverse hashmap looking for min and max: O(n) ****
Iterator<Entry<Integer, Integer>> it = hm.entrySet().iterator();
while (it.hasNext()) {
// **** ****
Entry<Integer, Integer> e = it.next();
// **** skip this key ****
if (e.getKey() == 0)
continue;
// **** update min and max ****
min = Math.min(e.getValue(), min);
max = Math.max(e.getValue(), max);
}
// **** package results ****
int[] result = { min, max };
// **** return results ****
return result;
}
/**
* Unite the set that includes x and y.
*/
void union(int x, int y) {
// **** set the modes in the parents array ****
if (parents[x] == 0)
parents[x] = x;
if (parents[y] == 0)
parents[y] = y;
// **** update the representative element of each set ****
if (parents[x] != 0 || parents[y] != 0) {
// **** get the low and high from these nodes ****
int high = Math.max(parents[x], parents[y]);
int low = Math.min(parents[x], parents[y]);
// ???? ????
System.out.println("union <<< high: " + high + " low: " + low);
// **** update to point to the proper representative ****
for (int i = 0; i < parents.length; i++) {
if (parents[i] == high)
parents[i] = low;
}
}
}
/**
* Return a string representation of the object.
*/
public String toString() {
// **** ****
StringBuilder sb = new StringBuilder();
//sb.append("\n n: " + this.n);
sb.append("\nparents: " + Arrays.toString(this.parents));
// **** ****
return sb.toString();
}
}
This last code snippet illustrates the implementation of an updated and simpler DisjointUnionSets class.
The main member is the parents array.
The constructor instantiates the necessary number of elements for the parents array leaving the values initialized to 0.
Next let’s look at the implementation of the union method. We set the nodes in the parents array. I was experimenting with 0 values so the next check does seem redundant at this time.
The idea is to get the high and low values for the parents that we have for the associated pair. We display the values.
Now we want to locate in the parents array the high value and set it to the low value to indicate that the low value is the representative for all other values in the parents array with the high value.
The minAndMax method is used to find and return the numbers of the set with the most and least numbers of nodes. We achieve this by instantiating and populating an array arr of Integer with the same values at the parents array. We need an array on Integer (not int) to generate a list (in this case an array list).
We then initialize the values for the min and max.
We declare a loop to traverse with the values in the array to obtain the frequency of the specified value in the array. This is the reason we moved from array of int, to array list of Integers so we can use the frequency method. We loop through all the items in the array. For each item we get the frequency in the array. For example, if the array contains four number fives, then the frequency would be four. The last step is to update the min and max values.
After the loop, we package the min and max values into an array and return the results array. Note that the minAndMax method has an execution O(n^2).
The maxAndMin method is an alternate approach to compute the min and max. We start by declaring a hash map.
We enter a loop in which we traverse the parents array and put the frequencies of each value into the hash map.
We then iterate through the hash map. We get a hash map entry. We skip the key with value zero. The requirements for the problem exclude zeros. We then update the min and max values.
When done with the loop we set the results array and return it.
Note that this and the previous method achieve the same results. The difference is in performance.
Finally the toString method is used to generate a DisjointUnionSets object string which we can display. This method is used to see the contents of the parents array. I commented out displaying the value of ‘n’.
I checked in the code into HackerRank. My solution passed the 39 test cases.
OK, we are done with the Java code. I used the Visual Studio Code IDE to generate the software for this post.
# **** ****
C:\Users\johnc>dir
05/13/2020 03:12 PM <DIR> .
05/13/2020 03:12 PM <DIR> ..
05/13/2020 03:07 PM 57 .angular-config.json
05/13/2020 03:03 PM <DIR> .config
09/22/2019 08:00 AM <DIR> .eclipse
03/15/2020 08:38 AM 59 .gitconfig
04/23/2020 11:11 AM <DIR> .p2
05/07/2020 08:11 AM 1,005,502 .pipwin
04/21/2020 08:07 AM <DIR> .pylint.d
09/22/2019 08:00 AM <DIR> .tooling
03/10/2020 03:53 PM <DIR> .vscode
05/13/2020 07:59 AM <DIR> 3D Objects
05/13/2020 07:59 AM <DIR> Contacts
04/08/2020 07:59 AM <DIR> ContainsCloseNums
02/17/2020 03:52 PM <DIR> Documents
05/13/2020 02:55 PM <DIR> Downloads
09/22/2019 07:57 AM <DIR> eclipse
09/22/2019 07:59 AM <DIR> eclipse-workspace_0
05/13/2020 07:59 AM <DIR> Favorites
05/13/2020 07:59 AM <DIR> Links
05/13/2020 07:59 AM <DIR> Music
05/13/2020 03:49 PM <DIR> my-app
09/12/2019 04:36 PM <DIR> NCH Software Suite
05/20/2020 07:05 AM <DIR> OneDrive
05/04/2020 03:42 PM <DIR> pipwin
05/13/2020 07:59 AM <DIR> Saved Games
05/13/2020 07:59 AM <DIR> Searches
05/11/2020 03:04 PM <DIR> source
05/13/2020 07:59 AM <DIR> Videos
05/05/2020 01:30 PM <DIR> vimfiles
05/19/2020 08:02 AM <DIR> workspace0
05/05/2020 01:51 PM 3,281 _viminfo
# **** ****
C:\Users\johnc>cd workspace0
# **** ****
C:\Users\johnc\workspace0>dir
05/19/2020 08:02 AM <DIR> .
05/19/2020 08:02 AM <DIR> ..
04/01/2020 08:57 AM <DIR> BST-Search
04/27/2020 08:46 AM <DIR> ClassesInPython
05/19/2020 11:44 AM <DIR> ComponentsInAGraph
04/10/2020 11:34 AM <DIR> ComposeRanges
04/08/2020 08:04 AM <DIR> ContainsCloseNums
05/08/2020 12:01 PM <DIR> CS50Python
05/19/2020 08:02 AM <DIR> DisjointSet
05/07/2020 02:44 PM <DIR> DownToZeroII
04/05/2020 08:32 AM <DIR> GraphBFS
04/21/2020 07:46 AM <DIR> Knights
04/24/2020 08:33 AM <DIR> Minesweeper
04/17/2020 03:41 PM <DIR> MissingNumber
03/29/2020 08:30 AM <DIR> ORCost
04/23/2020 11:13 AM <DIR> Python-Tutorial-CS50
04/22/2020 04:37 PM <DIR> PythonTutorial
04/19/2020 07:46 AM <DIR> RobotInAGrid
03/10/2020 04:24 PM <DIR> SortOnFrequency
04/29/2020 02:47 PM <DIR> UsingWithPython
04/28/2020 02:52 PM <DIR> WorkingWithFiles
# **** ****
C:\Users\johnc\workspace0>cd ComponentsInAGraph
# **** ****
C:\Users\johnc\workspace0\ComponentsInAGraph>git status
On branch master
Your branch is up to date with 'origin/master'.
Untracked files:
(use "git add <file>..." to include in what will be committed)
Solution.java
nothing added to commit but untracked files present (use "git add" to track)
# **** add the Solution.java ****
C:\Users\johnc\workspace0\ComponentsInAGraph>git add Solution.java
# **** ****
C:\Users\johnc\workspace0\ComponentsInAGraph>git status
On branch master
Your branch is up to date with 'origin/master'.
Changes to be committed:
(use "git restore --staged <file>..." to unstage)
new file: Solution.java
# **** ****
C:\Users\johnc\workspace0\ComponentsInAGraph>git log
commit 9f7fe72e27d9b772f14500191aa04eebde1696e4 (HEAD -> master, origin/master, origin/HEAD)
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
Date: Mon May 11 12:09:33 2020 -0500
Create README.md
# **** ****
C:\Users\johnc\workspace0\ComponentsInAGraph>git commit -m "code using previous post DisjointSet"
[master bdd9045] code using previous post DisjointSet
1 file changed, 183 insertions(+)
create mode 100644 Solution.java
# **** ****
C:\Users\johnc\workspace0\ComponentsInAGraph>git status
On branch master
Your branch is ahead of 'origin/master' by 1 commit.
(use "git push" to publish your local commits)
nothing to commit, working tree clean
# **** ****
C:\Users\johnc\workspace0\ComponentsInAGraph>git push origin master
Enumerating objects: 4, done.
Counting objects: 100% (4/4), done.
Delta compression using up to 12 threads
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 1.71 KiB | 1.71 MiB/s, done.
Total 3 (delta 0), reused 0 (delta 0)
To https://github.com/JohnCanessa/ComponentsInAGraph.git
9f7fe72..bdd9045 master -> master
# **** ****
C:\Users\johnc\workspace0\ComponentsInAGraph>git status
On branch master
Your branch is up to date with 'origin/master'.
nothing to commit, working tree clean
# **** ****
C:\Users\johnc\workspace0\ComponentsInAGraph>git log
commit bdd90459638ebf708a3765a74ef1697e3718b6f2 (HEAD -> master, origin/master, origin/HEAD)
Author: JohnCanessa <john.canessa@gmail.com>
Date: Wed May 20 11:52:49 2020 -0500
code using previous post DisjointSet
commit 9f7fe72e27d9b772f14500191aa04eebde1696e4
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
Date: Mon May 11 12:09:33 2020 -0500
Create README.md
In a console, I look for the folder holding the source code for this post. I start by checking git status. I add the code for the solution. I take a look at the log and then commit the changes. We are now ready to push them up to our GitHub repository. We push the changes and check the log. All seems to be fine.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 987 subscribers to my blog!!!
Keep safe during the COVID-19 pandemic.
John
Twitter: @john_canessa