Problem Statement
In this problem, you are provided with a 0-indexed 2D integer array named pairs. Each element of pairs is itself a pair represented as [starti, endi]. You need to rearrange the pairs such that the arrangement becomes "valid". A "valid" arrangement is defined where for every consecutive pair in the sequence (from the second pair onwards), the first element of the current pair (starti) equals the second element of the previous pair (endi-1). The task is to return any valid arrangement of these pairs. The problem guarantees at least one valid arrangement exists for the given input.
Examples
Example 1
Input:
pairs = [[5,1],[4,5],[11,9],[9,4]]
Output:
[[11,9],[9,4],[4,5],[5,1]]
Explanation:
This is a valid arrangement since endi-1 always equals starti. end0 = 9 == 9 = start1 end1 = 4 == 4 = start2 end2 = 5 == 5 = start3
Example 2
Input:
pairs = [[1,3],[3,2],[2,1]]
Output:
[[1,3],[3,2],[2,1]]
Explanation:
This is a valid arrangement since endi-1 always equals starti. end0 = 3 == 3 = start1 end1 = 2 == 2 = start2 The arrangements [[2,1],[1,3],[3,2]] and [[3,2],[2,1],[1,3]] are also valid.
Example 3
Input:
pairs = [[1,2],[1,3],[2,1]]
Output:
[[1,2],[2,1],[1,3]]
Explanation:
This is a valid arrangement since endi-1 always equals starti. end0 = 2 == 2 = start1 end1 = 1 == 1 = start2
Constraints
1 <= pairs.length <= 105pairs[i].length == 20 <= starti, endi <= 109starti != endi- No two pairs are exactly the same.
- There exists a valid arrangement of
pairs.
Approach and Intuition
To solve this problem and find a valid sequence of pairs that satisfies the condition endi-1 == starti, one possible approach is to treat the pairs as edges of a directed graph. In this graph, each pair [a, b] can be seen as a directed edge from vertex a to vertex b.
Steps to approach:
- Construct a mapping of each pair start element to its pair for quick lookup. This would help in finding the next pair in sequence quickly.
- Also, maintain an in-degree counter for each element to find the starting point of the sequence. The starting point typically would have an in-degree of zero (indicating no other pairs point to it), but since there's always a valid arrangement, we can start from any pair and attempt to create the sequence.
- Start with the first unvisited pair, and using the mapping, continuously append the subsequent pair to the result where the current pair’s second element matches the next pair's first element.
- This effectively builds up a path, or cycle-like sequence, which should be valid given the problem guarantees at least one valid arrangement.
Key Intuitions:
- Since the input guarantees at least one valid solution, we can confidently use the graph traversal approach without concern for dead-ends where a valid sequence cannot be created.
- Handling of mappings and direct checks to match pairs ensures the solution remains efficient and can handle the upper limits of the constraints effectively.
- Each vertex in our graph metaphor can have multiple outgoing edges but following any path ensures a valid sequence due to the problem's guarantees.
- The use of graph theory concepts like in-degree and adjacency list representation simplifies understanding the relationships between the pairs and aids in the efficient construction of the solution.
Solutions
- C++
- Java
- Python
class Solution {
public:
vector<vector<int>> arrangePairs(vector<vector<int>>& connections) {
unordered_map<int, deque<int>> graph;
unordered_map<int, int> degreeIn, degreeOut;
// Construct graph and maintain degrees
for (const auto& connection : connections) {
int from = connection[0], to = connection[1];
graph[from].push_back(to);
degreeOut[from]++;
degreeIn[to]++;
}
vector<int> traversal;
// Determine start node where out-degree exceeds in-degree by 1
int initialNode = -1;
for (const auto& entry : degreeOut) {
int current = entry.first;
if (degreeOut[current] == degreeIn[current] + 1) {
initialNode = current;
break;
}
}
// If no specific start node, begin at initial connection
if (initialNode == -1) {
initialNode = connections[0][0];
}
// Perform a Depth First Search
stack<int> traversalStack;
traversalStack.push(initialNode);
while (!traversalStack.empty()) {
int topNode = traversalStack.top();
if (!graph[topNode].empty()) {
int next = graph[topNode].front();
graph[topNode].pop_front();
traversalStack.push(next);
} else {
traversal.push_back(topNode);
traversalStack.pop();
}
}
// Reverse the traversal order for proper arrangement
reverse(traversal.begin(), traversal.end());
// Pair nodes according to the traversal
vector<vector<int>> finalPairs;
for (int i = 1; i < traversal.size(); ++i) {
finalPairs.push_back({traversal[i - 1], traversal[i]});
}
return finalPairs;
}
};
This solution is for a problem where you need to find a valid arrangement of pairs from a given list of paired connections, representing edges in a directed graph. This is implemented using C++.
In this approach:
It starts by creating a graph and tracking the in-degree and out-degree of each node using
unordered_map. The graph stores nodes and their connected nodes usingdequestructure for efficient front operations, which helps during the Depth First Search (DFS) traversal.It then determines the initial node to start the traversal. The choice of the starting node is based on the node whose out-degree exceeds its in-degree by one, which hints at a possible start of an Eulerian path. If no such node is found, the traversal starts from the node of the first connection in the given list.
A stack is used to perform DFS on the graph. The algorithm collects nodes in sequence by popping from the graph's adjacency list, pushing to the stack, and then moving to the next connected node. When no more nodes are connected to the current node, it begins backtracking, adding nodes to the result list.
After completing the DFS, the traversal order is reversed to align the direction from start to end in the correct sequence.
Finally, the nodes in the traversal list are paired sequentially in the manner they were visited during the DFS to form the final pairs, which are then returned.
This implementation efficiently organizes pairs by ensuring all nodes in the graph are visited and form a valid path or circuit, adhering to the specified conditions of paired connections and returning them as a vector of vector pairs.
class Solution {
public int[][] findValidArrangement(int[][] pairs) {
HashMap<Integer, LinkedList<Integer>> graph = new HashMap<>();
HashMap<Integer, Integer> degreeIncoming = new HashMap<>(), degreeOutgoing =
new HashMap<>();
// Create the graph and maintain degrees
for (int[] link : pairs) {
int source = link[0], destination = link[1];
graph.putIfAbsent(source, new LinkedList<>());
graph.get(source).add(destination);
degreeOutgoing.put(source, degreeOutgoing.getOrDefault(source, 0) + 1);
degreeIncoming.put(destination, degreeIncoming.getOrDefault(destination, 0) + 1);
}
ArrayList<Integer> path = new ArrayList<>();
// Determine starting vertex (where outgoing exceeds incoming by 1)
int startingVertex = -1;
for (int vertex : degreeOutgoing.keySet()) {
if (degreeOutgoing.get(vertex) == degreeIncoming.getOrDefault(vertex, 0) + 1) {
startingVertex = vertex;
break;
}
}
// If no explicit start vertex, use initial pair start
if (startingVertex == -1) {
startingVertex = pairs[0][0];
}
Stack<Integer> traversalStack = new Stack<>();
traversalStack.push(startingVertex);
// Depth-first traversal using a stack
while (!traversalStack.isEmpty()) {
int current = traversalStack.peek();
if (
graph.getOrDefault(current, new LinkedList<>()).size() >
0
) {
// Forward traversal
int next = graph.get(current).removeFirst();
traversalStack.push(next);
} else {
// Backtrack, current vertex completed
path.add(current);
traversalStack.pop();
}
}
// Reverse to get the correct path order
Collections.reverse(path);
// Generate final pairs array from path
int[][] resultArrangement = new int[path.size() - 1][2];
for (int i = 1; i < path.size(); ++i) {
resultArrangement[i - 1][0] = path.get(i - 1);
resultArrangement[i - 1][1] = path.get(i);
}
return resultArrangement;
}
}
The provided Java solution is constructed to find a valid arrangement of pairs that allow the formation of a directed path or cycle using all given pairs. Here's a breakdown of the approach taken:
Graph Representation: Utilize a
HashMapto represent the directed graph. Each key corresponds to a starting point of a pair, and the value is aLinkedListof destinations creating edges from the starting point.Counting Degrees: Use two separate
HashMapsfor tracking the count of incoming and outgoing degrees for each vertex. This helps in determining the flow of traversal from one vertex to another.Find Starting Vertex: Identify the starting vertex by comparing the outgoing and incoming degrees. The ideal starting vertex is one where the outgoing degree surpasses the incoming degree by exactly one. If such a vertex doesn't exist, default to the first vertex of the input pairs.
Depth-First Traversal: Implement a depth-first traversal using a
Stackto travel through the graph. Push the starting vertex onto the stack and then continuously do the following until the stack is empty: {- Check the current vertex's links. If there are outgoing edges, push the destination vertex onto the stack and remove the edge from the graph.
- If no outgoing edges remain, pop the vertex from the stack and add it to the result path. }
Construct the Result Path: Using the order of vertices obtained from the stack (reversed to correct the direction), pair consecutive vertices to form the required pairs that represent the resultant arrangement.
Reverse the Path Order: Since elements were added in the traversal completion order, reverse the collected path to reflect the true direction from start to finish.
The end result is constructed by iterating through the path of vertices, pairing each vertex with its successor to reassemble the pairs in the correct sequence, forming a valid arrangement that maintains the directions as specified in the original graph.
class Solution:
def findValidArrangement(self, pairs):
graph = collections.defaultdict(list)
in_degree, out_degree = collections.defaultdict(int), collections.defaultdict(int)
# Construct graph and track degrees of nodes
for start, end in pairs:
graph[start].append(end)
out_degree[start] += 1
in_degree[end] += 1
ordered_pairs = []
# Determine starting node
starting_node = -1
for node in out_degree:
if out_degree[node] == in_degree[node] + 1:
starting_node = node
break
# Start from an arbitrary node if specific start not found
if starting_node == -1:
starting_node = pairs[0][0]
stack = [starting_node]
# Use stack for DFS traversal
while stack:
current = stack[-1]
if graph[current]:
# Process next connected node
neighbor = graph[current].pop(0)
stack.append(neighbor)
else:
# Backtrack and record the path
ordered_pairs.append(current)
stack.pop()
# Reverse to correct order of path
ordered_pairs.reverse()
# Form the result in pairs
arranged_pairs = []
for i in range(1, len(ordered_pairs)):
arranged_pairs.append([ordered_pairs[i - 1], ordered_pairs[i]])
return arranged_pairs
The provided Python script is designed to arrange a list of pairs into a valid path based on specific conditions. The method findValidArrangement in the Solution class executes this task using concepts like graph traversal and depth-first search (DFS). Here is a breakdown of how the solution works:
- Define a graph and two dictionaries to keep track of the in-degrees and out-degrees of nodes.
- Populate the graph with directed connections from each pair and update the corresponding degrees.
- Identify a possible starting node. The node from which to begin the traversal is chosen based on the condition if its out-degree is higher by one than its in-degree.
- If a specific starting node isn't found, it defaults to the first element of the first pair.
- Initialize a stack with the starting node for DFS traversal.
- Process nodes using a while loop and the stack to explore the graph iteratively. Within this loop, if the current node has neighbors, move to the neighbor, otherwise, backtrack and record the path discovered.
- Once the stack is empty, reverse the recorded path to ensure the pairs are in the correct order.
- Lastly, form the resultant list of pairs from the ordered nodes.
This approach effectively arranges the pairs to follow one another where the end of one pair matches the start of the next, creating a continuous path, provided the input pairs allow for such an arrangement. Note that the solution assumes there exists at least one valid arrangement from the input.
No comments yet.