Problem

You are given an integer n. Consider an equilateral triangle of side length n, broken up into n2 unit equilateral triangles. The triangle has n 1-indexed rows where the ith row has 2i - 1 unit equilateral triangles.

The triangles in the ith row are also 1-indexed with coordinates from (i, 1) to (i, 2i - 1). The following image shows a triangle of side length 4 with the indexing of its triangle.

Two triangles are neighbors if they share a side. For example:

  • Triangles (1,1) and (2,2) are neighbors
  • Triangles (3,2) and (3,3) are neighbors.
  • Triangles (2,2) and (3,3) are not neighbors because they do not share any side.

Initially, all the unit triangles are white. You want to choose k triangles and color them red. We will then run the following algorithm:

  1. Choose a white triangle that has at least two red neighbors.
    • If there is no such triangle, stop the algorithm.
  2. Color that triangle red.
  3. Go to step 1.

Choose the minimum k possible and set k triangles red before running this algorithm such that after the algorithm stops, all unit triangles are colored red.

Return a 2D list of the coordinates of the triangles that you will color red initially. The answer has to be of the smallest size possible. If there are multiple valid solutions, return any.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2600-2699/2647.Color%20the%20Triangle%20Red/images/example1.jpg)
Input: n = 3
Output: [[1,1],[2,1],[2,3],[3,1],[3,5]]
Explanation: Initially, we choose the shown 5 triangles to be red. Then, we run the algorithm:
- Choose (2,2) that has three red neighbors and color it red.
- Choose (3,2) that has two red neighbors and color it red.
- Choose (3,4) that has three red neighbors and color it red.
- Choose (3,3) that has three red neighbors and color it red.
It can be shown that choosing any 4 triangles and running the algorithm will not make all triangles red.

Example 2:

1
2
3
4
5
6

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/2600-2699/2647.Color%20the%20Triangle%20Red/images/example2.jpg)
Input: n = 2
Output: [[1,1],[2,1],[2,3]]
Explanation: Initially, we choose the shown 3 triangles to be red. Then, we run the algorithm:
- Choose (2,2) that has three red neighbors and color it red.
It can be shown that choosing any 2 triangles and running the algorithm will not make all triangles red.

Constraints:

  • 1 <= n <= 1000

Solution

Method 1 – Greedy (Boundary Coloring)

Intuition

To ensure all triangles become red, we must initially color all boundary triangles (the outermost ones) red. This is because only boundary triangles can be left with fewer than two red neighbors if not colored at the start. Once the boundary is red, the propagation rule will fill the rest.

Approach

  1. For each row from 1 to n:
    • Color the first and last triangle in the row red (i.e., (i,1) and (i,2i-1)).
  2. This covers all boundary triangles.
  3. Return the list of these coordinates.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    vector<vector<int>> colorRed(int n) {
        vector<vector<int>> ans;
        for (int i = 1; i <= n; ++i) {
            ans.push_back({i, 1});
            if (2 * i - 1 != 1) ans.push_back({i, 2 * i - 1});
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func colorRed(n int) [][]int {
    ans := [][]int{}
    for i := 1; i <= n; i++ {
        ans = append(ans, []int{i, 1})
        if 2*i-1 != 1 {
            ans = append(ans, []int{i, 2*i-1})
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public List<List<Integer>> colorRed(int n) {
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            ans.add(Arrays.asList(i, 1));
            if (2 * i - 1 != 1) ans.add(Arrays.asList(i, 2 * i - 1));
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun colorRed(n: Int): List<List<Int>> {
        val ans = mutableListOf<List<Int>>() 
        for (i in 1..n) {
            ans.add(listOf(i, 1))
            if (2 * i - 1 != 1) ans.add(listOf(i, 2 * i - 1))
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def colorRed(self, n: int) -> list[list[int]]:
        ans = []
        for i in range(1, n + 1):
            ans.append([i, 1])
            if 2 * i - 1 != 1:
                ans.append([i, 2 * i - 1])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn color_red(n: i32) -> Vec<Vec<i32>> {
        let mut ans = vec![];
        for i in 1..=n {
            ans.push(vec![i, 1]);
            if 2 * i - 1 != 1 {
                ans.push(vec![i, 2 * i - 1]);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    colorRed(n: number): number[][] {
        const ans: number[][] = [];
        for (let i = 1; i <= n; i++) {
            ans.push([i, 1]);
            if (2 * i - 1 !== 1) ans.push([i, 2 * i - 1]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)