Color the Triangle Red - Problem

You are given an integer n. Consider an equilateral triangle of side length n, broken up into n² unit equilateral triangles.

The triangle has n 1-indexed rows where the i-th row has 2i - 1 unit equilateral triangles. The triangles in the i-th row are also 1-indexed with coordinates from (i, 1) to (i, 2i - 1).

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 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
  2. If there is no such triangle, stop the algorithm
  3. Color that triangle red
  4. 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.

Input & Output

Example 1 — Small Triangle (n=2)
$ Input: n = 2
› Output: [[1,1],[2,2]]
💡 Note: For n=2, we have triangles (1,1), (2,1), (2,2), (2,3). Starting with (1,1) and (2,2) red, the algorithm can color (2,1) and (2,3) since they each have 2 red neighbors.
Example 2 — Medium Triangle (n=3)
$ Input: n = 3
› Output: [[1,1],[3,1],[3,5]]
💡 Note: For n=3, we place red triangles at the top corner and two bottom corners. This strategic placement allows the spreading algorithm to color all remaining triangles through the neighbor rule.
Example 3 — Single Triangle (n=1)
$ Input: n = 1
› Output: [[1,1]]
💡 Note: For n=1, there's only one triangle (1,1), so we must color it initially. No spreading is needed.

Constraints

  • 1 ≤ n ≤ 1000
  • Triangle has n² unit triangles total
  • Row i has 2i - 1 triangles

Visualization

Tap to expand
Triangle Coloring Problem: Strategic Red PlacementInput: Triangle Grid(1,1)(2,1)(2,2)(2,3)n=2 triangleInitial Placement(1,1)(2,2)Red: Initial positionsAfter SpreadingGreen: All coloredRule: White triangle colors red if it has 2+ red neighborsGoal: Find minimum initial positions for complete coverage🎯 Key Insight: Strategic placement enables viral spreading pattern
Understanding the Visualization
1
Input
Triangle of side length n with coordinate system
2
Process
Place initial red triangles, then spread using 2-neighbor rule
3
Output
Minimum set of initial positions for full coverage
Key Takeaway
🎯 Key Insight: Corner positions are crucial because they have the fewest neighbors and need careful placement to ensure connectivity.

Related Problems

Asked in
Google 25 Facebook 18 Microsoft 15
12.5K Views
Medium Frequency
~45 min Avg. Time
340 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen