Two Furthest Houses With Different Colors

Two Furthest Houses With Different Colors - Problem

Array Greedy Easy

There are n houses evenly lined up on the street, and each house is beautifully painted. You are given a 0-indexed integer array colors of length n, where colors[i] represents the color of the i^th house.

Return the maximum distance between two houses with different colors.

The distance between the i^th and j^th houses is abs(i - j), where abs(x) is the absolute value of x.

Input & Output

Example 1 — Basic Case

$ Input: colors = [1,1,1,6,1,1,1]

› Output: 3

💡 Note: The house at index 3 has color 6, which differs from houses at indices 0 and 6 (both color 1). Distance from index 0 to 3 is |0-3| = 3, and from index 6 to 3 is |6-3| = 3. Maximum distance is 3.

Example 2 — Different Colors at Ends

$ Input: colors = [1,8,3,8,3]

› Output: 4

💡 Note: House at index 0 (color 1) and house at index 4 (color 3) have different colors. The distance is |0-4| = 4, which is the maximum possible.

Example 3 — Minimum Length

$ Input: colors = [0,1]

› Output: 1

💡 Note: Only two houses with different colors (0 and 1). Distance between indices 0 and 1 is |0-1| = 1.

Constraints

2 ≤ colors.length ≤ 100
0 ≤ colors[i] ≤ 100
Test cases are generated such that at least two houses have different colors.

Visualization

Tap to expand

Understanding the Visualization

Input

Array of house colors with indices

Process

Find pairs with different colors and calculate distances

Output

Maximum distance between any two different colored houses

Key Takeaway

🎯 Key Insight: Maximum distance is most likely between houses at opposite ends of the street

Asked in

G Google 15 M Microsoft 12

Brief HTML summary: The key insight is that maximum distance between different colored houses is likely to involve houses near the opposite ends of the street. Best approach is greedy optimization which checks from both extremes. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	Check all pairs of houses to find maximum distance with different colors
Greedy Optimization	O(n)	O(1)	Check distances from first and last house to find maximum efficiently

Brute Force — Algorithm Steps

Step 1: Use nested loops to check all pairs of houses
Step 2: For each pair with different colors, calculate distance abs(i - j)
Step 3: Keep track of maximum distance found

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Pairs

Compare each house with all houses after it

Find Different Colors

Calculate distance when colors differ

Track Maximum

Keep the largest distance found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* colors, int n) {
    int maxDistance = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (colors[i] != colors[j]) {
                int distance = j - i; // j > i so no need for abs
                if (distance > maxDistance) {
                    maxDistance = distance;
                }
            }
        }
    }
    
    return maxDistance;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple JSON array parsing
    int colors[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]"); // Skip '['
    while (token != NULL) {
        colors[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(colors, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops check all pairs of houses (n × n comparisons)

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses a few variables to track maximum distance

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler