# Count of Smaller Number I && II

Count of Smaller Number I

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) and an query list. For each query, give you an integer, return the number of element in the array that are smaller that the given integer.

Example

For array `[1,2,7,8,5]`, and queries `[1,8,5]`, return `[0,4,2]`

Note

We suggest you finish problem Segment Tree Build and Segment Tree Query II first.

Challenge

Could you use three ways to do it.

1. Just loop
2. Sort and binary search
3. Build Segment Tree and Search.

Solution:  Version 1. sort + binary search O(nlogn) Time
//Version 2. Segment Tree. not as efficient as version 1.
//check <Count of Smaller Number II>

```public ArrayList<Integer> countOfSmallerNumber(int[] A, int[] queries) {
//Version 1. sort + binary search
//Version 2. Segment Tree. not as efficient as version 1.
//check <Count of Smaller Number before itself>
ArrayList<Integer> result = new ArrayList<>();
if (A == null || queries == null) {
return result;
}
if (A.length == 0) {
for (int i = 0; i < queries.length; i++) {
}
return result;
}
Arrays.sort(A);
for (int i = 0; i < queries.length; i++) {
int target = queries[i];
//find the last element A[i]<target, i+1 is the number
int start = 0;
int end = A.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (A[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (A[end] < target) {
} else if (A[start] < target) {
} else {
}
}
return result;
}```

Count of Smaller Number II

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) . For each element`Ai` in the array, count the number of element before this element `Ai` is smaller than it and return count number array.

Example

For array `[1,2,7,8,5]`, return `[0,1,2,3,2]`

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query II and Count of Smaller Number before itself I first.

Solution: Segment Tree. 这道题不能用sort+binary search的方法了因为顺序不能改变。

```public class SegmentTreeNode {
int start, end;
int count;
SegmentTreeNode left;
SegmentTreeNode right;
public SegmentTreeNode(int start, int end) {
this.start = start;
this.end = end;
this.count = 0;
}
}

public ArrayList<Integer> countOfSmallerNumberII(int[] A) {
ArrayList<Integer> result = new ArrayList<>();
if (A == null || A.length == 0) {
return result;
}
SegmentTreeNode node = buildSegmentTree(0, 10000);
for (int i = 0; i < A.length; i++) {
if (A[i] == 0) {
} else {
}
update(node, A[i]);
}
return result;
}

public SegmentTreeNode buildSegmentTree(int start, int end) {
SegmentTreeNode node = new SegmentTreeNode(start, end);
if (start < end) {
int mid = start + (end - start) / 2;
node.left = buildSegmentTree(start, mid);
node.right = buildSegmentTree(mid + 1, end);
node.count = node.left.count + node.right.count;
}
return node;
}

public int query(SegmentTreeNode node, int start, int end) {
if (node.start == start && node.end == end) {
return node.count;
}
int leftCount = 0, rightCount = 0;
int mid = node.start + (node.end - node.start) / 2;
if (start <= mid) {
if (end <= mid) {
leftCount = query(node.left, start, end);
} else {
leftCount = query(node.left, start, mid);
}
}
if (end > mid) {
if (start > mid) {
rightCount = query(node.right, start, end);
} else {
rightCount = query(node.right, mid + 1, end);
}
}
return leftCount + rightCount;
}

public void update(SegmentTreeNode node, int index) {
if (node.start == index && node.end == index) {
node.count = node.count + 1;
} else {
int mid = node.start + (node.end - node.start) / 2;
if (node.start <= index && index <= mid) {
update(node.left, index);
} else if (mid < index && index <= node.end) {
update(node.right, index);
}
node.count = node.left.count + node.right.count; //or node.count = node.count+1;
}
}```
Share

# Interval Sum I && II

Interval Sum I

Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers `[start, end]`. For each query, calculate the sum number between index start and end in the given array, return the result list.

Example

For array `[1,2,7,8,5]`, and queries `[(0,4),(1,2),(2,4)]`, return `[23,9,20]`

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query and Segment Tree Modify first.

Challenge

O(logN) time for each query

Solution: Version 1. prefix sum,
(Version 2. Segment tree: check Interval Sum II)

