LeetCode 2078: Two Furthest Houses With Different Colors | Java Solution Explained (Step-by-Step Guide)

Why This Problem Is InterestingAt first glance, this looks like a basic array problem. But here’s the twist:👉 If you try solving it “normally,” you’ll overthink it. 👉 If you observe patterns, it becomes one of the easiest O(n) problems.This is exactly the kind of question interviewers use to test:Do you brute force blindly?Or do you see patterns in constraints?🚀 Problem Linkhttps://leetcode.com/problems/two-furthest-houses-with-different-colors/🧩 Problem Breakdown (Understand Like a Beginner)You are given:colors = [1,1,1,6,1,1,1]Each index = house Each value = colorYou need to:👉 Pick two houses with different colors 👉 Maximize the distance between themDistance formula:|i - j|🧠 First Thought (What Most People Do)“Let me check all pairs…”(0,1), (0,2), (0,3), ...(1,2), (1,3), ...Yes, it works. But…👉 That’s O(n²) 👉 Completely unnecessary for n ≤ 100? Maybe fine 👉 But logically inefficient🟡 Approach 1: Brute Force (Baseline Thinking)💻 Codeclass Solution { public int maxDistance(int[] colors) { int n = colors.length; int max = 0; for (int i = 0; i < n; i++) { for (int j = n - 1; j > i; j--) { if (colors[i] != colors[j]) { max = Math.max(max, j - i); } } } return max; }}⏱ Time Complexity (Why O(n²)?)Outer loop → runs n timesInner loop → runs n times👉 Total = n * n = O(n²)❌ Why This Is WastefulYou are:Checking close houses (useless)When the answer depends on far houses💡 Key Turning Point (Where Real Thinking Starts)Ask yourself:👉 “To maximize |i - j|, what do I need?”Answer:👉 Make i and j as far apart as possibleThat means:i should be near 0j should be near n-1🔥 Critical Observation👉 The answer will always involve either:First house (index 0), ORLast house (index n-1)Why?Because they give maximum possible distance🟢 Approach 2: Two Direction ScanNow your idea makes perfect sense:Step 1Fix first element → find farthest different colorStep 2Fix last element → find farthest different color💻 Your Codeclass Solution { public int maxDistance(int[] colors) { int i = 0; int i2 = colors.length - 1; int j1 = 1; int j2 = colors.length - 2; int max1 = Integer.MIN_VALUE; int max2 = Integer.MIN_VALUE; while (j1 < colors.length) { if (colors[i] != colors[j1]) { max1 = Math.max(max1, Math.abs(j1 - i)); } j1++; } while (j2 >= 0) { if (colors[i2] != colors[j2]) { max2 = Math.max(max2, Math.abs(j2 - i2)); } j2--; } return Math.max(max1, max2); }}🔍 Dry Run (Deep Understanding)Input:colors = [1,1,1,6,1,1,1]🔹 First Loop (Fix index 0)Compare:0 vs 1 → same0 vs 2 → same0 vs 3 → different ✅ → distance = 30 vs 4 → same0 vs 5 → same0 vs 6 → same👉 max1 = 3🔹 Second Loop (Fix last index)Compare:6 vs 5 → same6 vs 4 → same6 vs 3 → different ✅ → distance = 36 vs 2 → same...👉 max2 = 3✅ Final Answer:max(3, 3) = 3⏱ Time Complexity (Why O(n)?)First loop → O(n)Second loop → O(n)👉 Total = O(n) + O(n) = O(n)🟢 Approach 3: Cleaner Optimization (Best Version)We can compress both loops into one:💻 Codeclass Solution { public int maxDistance(int[] colors) { int n = colors.length; int max = 0; for (int i = 0; i < n; i++) { if (colors[i] != colors[0]) { max = Math.max(max, i); } if (colors[i] != colors[n - 1]) { max = Math.max(max, n - 1 - i); } } return max; }}🔍 Why This Works (Core Insight)We only check:Distance from startDistance from endBecause:👉 Any maximum distance pair must include one endpointThis avoids:Redundant comparisonsNested loops🧠 Mental Model (Remember This)Instead of thinking:❌ “Check all pairs”Think:✅ “Where can maximum distance even exist?”🎯 Final TakeawaysAlways question brute forceDistance problems → think endpoints firstConstraints often hide optimizationsObservations > Code