LeetCode 2647 - Color the Triangle Red

The problem asks us to determine the minimal set of initial triangles to color red in an equilateral triangle of side length n, such that by repeatedly applying a propagation rule, all triangles eventually become red.

leetcodehardarraymath

LeetCode Problem 2647

Difficulty: 🔴 Hard
Topics: Array, Math

Solution

Problem Understanding

The problem asks us to determine the minimal set of initial triangles to color red in an equilateral triangle of side length n, such that by repeatedly applying a propagation rule, all triangles eventually become red. The propagation rule is simple: any white triangle with at least two red neighbors becomes red automatically.

The input n specifies the size of the triangle, with n rows. Each row i has 2i - 1 triangles indexed from 1 to 2i - 1. The output should be a 2D list of coordinates representing the initially red triangles, chosen such that the number of initially red triangles k is minimal.

Key points:

  • Triangles have neighbors if they share a side. Edge and corner triangles have fewer neighbors.
  • The minimal set of red triangles is needed to trigger a chain reaction that eventually colors all triangles.
  • Constraints: 1 <= n <= 1000, meaning the algorithm must scale efficiently to around 1,000,000 unit triangles. Brute-force simulation is not feasible.

Important edge cases include n = 1 (single triangle), n = 2 (small triangle with propagation easily traceable), and n very large (to test efficiency). The problem guarantees that a solution exists for any n >= 1.

Approaches

Brute Force Approach

A brute-force solution would attempt to try all possible combinations of initially red triangles and simulate the propagation. This involves checking for every subset of triangles whether coloring them initially leads to full propagation. This is correct in principle but computationally infeasible: with O(n^2) triangles, the number of subsets is exponential (2^(n^2)), which is impossible for n = 1000.

Key Insight and Optimal Approach

The key insight is that there is a pattern in how red spreads. By observing smaller examples, we can see that the minimal initial red triangles are positioned along all edges with a step of 2. Essentially, coloring the boundary triangles in a checkerboard pattern ensures that every inner triangle will eventually have at least two red neighbors and become red.

The optimal approach is a pattern-based selection:

  1. Color the first triangle (1,1) and then every second triangle along each row starting from the left.
  2. This covers all positions required to propagate red to every triangle in the triangle grid.
  3. This pattern guarantees the minimal number of initial red triangles.

The key is recognizing the propagation pattern rather than simulating every step.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(n^2)) O(n^2) Check all subsets, simulate propagation
Optimal O(n^2) O(n^2) Pattern-based initial red triangles using row stepping

Algorithm Walkthrough

  1. Initialize an empty list res to hold coordinates of initially red triangles.
  2. Iterate through each row i from 1 to n.
  3. Within each row, iterate through columns j from 1 to 2i - 1, selecting every second triangle starting with the first triangle in odd rows. This ensures coverage for propagation.
  4. Append each selected triangle (i, j) to res.
  5. Return res as the final list of initially red triangles.

Why it works: Coloring every other triangle along rows ensures that every white triangle inside the triangle eventually has at least two red neighbors, fulfilling the propagation rule. This guarantees that all triangles become red while minimizing the number of initial red triangles.

Python Solution

from typing import List

class Solution:
    def colorRed(self, n: int) -> List[List[int]]:
        res = []
        for i in range(1, n + 1):
            # Choose triangles in odd positions in the row for propagation
            for j in range(1, 2 * i, 2):
                res.append([i, j])
        return res

Explanation: We iterate over each row i. For each row, we choose columns j in steps of 2 starting from 1. This captures the "checkerboard" pattern needed for minimal initial red triangles to guarantee full propagation.

Go Solution

func colorRed(n int) [][]int {
    res := [][]int{}
    for i := 1; i <= n; i++ {
        for j := 1; j < 2*i; j += 2 {
            res = append(res, []int{i, j})
        }
    }
    return res
}

Explanation: Go version mirrors Python logic. We use slices for dynamic arrays. append is used to collect the initial red triangles. Step of 2 ensures the same pattern. Empty slice initialization is equivalent to Python list.

Worked Examples

Example 1: n = 3

Initial red triangles according to the algorithm: [[1,1], [2,1], [2,3], [3,1], [3,3], [3,5]].

Step by step propagation:

Step Newly Red Triangles Explanation
Initial [[1,1],[2,1],[2,3],[3,1],[3,3],[3,5]] Pattern-based selection
1 (2,2) 2 red neighbors: (2,1),(1,1)
2 (3,2) 2 red neighbors: (3,1),(2,2)
3 (3,4) 2 red neighbors: (3,3),(2,3)
4 (3,3) Already red from initial, propagation continues
All all triangles red Algorithm stops

Example 2: n = 2

Initial red triangles: [[1,1],[2,1],[2,3]].

Propagation:

Step Newly Red Triangles Explanation
Initial [[1,1],[2,1],[2,3]] Pattern-based selection
1 (2,2) 2 red neighbors: (2,1),(1,1)
All all triangles red Algorithm stops

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) We iterate over each row and each triangle in the row once.
Space O(n^2) Output list contains roughly half of the total triangles (n^2/2).

Reasoning: Each row has 2i - 1 triangles, sum over i = 1 to n gives n^2. Selecting every other triangle reduces count but asymptotic complexity remains O(n^2). Storage scales with number of selected triangles.

Test Cases

sol = Solution()

# Example tests
assert sol.colorRed(3) == [[1,1],[2,1],[2,3],[3,1],[3,3],[3,5]]  # Example 1
assert sol.colorRed(2) == [[1,1],[2,1],[2,3]]                     # Example 2

# Edge tests
assert sol.colorRed(1) == [[1,1]]  # Single triangle
assert sol.colorRed(4) == [[1,1],[2,1],[2,3],[3,1],[3,3],[3,5],[4,1],[4,3],[4,5],[4,7]]  # Larger triangle

# Stress test
result = sol.colorRed(1000)
assert len(result) == 500500  # Half of total triangles
Test Why
n=1 Minimal case, single triangle
n=2 Small triangle, easy to manually verify
n=3 Checks correct propagation pattern
n=4 Larger triangle, verifies pattern scaling
n=1000 Stress test for performance and correctness

Edge Cases

Edge Case 1: n = 1

The triangle has only one unit. The algorithm correctly returns [[1,1]]. There is no propagation needed, but the minimal initial red set is exactly one triangle.

Edge Case 2: Even vs Odd Row Lengths

Rows with an even number of triangles still work correctly because we select every other triangle starting from the first. This ensures inner triangles eventually have two red neighbors. No extra logic is required for even-length rows.

Edge Case 3: Large n (n=1000)

Performance is critical. The algorithm iterates over rows and columns in a deterministic pattern and does not simulate propagation. Memory usage scales with half of n^2, which is acceptable given constraints. This avoids any stack overflow or TLE.

This approach handles all edge cases while guaranteeing minimal initial red triangles and correct full propagation.