Number of Ways to Paint N×3 Grid | LeetCode 1411 | Recurrence Explained

In this video, we solve LeetCode 1411 — Number of Ways to Paint N × 3 Grid using a dynamic programming recurrence.

Code:
https://leetcode.com/problems/number-...

Upsolve Leetcode Contest:
   • Leetcode Contests  

Greedy & Heaps:
   • Greedy & Heaps  

Two pointers:
   • Two pointers  

Sliding Window:
   • Sliding Window  

Maths & Geometry:
   • Maths & Geometry  

Stack:
   • Stack  

Set & Map:
   • Set & Map  

Bit manipulation:
   • Bit Manipulation  

Backtracking:
   • Backtracking  

Linked List:
   • Linked List  

Binary Search:
   • Binary Search  

Graph:
   • Graph  

Dynamic Progamming:
   • Dynamic Programming  

You are given an integer n representing the number of rows of a grid with 3 columns. Each cell must be painted with one of three colors such that:

No two adjacent cells horizontally or vertically have the same color.

You need to return the total number of valid colorings modulo 10⁹ + 7.

🔗 Problem Link:
https://leetcode.com/problems/number-...

✅ Approach

We classify each row into two types:
Type A (2-color pattern): patterns like ABA
Type B (3-color pattern): patterns like ABC

We maintain:

two = number of ways to paint rows ending with 2-color pattern
three = number of ways to paint rows ending with 3-color pattern
Transition:

⏱️ Complexity
Time: O(n)
Space: O(1)

#leetcode #leetcode1411 #numberofwaystopaintgrid #dynamicprogramming #dp #gridproblems #combinatorics #recurrence #mathdp #javacode #java #coding #programming #datastructures #algorithms #dsa #competitiveprogramming #codinginterview #faang #maang #placementprep #dailycodingchallenge #studyplacement #techcommunity #codeeveryday #learncoding #problem-solving