```public ArrayList<Long> intervalSum(int[] A,
ArrayList<Interval> queries) {
//Version 1. prefix sum,
//Version 2. Segment tree: check Interval Sum II
ArrayList<Long> result = new ArrayList<>();
if (A == null || queries == null || A.length == 0 || queries.size() == 0) {
return result;
}
Long[] prefixSum = new Long[A.length];
Long sum = 0L;
for (int i = 0; i < A.length; i++) {
sum += A[i];
prefixSum[i] = sum;
}
for (Interval interval : queries) {
if (interval.start == 0) {
} else {
}

}
return result;
}```

Interval Sum II

Given an integer array in the construct method, implement two methods `query(start, end)` and`modify(index, value)`:

• For query(start, end), return the sum from index start to index end in the given array.
• For modify(index, value), modify the number in the given index to value

Example

Given array A = `[1,2,7,8,5]`.

• `query(0, 2)`, return `10`.
• `modify(0, 4)`, change A[0] from 1 to 4.
• `query(0, 1)`, return `6`.
• `modify(2, 1)`, change A[2] from 7 to 1.
• `query(2, 4)`, return `14`.

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query and Segment Tree Modify first.

Challenge

O(logN) time for `query` and `modify`.

Solution: Segment Tree.

```public class Solution {
SegmentTreeNode root;

public class SegmentTreeNode {
int start, end;
int sum;
SegmentTreeNode left;
SegmentTreeNode right;
public SegmentTreeNode(int start, int end) {
this.start = start;
this.end = end;
}
}
public Solution(int[] A) {
if (A == null || A.length == 0) {
return;
}
this.root = buildSegmentTree(A, 0, A.length - 1);
}

private SegmentTreeNode buildSegmentTree(int[] A, int start, int end) {
SegmentTreeNode node = new SegmentTreeNode(start, end);
if (start == end) {
node.sum = A[start];
} else {
int mid = start + (end - start) / 2;
node.left = buildSegmentTree(A, start, mid);
node.right = buildSegmentTree(A, mid + 1, end);
node.sum = node.left.sum + node.right.sum;
}
return node;
}

public long query(int start, int end) {
if (start < this.root.start || end > this.root.end) {
return -1;
}
return query(this.root, start, end);
}

private long query(SegmentTreeNode root, int start, int end) {
if (root.start == start && root.end == end) {
return root.sum;
}
int mid = root.start + (root.end - root.start) / 2;
long leftSum = 0L, rightSum = 0L;
if (start <= mid) {
if (end <= mid) {
leftSum = query(root.left, start, end);
} else {
leftSum = query(root.left, start, mid);
}
}
if (end > mid) {
if (start > mid) {
rightSum = query(root.right, start, end);
} else {
rightSum = query(root.right, mid + 1, end);
}
}
return leftSum + rightSum;
}

public void modify(int index, int value) {
modify(this.root, index, value);
}

public void modify(SegmentTreeNode root, int index, int value) {
if (root.start == index && root.end == index) {
root.sum = value;
} else {
int mid = root.start + (root.end - root.start) / 2;
if (index <= mid) {
modify(root.left, index, value);
} else {
modify(root.right, index, value);
}
root.sum = root.left.sum + root.right.sum;
}
}
}```

# Majority Number I & II & III

Majority Number I （找一个出现次数>1/2的数）

Given an array of integers, the majority number is the number that occurs `more than half` of the size of the array. Find it.

Example

Given `[1, 1, 1, 1, 2, 2, 2]`, return `1`

Challenge

O(n) time and O(1) extra space

Solution: 用的抵消的思想，如果两个数不一样大，就相互抵消，一样大就保留， 用count计数

```public int majorityNumber(ArrayList<Integer> nums) {
int candidate = -1;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
if (count == 0) {
candidate = nums.get(i);
count++;
} else {
if (candidate == nums.get(i)) {
count++;
} else {
count--;
}
}
}
return candidate;
}```

Majority Number II （找一个出现次数>1/3的数）

Given an array of integers, the majority number is the number that occurs `more than 1/3` of the size of the array.

