Leetcode 1042: Flower Planting With No Adjacent
You are given n gardens labeled from 1 to n, and an array paths where paths[i] = [xi, yi] describes a bidirectional path between garden xi and garden yi. Each garden needs to be assigned one of 4 types of flowers. You need to ensure that for any two gardens connected by a path, they have different types of flowers. Your task is to return any valid flower assignment for all gardens such that no two adjacent gardens share the same flower type.
Problem
Approach
Steps
Complexity
Input: You are given an integer n, the number of gardens, and a list of pairs paths, where each pair [xi, yi] represents a bidirectional path between garden xi and garden yi.
Example: Input: n = 5, paths = [[1,2], [2,3], [3,4], [4,5]]
Constraints:
• 1 <= n <= 10^4
• 0 <= paths.length <= 2 * 10^4
• paths[i].length == 2
• 1 <= xi, yi <= n
• xi != yi
• Each garden has at most 3 paths coming into or leaving it.
Output: Return an array where the i-th element represents the type of flower planted in the i-th garden. The flower types are denoted by integers 1, 2, 3, or 4.
Example: Output: [1, 2, 3, 4, 1]
Constraints:
• There is guaranteed to be at least one valid answer.
Goal: The goal is to assign flower types to gardens such that no two connected gardens have the same flower type.
Steps:
• 1. Represent the gardens and paths as a graph.
• 2. Use a greedy approach to assign flower types to gardens, making sure adjacent gardens get different flower types.
Goal: The problem has the following constraints:
Steps:
• 1 <= n <= 10^4
• 0 <= paths.length <= 2 * 10^4
• 1 <= xi, yi <= n
• xi != yi
• Every garden has at most 3 paths coming into or leaving it.
Assumptions:
• It is guaranteed that there is always a valid solution.
• Input: Input: n = 5, paths = [[1,2], [2,3], [3,4], [4,5]]
• Explanation: In this case, we can assign flowers such that adjacent gardens have different types. One valid solution is to assign flowers [1, 2, 1, 2, 1] to gardens [1, 2, 3, 4, 5].
• Input: Input: n = 6, paths = [[1,2], [1,3], [2,4], [3,5], [4,6]]
• Explanation: Here, we can assign flowers such that adjacent gardens do not share the same flower type. One valid solution is [1, 2, 3, 4, 3, 2].
Approach: The approach is based on graph coloring, where each garden is a node, and paths between gardens are edges. The goal is to color the nodes (gardens) with 4 colors (flower types) such that no two connected nodes share the same color.
Observations:
• The problem can be viewed as a graph coloring problem, where adjacent gardens must be assigned different flowers.
• Since each garden has at most 3 paths, we can use a greedy approach to assign flower types.
• A greedy algorithm should suffice for this problem, where we try to assign the lowest available flower type that hasn’t been used by adjacent gardens.
Steps:
• 1. Construct a graph where each garden is a node and each path is an edge.
• 2. Initialize an array to store flower types for each garden, initially set to 0.
• 3. For each garden, check the flower types of its neighbors and assign the lowest available flower type.
Empty Inputs:
• The problem guarantees at least one valid path, so no need to handle empty inputs.
Large Inputs:
• The algorithm must efficiently handle large inputs, with up to 10^4 gardens and 2 * 10^4 paths.
Special Values:
• The constraints ensure there is always a valid solution, so no need to handle cases with no solution.
Constraints:
• The number of paths per garden will not exceed 3, so the graph is sparse.
vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
vector<int> res(n, 0);
vector<vector<int>> gph(n);
for(vector<int> &p: paths) {
gph[p[0]-1].push_back(p[1]-1);
gph[p[1]-1].push_back(p[0]-1);
}
for(int i = 0; i < n; i++) {
int colors[5] = {};
for(int j: gph[i]) {
colors[res[j]] = 1;
}
for(int c = 4; c > 0; c--)
if(!colors[c])
res[i] = c;
}
return res;
}
1 : Function Definition
vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
Define the function 'gardenNoAdj' that solves the problem of coloring the gardens such that no two adjacent gardens share the same color.
2 : Variable Initialization
vector<int> res(n, 0);
Initialize the result vector 'res' with size 'n' and set all garden colors to 0, indicating that no garden is colored yet.
3 : Graph Initialization
vector<vector<int>> gph(n);
Create an adjacency list 'gph' to represent the graph of gardens, where each garden's neighbors (adjacent gardens) will be stored.
4 : Graph Construction
for(vector<int> &p: paths) {
Iterate through the paths provided, where each path connects two gardens.
5 : Graph Construction
gph[p[0]-1].push_back(p[1]-1);
For each path, add an edge between the two gardens in the adjacency list. Since gardens are 1-indexed, subtract 1 to match the 0-indexed array.
6 : Graph Construction
gph[p[1]-1].push_back(p[0]-1);
Similarly, add the reverse edge to ensure the graph is undirected (both gardens are adjacent to each other).
7 : Outer Loop
for(int i = 0; i < n; i++) {
Start a loop to iterate through each garden and assign a color to it.
8 : Color Initialization
int colors[5] = {};
Initialize an array 'colors' to keep track of which colors are already used by adjacent gardens. The array size is 5 because there are 4 colors (indexed 1 to 4) and a 0 to indicate unused colors.
9 : Adjacent Gardens Loop
for(int j: gph[i]) {
For each garden 'i', loop through its adjacent gardens to find out which colors are already taken.
10 : Mark Colors Used
colors[res[j]] = 1;
Mark the color of each adjacent garden as used in the 'colors' array.
11 : Color Assignment Loop
for(int c = 4; c > 0; c--)
Loop through the available colors (from 4 down to 1) and assign the first available color to the current garden.
12 : Check Available Color
if(!colors[c])
If the current color is not used by any adjacent garden (i.e., 'colors[c]' is 0), assign this color to the garden.
13 : Assign Color
res[i] = c;
Assign the color 'c' to the garden 'i'.
14 : Return Statement
return res;
Return the 'res' vector, which contains the colors assigned to each garden.
Best Case: O(n + m)
Average Case: O(n + m)
Worst Case: O(n + m)
Description: The time complexity is O(n + m), where n is the number of gardens and m is the number of paths.
Best Case: O(n + m)
Worst Case: O(n + m)
Description: The space complexity is O(n + m), where n is the number of gardens and m is the number of paths, for storing the graph and flower assignments.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus