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

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

Understand the problem deeply with examples, then master an optimal O(n) solution using a simple observation.

14 views
0
0
Github icon
Github icon
Listen to articleAudio version

Why This Problem Is Interesting

At 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:

  1. Do you brute force blindly?
  2. Or do you see patterns in constraints?

🚀 Problem Link

https://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 = color

You need to:

👉 Pick two houses with different colors

👉 Maximize the distance between them

Distance 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)

💻 Code


class 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²)?)

  1. Outer loop → runs n times
  2. Inner loop → runs n times

👉 Total = n * n = O(n²)

❌ Why This Is Wasteful

You are:

  1. Checking close houses (useless)
  2. 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 possible

That means:

  1. i should be near 0
  2. j should be near n-1

🔥 Critical Observation

👉 The answer will always involve either:

  1. First house (index 0), OR
  2. Last house (index n-1)

Why?

Because they give maximum possible distance

🟢 Approach 2: Two Direction Scan

Now your idea makes perfect sense:

Step 1

Fix first element → find farthest different color

Step 2

Fix last element → find farthest different color

💻 Your Code


class 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 → same
0 vs 2 → same
0 vs 3 → different ✅ → distance = 3
0 vs 4 → same
0 vs 5 → same
0 vs 6 → same

👉 max1 = 3

🔹 Second Loop (Fix last index)

Compare:

6 vs 5 → same
6 vs 4 → same
6 vs 3 → different ✅ → distance = 3
6 vs 2 → same
...

👉 max2 = 3

✅ Final Answer:

max(3, 3) = 3

⏱ Time Complexity (Why O(n)?)

  1. First loop → O(n)
  2. Second loop → O(n)

👉 Total = O(n) + O(n) = O(n)

🟢 Approach 3: Cleaner Optimization (Best Version)

We can compress both loops into one:

💻 Code


class 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:

  1. Distance from start
  2. Distance from end

Because:

👉 Any maximum distance pair must include one endpoint

This avoids:

  1. Redundant comparisons
  2. Nested loops

🧠 Mental Model (Remember This)

Instead of thinking:

❌ “Check all pairs”

Think:

✅ “Where can maximum distance even exist?”

🎯 Final Takeaways

  1. Always question brute force
  2. Distance problems → think endpoints first
  3. Constraints often hide optimizations
  4. Observations > Code


Related Articles

Maximum Product Subarray

Maximum Product Subarray

LeetCode Question 152 Medium

Read Article
LeetCode 1855 Maximum Distance Between Pair of Values | Two Pointer Java Solution

LeetCode 1855 Maximum Distance Between Pair of Values | Two Pointer Java Solution

Learn how to solve LeetCode 1855 using the two-pointer technique. Includes intuition, dry run, optimized Java code, and alternative approaches.

Read Article
Maximum Absolute Sum of Any Subarray

Maximum Absolute Sum of Any Subarray

LeetCode Question 1749 Medium

Read Article
Maximum Subarray

Maximum Subarray

LeetCode Question 53 Medium

Read Article
Ai Assistant Kas