Scale Engineer

Two Furthest Houses With Different Colors

Easy
#1892Time: O(n^2), where `n` is the number of houses. The nested loops lead to a number of comparisons proportional to n * n.Space: O(1), as it only uses a few variables to store the indices and the maximum distance, requiring constant extra space.1 company
Patterns
Greedy
Data structures
Array
Companies
Visa

Prompt

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 ith house.

Return the maximum distance between two houses with different colors.

The distance between the ith and jth 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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

O(n^2), where `n` is the number of houses. The nested loops lead to a number of comparisons proportional to n * n.

Space

O(1), as it only uses a few variables to store the indices and the maximum distance, requiring constant extra space.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem