LeetCode 1257: Smallest Common Region
LeetCode 1257 Solution Explanation
Explanation:
To find the smallest common region between two given regions in a hierarchy, we can follow these steps:
- Build a map to store the parent-child relationships for each region.
- Find the path from the given regions to the root.
- Compare the two paths to find the smallest common region.
Time complexity: O(n) where n is the number of regions Space complexity: O(n) for storing the parent-child relationships
LeetCode 1257 Solutions in Java, C++, Python
import java.util.*;
class Solution {
public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
Map<String, String> parent = new HashMap<>();
for (List<String> region : regions) {
String par = region.get(0);
for (int i = 1; i < region.size(); i++) {
parent.put(region.get(i), par);
}
}
Set<String> path1 = new HashSet<>();
String curr = region1;
while (curr != null) {
path1.add(curr);
curr = parent.get(curr);
}
curr = region2;
while (curr != null) {
if (path1.contains(curr)) {
return curr;
}
curr = parent.get(curr);
}
return null;
}
}Interactive Code Editor for LeetCode 1257
Improve Your LeetCode 1257 Solution
Use the editor below to refine the provided solution for LeetCode 1257. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...