Find it.

Example

Given `[1, 2, 1, 2, 1, 3, 3]`, return `1`.

Note

There is only one majority number in the array.

Challenge

O(n) time and O(1) extra space.

Solution: 策略和I一样，只是现在有两个candidate,

```public int majorityNumber(ArrayList<Integer> nums) {
int candidate1 = -1;
int candidate2 = -1;
int count1 = 0;
int count2 = 0;
for (Integer num : nums) {
if (candidate1 == num) {
count1 ++;
} else if (candidate2 == num) {
count2 ++;
} else if (count1 == 0) {
candidate1 = num;
count1 = 1;
} else if (count2 == 0) {
candidate2 = num;
count2 = 1;
} else {
count1--;
count2--;
}
}
if (count1 == 0) {
return candidate2;
}
if (count2 == 0) {
return candidate1;
}
count1 = 0;
count2 = 0;
for (Integer num : nums) {
if (num == candidate1) {
count1++;
}
if (num == candidate2) {
count2++;
}
}
return count1 > count2 ? candidate1 : candidate2;
}```

Majority Number III （找一个出现次数>1/k的数）

Given an array of integers and a number k, the majority number is the number that occurs `more than 1/k` of the size of the array.

Find it.

Example

Given `[3,1,2,3,2,3,3,4,4,4]` and `k=3`, return `3`.

Note

There is only one majority number in the array.

Challenge

O(n) time and O(k) extra space

Solution: Similar approach as I & II

```public int majorityNumber(ArrayList<Integer> nums, int k) {
Map<Integer, Integer> majorityCounts = new HashMap<>();
for (Integer num : nums) {
if (majorityCounts.containsKey(num)) {
majorityCounts.put(num, majorityCounts.get(num) + 1);
} else {
if (majorityCounts.size() < k - 1) {
majorityCounts.put(num, 1);
} else {
List<Integer> toBeRemoved = new ArrayList<>();
for (Integer key : majorityCounts.keySet()) {
if (majorityCounts.get(key) > 1) {
majorityCounts.put(key, majorityCounts.get(key) - 1);
} else {
}
}
//important here: can not remove the element while iterating the set
//which will cause ConcurrentModificationException
for (Integer key : toBeRemoved) {
majorityCounts.remove(key);
}
}
}
}
Set<Integer> results = majorityCounts.keySet();
int maxCount = 0;
int candidate = 0;
for (Integer key : majorityCounts.keySet()) {
majorityCounts.put(key, 0);
}
for (Integer num : nums) {
if (majorityCounts.containsKey(num)) {
int count = majorityCounts.get(num) + 1;
majorityCounts.put(num, count);
if (count > maxCount) {
maxCount = count;
candidate = num;
}
}
}
return candidate;
}```

# Lintcode: Data Stream Median

#### Data Stream Median

Numbers keep coming, return the median of numbers at every time a new number added.

Example

For numbers coming list: `[1, 2, 3, 4, 5]`, return `[1, 1, 2, 2, 3]`.

For numbers coming list: `[4, 5, 1, 3, 2, 6, 0]`, return `[4, 4, 4, 3, 3, 3, 3]`.

For numbers coming list: `[2, 20, 100]`, return `[2, 2, 20]`.

Challenge

Total run time in O(nlogn).

Clarification

What’s the definition of Median? – Median is the number that in the middle of a sorted array. If there are n numbers in a sorted array A, the median is `A[(n - 1) / 2]`. For example, if `A=[1,2,3]`, median is `2`. If `A=[1,19]`, median is `1`.

Solution: 维护两个堆 左边是max heap右边是min heap。当有新的数进来时先比较两个heap的数量 永远让left和right的size一样或者left比right多1， 这样的话median永远是left.poll()。然后确定好应该加到哪个heap之后，要比较当前数和两个堆顶数的大小，来决定是直接把该数放到那个heap中还是应该把另外一个heap的root放过来然后把这个数放到另外那个堆里。

O(NlogN) time.

