# 2647. Color the Triangle Red¶

• Time: $O(n^2)$
• Space: $O(n^2)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { public: vector> colorRed(int n) { vector> ans; const int tipSize = n % 4; // The tip of the triangle is always painted red. if (tipSize >= 1) ans.push_back({1, 1}); // Paint the rightmost and the leftmost elements at the following rows. for (int i = 2; i <= tipSize; ++i) { ans.push_back({i, 1}); ans.push_back({i, 2 * i - 1}); } // Paint the 4-row chunks. for (int i = tipSize + 1; i < n; i += 4) { // Fill the first row of the chunk. ans.push_back({i, 1}); // Fill the second row. for (int j = 1; j <= i; ++j) ans.push_back({i + 1, 2 * j + 1}); // Fill the third row. ans.push_back({i + 2, 2}); // Fill the fourth row. for (int j = 0; j <= i + 2; ++j) ans.push_back({i + 3, 2 * j + 1}); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public int[][] colorRed(int n) { List ans = new ArrayList<>(); final int tipSize = n % 4; // The tip of the triangle is always painted red. if (tipSize >= 1) ans.add(new int[] {1, 1}); // Paint the rightmost and the leftmost elements at the following rows. for (int i = 2; i <= tipSize; ++i) { ans.add(new int[] {i, 1}); ans.add(new int[] {i, 2 * i - 1}); } // Paint the 4-row chunks. for (int i = tipSize + 1; i < n; i += 4) { // Fill the first row of the chunk. ans.add(new int[] {i, 1}); // Fill the second row. for (int j = 1; j <= i; ++j) ans.add(new int[] {i + 1, 2 * j + 1}); // Fill the third row. ans.add(new int[] {i + 2, 2}); // Fill the fourth row. for (int j = 0; j <= i + 2; ++j) ans.add(new int[] {i + 3, 2 * j + 1}); } return ans.stream().toArray(int[][] ::new); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution: def colorRed(self, n: int) -> List[List[int]]: ans = [] tipSize = n % 4 # The tip of the triangle is always painted red. if tipSize >= 1: ans.append([1, 1]) # Pamost right and most left elements at the following rows. for i in range(2, tipSize + 1): ans.append([i, 1]) ans.append([i, 2 * i - 1]) # Pa4-row chunks. for i in range(tipSize + 1, n, 4): # Fill the first row of the chunk. ans.append([i, 1]) # Fill the second row. for j in range(1, i + 1): ans.append([i + 1, 2 * j + 1]) # Fill the third row. ans.append([i + 2, 2]) # Fill the fourth row. for j in range(i + 2 + 1): ans.append([i + 3, 2 * j + 1]) return ans