LeetCode Challenge: Stable Binary Arrays II

📌 LeetCode Daily Challenge — Day 10 Remember yesterday's problem? Here's the plot twist 🔄 Yesterday I solved: 3145. Stable Binary Arrays I — Medium Today I'm solving: 3146. Stable Binary Arrays II — Hard Same problem. Same logic. Same code. But the constraints jumped from 200 to 1000 and that one change decides whether your solution passes or fails! Topic: Dynamic Programming, Prefix Sum 📌 What Changed: Problem 1 → zero, one ≤ 200 → DP table = 40K states Problem 2 → zero, one ≤ 1000 → DP table = 1M states If your solution has any hidden inner loop, Problem 2 catches it immediately with TLE 💥 🧠 Why The Same Code Still Works: 🔹 The solution I wrote yesterday already used the subtraction trick 🔹 Instead of looping over run lengths (O(limit) per state), I subtract the boundary case (O(1) per state) 🔹 dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1] - dp[i-limit-1][j][1] 🔹 That one subtraction collapses the entire run length dimension 🔹 Total complexity → O(zero × one), scales perfectly even when constraints jump 5x 🏃 Quick Recap: Input: zero = 1, one = 1, limit = 2 Valid arrays with one 0 and one 1: "01" ✅ "10" ✅ return 2 ✅ Same input, same output but Problem 2 would reject any O(n²×limit) approach instantly. ⏱️ Time Complexity: O(zero × one) Every state computed in O(1) no inner loops 📦 Space Complexity: O(zero × one) 3D DP with last digit dimension = 2 💭 Here's the lesson: LeetCode often pairs a Medium and Hard version of the same problem. Medium lets you verify your logic even with a slightly naive approach. Hard cranks the constraints and forces you to write the truly optimized version. If you solve Medium with the optimal approach from day one, the Hard version is just copy-paste ✅ That's why thinking about optimization early always pays off! Same article from yesterday applies here the code hasn't changed one bit: https://lnkd.in/gMRVXyKx Have you ever had a solution that scaled perfectly from Medium to Hard? Drop it in the comments 👇 See you in the next problem 👋 #java #SoftwareEngineer #CodingInterview #DynamicProgramming #BackendDeveloper

  • graphical user interface, text, application, email

To view or add a comment, sign in

Explore content categories