Two Furthest Houses With Different Colors

EASY

Description

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.

Example 1:

Input: colors = [1,1,1,6,1,1,1]
Output: 3
Explanation: In the above image, color 1 is blue, and color 6 is red.
The furthest two houses with different colors are house 0 and house 3.
House 0 has color 1, and house 3 has color 6. The distance between them is abs(0 - 3) = 3.
Note that houses 3 and 6 can also produce the optimal answer.

Example 2:

Input: colors = [1,8,3,8,3]
Output: 4
Explanation: In the above image, color 1 is blue, color 8 is yellow, and color 3 is green.
The furthest two houses with different colors are house 0 and house 4.
House 0 has color 1, and house 4 has color 3. The distance between them is abs(0 - 4) = 4.

Example 3:

Input: colors = [0,1]
Output: 1
Explanation: The furthest two houses with different colors are house 0 and house 1.
House 0 has color 0, and house 1 has color 1. The distance between them is abs(0 - 1) = 1.

Constraints:

n == colors.length
2 <= n <= 100
0 <= colors[i] <= 100
Test data are generated such that at least two houses have different colors.

Approaches

Checkout 2 different approaches to solve Two Furthest Houses With Different Colors. Click on different approaches to view the approach and algorithm in detail.

Brute Force

The most straightforward approach is to check every possible pair of houses. We can use nested loops to iterate through all combinations of two distinct houses, i and j, and calculate the distance between them if their colors are different. We keep track of the maximum distance found.

Algorithm

Initialize a variable maxDistance to 0.
Use a nested loop. The outer loop iterates through each house i from 0 to n-1.
The inner loop iterates through each subsequent house j from i + 1 to n-1.
Inside the inner loop, check if colors[i] is different from colors[j].
If they are different, calculate the distance j - i.
Update maxDistance to be the maximum of its current value and the newly calculated distance.
After iterating through all pairs, return maxDistance.

This method systematically explores all potential pairs of houses to find the one with the maximum distance and different colors.

We initialize a variable, maxDistance, to store the maximum distance, starting at 0.
The outer loop selects the first house, i, starting from index 0 up to n-1.
The inner loop selects the second house, j, starting from i+1 to n-1. This ensures that each pair (i, j) is considered only once and j > i, so the distance is simply j - i.
For each pair, we compare their colors, colors[i] and colors[j].
If the colors are not the same, we update maxDistance with Math.max(maxDistance, j - i).
After the loops complete, maxDistance will hold the largest distance found between any two houses of different colors.

class Solution {
    public int maxDistance(int[] colors) {
        int n = colors.length;
        int maxDistance = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (colors[i] != colors[j]) {
                    maxDistance = Math.max(maxDistance, j - i);
                }
            }
        }
        return maxDistance;
    }
}

Complexity Analysis

Time Complexity: O(n^2), where `n` is the number of houses. The nested loops lead to a number of comparisons proportional to n * n.Space Complexity: O(1), as it only uses a few variables to store the indices and the maximum distance, requiring constant extra space.

Pros and Cons

Pros:

Simple to understand and implement.
Guaranteed to find the correct answer as it checks all possibilities.

Cons:

Inefficient due to its quadratic time complexity. For larger values of n (though not in this problem's constraints), this approach would be too slow.

Code Solutions

Checking out 3 solutions in different languages for Two Furthest Houses With Different Colors. Click on different languages to view the code.

class Solution {
public
  int maxDistance(int[] colors) {
    int ans = 0, n = colors.length;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        if (colors[i] != colors[j]) {
          ans = Math.max(ans, Math.abs(i - j));
        }
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Two Furthest Houses With Different Colors

Patterns:

Greedy

Data Structures:

Array

Companies:

Visa |