algoadvance

Leetcode 2078. Two Furthest Houses With Different Colors

Problem Statement

You are given an array colors where colors[i] is the color of the i-th house. Return the maximum distance between two houses with different colors.

Example:

Input: colors = [1, 1, 2, 3, 1, 2]
Output: 5
Explanation: The furthest two houses with different colors are house 0 (color 1) and house 5 (color 2), which are 5 units apart.

Clarifying Questions

  1. Q: What is the range of the length of the array?
    • A: The length of the array colors can range from 2 to 100.
  2. Q: What is the range of the values in the array?
    • A: The values in the array represent colors and can range from 0 to 100.
  3. Q: Can there be multiple colors being the same in the array?
    • A: Yes, there can be multiple occurrences of the same color.
  4. Q: Are the indices 0-based?
    • A: Yes, the problem assumes a 0-based index for the array.

Strategy

  1. We need to find the maximum distance between two houses with different colors.
  2. We will explore two main directions:
    • From the start of the array, find the furthest house with a different color from the last house.
    • From the end of the array, find the furthest house with a different color from the first house.
  3. The maximum of these two distances will be our answer.

Code

public class FurthestHouses {
    public int maxDistance(int[] colors) {
        int n = colors.length;
        int maxDistance = 0;
        
        // Check distance from the first house
        for (int i = n - 1; i >= 0; i--) {
            if (colors[i] != colors[0]) {
                maxDistance = Math.max(maxDistance, i);
                break;
            }
        }

        // Check distance from the last house
        for (int i = 0; i < n; i++) {
            if (colors[i] != colors[n - 1]) {
                maxDistance = Math.max(maxDistance, n - 1 - i);
                break;
            }
        }

        return maxDistance;
    }

    public static void main(String[] args) {
        FurthestHouses fh = new FurthestHouses();
        int[] colors = {1, 1, 2, 3, 1, 2};
        System.out.println(fh.maxDistance(colors)); // Output: 5
    }
}

Time Complexity

By following this strategy, we ensure that we cover all edge cases and obtain the correct maximum distance efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI