iframe-proxy | Sunbelt Computer Software

History

167 lines (139 loc) · 4 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

// @saorav21994

// SC : O(n)

// TC : O(total node references in original graph)

// BFS algo to parse and clone each reference 1-by-1. Map is used to prevent duplicate creation of existing node and get reference to previous node.

// Definition for a Node.

class Node {

public int val;

public List<Node> neighbors;

public Node() {

val = 0;

neighbors = new ArrayList<Node>();

}

public Node(int _val) {

val = _val;

neighbors = new ArrayList<Node>();

}

public Node(int _val, ArrayList<Node> _neighbors) {

val = _val;

neighbors = _neighbors;

}

class Solution {

public Node cloneGraph(Node node) {

if (node == null)

return node;

Map<Node, Node> map = new HashMap<>();

Queue<Node> queue = new LinkedList<>();

queue.offer(node);

map.put(node, new Node(node.val));

// BFS

while (!queue.isEmpty()) {

Node curr = queue.poll();

for (Node neigh : curr.neighbors) {

if (!map.containsKey(neigh)) {

map.put(neigh, new Node(neigh.val));

queue.offer(neigh);

}

map.get(curr).neighbors.add(map.get(neigh));

}

return map.get(node); // return the head

}

// Author : @romitdutta10

// SC : O(n)

// TC : O(total node references in original graph)

// DFS easy to understand

// Problem : https://leetcode.com/problems/clone-graph/

// Definition for a Node.

class Node {

public int val;

public List<Node> neighbors;

public Node() {

val = 0;

neighbors = new ArrayList<Node>();

}

public Node(int _val) {

val = _val;

neighbors = new ArrayList<Node>();

}

public Node(int _val, ArrayList<Node> _neighbors) {

val = _val;

neighbors = _neighbors;

}

class Solution {

Map<Node, Node> nodePool = new HashMap<>();

public Node cloneGraph(Node node) {

if(node == null) {

return null;

}

if(nodePool.containsKey(node)) {

return nodePool.get(node);

}

Node copy = new Node(node.val);

nodePool.put(node, copy);

List<Node> neighbours = new ArrayList<>();

for(Node neighbour : node.neighbors) {

Node copiedNeighbour = cloneGraph(neighbour);

neighbours.add(copiedNeighbour);

}

copy.neighbors = neighbours;

return copy;

}

// Author : @romitdutta10

// SC : O(n)

// TC : O(total node references in original graph)

// DFS optimized

// Problem : https://leetcode.com/problems/clone-graph/

// Definition for a Node.

class Node {

public int val;

public List<Node> neighbors;

public Node() {

val = 0;

neighbors = new ArrayList<Node>();

}

public Node(int _val) {

val = _val;

neighbors = new ArrayList<Node>();

}

public Node(int _val, ArrayList<Node> _neighbors) {

val = _val;

neighbors = _neighbors;

}

class Solution {

HashMap<Integer, Node> nodeMap = new HashMap<>();

public Node cloneGraph(Node node) {

if(node == null)

return null;

Node new_node;

if(nodeMap.get(node.val)!=null)

new_node = nodeMap.get(node.val);

else {

//System.out.println("Adding new node "+node.val);

new_node = new Node(node.val);

nodeMap.put(node.val, new_node);

}

List<Node> neighbors = new_node.neighbors;

for(Node n : node.neighbors){

//System.out.println("Traversing over neighbors "+n.val);

if(!neighbors.contains(n)){

if(nodeMap.get(n.val)!=null)

neighbors.add(nodeMap.get(n.val));

else

neighbors.add(cloneGraph(n));

}

return new_node;

}

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

CloneGraph.java

Latest commit

History

CloneGraph.java

File metadata and controls