```public int[] medianII(int[] nums) {
if (nums == null || nums.length == 0) {
return nums;
}
int initialSize = 20;
int[] median = new int[nums.length];
Queue < Integer > leftHeap = new PriorityQueue < > (initialSize,
new Comparator < Integer > () {
public int compare(Integer a, Integer b) {
return b - a;
}
});
Queue < Integer > rightHeap = new PriorityQueue < > ();

for (int i = 0; i < nums.length; i++) {
if (leftHeap.size() > rightHeap.size()) {
//need to put this one to rightHeap
if (nums[i] >= leftHeap.peek()) {
rightHeap.offer(nums[i]);
} else {
rightHeap.offer(leftHeap.poll());
leftHeap.offer(nums[i]);
}
} else {
//need to put this one to leftHeap
if (leftHeap.isEmpty() && rightHeap.isEmpty()) {
leftHeap.offer(nums[i]);
} else {
if (nums[i] <= rightHeap.peek()) {
leftHeap.offer(nums[i]);
} else {
leftHeap.offer(rightHeap.poll());
rightHeap.offer(nums[i]);
}
}
}
median[i] = leftHeap.peek();
}
return median;
}```

# LRU Cache

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: `get` and `set`.

`get(key)` – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
`set(key, value)` – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Solution: Use a doubly linked list, with a head and tail node pointers, as well as a hashMap with all the key and node pairs.

1. When get(), it first checks if the key is in the map, if it is, remove that node from its original position and move to the tail (right before the tail node). if it doesn’t exists, return -1.

2. When set(key, value), it first call get function, to see if it exists, them update the value, otherwise, check if the queue is full, then remove the first element (the one right after head node) and add the new node to the tail.

Set(), Get() O(1) Time.

```public class Solution {
public class Node {
int key;
int value;
Node prev;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}

Map<Integer, Node> cache;
int capacity;
Node tail;

public Solution(int capacity) {
cache = new HashMap<>();
this.capacity = capacity;
tail = new Node(0, 0);
}

public int get(int key) {
if (cache.containsKey(key)) {
//remove it from its original place
//put to the tail the queue
Node node = cache.get(key);
removeNode(node);
return node.value;
}
return -1;
}

public void set(int key, int value) {
if (get(key) != -1) {
cache.get(key).value = value;
return;
}
Node newNode = new Node(key, value);
if (cache.size() < capacity) {
} else {
}
cache.put(newNode.key, newNode);
}

node.prev = tail.prev;
node.prev.next = node;
node.next = tail;
tail.prev = node;
}

public void removeNode(Node node) {
if (node.prev != null) {
node.prev.next = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
}
node.next = null;
node.prev = null;
}
}```

# Rehashing

The size of the hash table is not determinate at the very beginning. If the total size of keys is too large (e.g. size >= capacity / 10), we should double the size of the hash table and rehash every keys. Say you have a hash table looks like below:

`size=3`, `capacity=4`

```<code>[null, 21, 14, null]
↓    ↓
9   null
↓
null
</code>```

The hash function is:

```<code>int hashcode(int key, int capacity) {
return key % capacity;
}
</code>```

here we have three numbers, 9, 14 and 21, where 21 and 9 share the same position as they all have the same hashcode 1 (21 % 4 = 9 % 4 = 1). We store them in the hash table by linked list.

rehashing this hash table, double the capacity, you will get:

`size=3`, `capacity=8`

```<code>index:   0    1    2    3     4    5    6   7
hash : [null, 9, null, null, null, 21, 14, null]
</code>```

Given the original hash table, return the new hash table after rehashing .

Example

Given `[null, 21->9->null, 14->null, null]`,

return `[null, 9->null, null, null, null, 21->null, 14->null, null]`

Note

For negative integer in hash table, the position can be calculated as follow:

• C++/Java: if you directly calculate -4 % 3 you will get -1. You can use function: a % b = (a % b + b) % b to make it is a non negative integer.
• Python: you can directly use -1 % 3, you will get 2 automatically.

Solution:

Note: For negative integer in hash table, the position can be calculated as follow:
if you directly calculate -4 % 3 you will get -1.
You can use function: a % b = (a % b + b) % b to make it is a non negative integer.

```public ListNode[] rehashing(ListNode[] hashTable) {
if (hashTable == null) {
return null;
}
ListNode[] newHash = new ListNode[hashTable.length * 2];
int capacity = newHash.length;
for (int i = 0; i < hashTable.length; i++) {
ListNode node = hashTable[i];
while (node != null) {
int index = mod(node.val, capacity);
ListNode next = node.next; //need to remove the next pointer
node.next = null;
//if it is the first one
if (newHash[index] == null) {
newHash[index] = node;
} else {
ListNode runner = newHash[index];
while (runner.next != null) {
runner = runner.next;
}
runner.next = node;
}
hashTable[i] = next; //set to its next node
node = next;
}
}
return newHash;
}

//For negative integer in hash table, the position can be calculated as follow:
//if you directly calculate -4 % 3 you will get -1.
//You can use function: a % b = (a % b + b) % b to make it is a non negative integer.
public int mod(int A, int module) {
return (A % module + module) % module;
}```

# Heapify

Heapify

Given an integer array, heapify it into a min-heap array.

For a heap array A, A[0] is the root of heap, and for each A[i], A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].

Example

Given [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.

Challenge

O(n) time complexity

Clarification

What is heap?

• Heap is a data structure, which usually have three methods: push, pop and top. where “push” add a new element the heap, “pop” delete the minimum/maximum element in the heap, “top” return the minimum/maximum element.
What is heapify?
• Convert an unordered integer array into a heap array. If it is min-heap, for each element A[i], we will get A[i * 2 + 1] >= A[i] and A[i * 2 + 2] >= A[i].
What if there is a lot of solutions?
• Return any of them.

Solution 1: For each of the node in the heap array, use siftup method once.

```public void heapify(int[] A) {
if (A == null || A.length <= 1) {
return;
}
for (int i = 0; i < A.length; i++) {
siftUp(A, );
}
}

public void siftUp(int[] A, int index) {
int parentIndex = (index - 1) / 2;
while (parentIndex >= 0 && A[index] < A[parentIndex]) {
swap(A, index, parentIndex);
index = parentIndex;
parentIndex = (index - 1) / 2;
}
}

public void swap(int[] A, int a, int b) {
int tmp = A[a];
A[a] = A[b];
A[b] = tmp;
}```

Solution 2. for A[0, …, n/2-1] non leaf nodes, call siftDown method, O(n) time complexity.

```public void heapify(int[] A) {
if (A == null || A.length <= 1) {
return;
}
for (int i = A.length / 2 - 1; i >= 0; i--) {
siftDown(A, i);
}
}

public void siftDown(int[] A, int index) {
while (index < A.length) {
int smallest = index;
if (index * 2 + 1 < A.length && A[index * 2 + 1] < A[smallest]) {
smallest = index * 2 + 1;
}
if (index * 2 + 2 < A.length && A[index * 2 + 2] < A[smallest]) {
smallest = index * 2 + 2;
}
if (smallest == index) {
break;
}
swap(A, smallest, index);
index = smallest;
}
}

public void swap(int[] A, int a, int b) {
int tmp = A[a];
A[a] = A[b];
A[b] = tmp;
}```

# Hash Function

Hash Function

In data structure Hash, hash function is used to convert a string(or any other type) into an integer smaller than hash size and bigger or equal to zero. The objective of designing a hash function is to “hash” the key as unreasonable as possible. A good hash function can avoid collision as less as possible. A widely used hash function algorithm is using a magic number 33, consider any string as a 33 based big integer like follow:

hashcode(“abcd”) = (ascii(a) * 333 + ascii(b) * 332 + ascii(c) *33 + ascii(d)) % HASH_SIZE

= (97* 333 + 98 * 332 + 99 * 33 +100) % HASH_SIZE

= 3595978 % HASH_SIZE

here HASH_SIZE is the capacity of the hash table (you can assume a hash table is like an array with index 0 ~ HASH_SIZE-1).

Given a string as a key and the size of hash table, return the hash value of this key.f

Example

For key=”abcd” and size=100, return 78

Clarification

For this problem, you are not necessary to design your own hash algorithm or consider any collision issue, you just need to implement the algorithm as described.

Solution: Use a helper to avoid overflow.  To calculate a*33%HASH_SIZE, instead of multiply by 33, we add a to itself 33 times. if(result+num>mod) we only add num-mod it to the result, otherwise, just need to add num to result. In this case, we are either adding or removing HASH_SIZE from the final result so it won’t overflow.

```public int hashCode(char[] key, int HASH_SIZE) {
int result = 0;
for (int i = 0; i < key.length; i++) {
result = helper(result, 33, HASH_SIZE);
result += key[i];
result %= HASH_SIZE;
}
return result;
}

int helper(int num, int base, int mod) {
int result = 0;
for (int i = 0; i < base; i++) {
if (result + num > mod) {
result += num - mod;
} else {
result += num;
}
}
return result;
}```

# Topological Sorting

#### Topological Sorting

Given an directed graph, a topological order of the graph nodes is defined as follow:

• For each directed edge `A -> B` in graph, A must before B in the order list.
• The first node in the order can be any node in the graph with no nodes direct to it.

Find any topological order for the given graph.

Example

For graph as follow:

The topological order can be:

```<code>[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...
</code>```
Note

You can assume that there is at least one topological order in the graph.

Challenge

Can you do it in both BFS and DFS?

Solution 1. BFS

1. first create a map which contains all the nodes and its indegrees

2. only add node with 0 indegree to the list and once the node is select, remove 1 indegree from all its neighbors

```public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
//BFS
ArrayList<DirectedGraphNode> result = new ArrayList<>();
if (graph == null || graph.size() <= 1) {
return graph;
}
HashMap<DirectedGraphNode, Integer> inDegreeMap = new HashMap<>();
for (DirectedGraphNode node : graph) {
if (!inDegreeMap.containsKey(node)) {
inDegreeMap.put(node, 0);
}
for (DirectedGraphNode neighbor : node.neighbors) {
if (inDegreeMap.containsKey(neighbor)) {
inDegreeMap.put(neighbor, inDegreeMap.get(neighbor) + 1);
} else {
inDegreeMap.put(neighbor, 1);
}
}
}
while (!inDegreeMap.isEmpty()) {
for (DirectedGraphNode node : inDegreeMap.keySet()) {
if (inDegreeMap.get(node) == 0) {
inDegreeMap.remove(node);
for (DirectedGraphNode neighbor : node.neighbors) {
inDegreeMap.put(neighbor, inDegreeMap.get(neighbor) - 1);
}
break;
}
}
}
return result;
}```

# Clone Graph

Clone Graph

Clone an undirected graph. Each node in the graph contains a `label` and a list of its `neighbors`.
OJ’s undirected graph serialization:

Nodes are labeled uniquely.

We use `#` as a separator for each node, and `,` as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph `{0,1,2#1,2#2,2}`.

The graph has a total of three nodes, and therefore contains three parts as separated by `#`.

1. First node is labeled as `0`. Connect node `0` to both nodes `1` and `2`.
2. Second node is labeled as `1`. Connect node `1` to node `2`.
3. Third node is labeled as `2`. Connect node `2` to node `2` (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

```       1
/ \
/   \
0 --- 2
/ \
\_/
```

Solution: BFS遍历图 用Hash表存储Original Node-》 Copy Node 映射
O(n) time complexity, O(n) space

```public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
queue.offer(node);
UndirectedGraphNode copyRoot = new UndirectedGraphNode(node.label);
map.put(node, copyRoot);
while (!queue.isEmpty()) {
int count = queue.size();
for (int i = 0; i < count; i++) {
UndirectedGraphNode curr = queue.poll();
for (UndirectedGraphNode neighbor : curr.neighbors) {
if (!map.containsKey(neighbor)) {
queue.offer(neighbor);
UndirectedGraphNode currCopy = new UndirectedGraphNode(neighbor.label);
map.put(neighbor, currCopy);
}
}
}
}
for (UndirectedGraphNode originalNode : map.keySet()) {
for (UndirectedGraphNode neighbor : originalNode.neighbors) {