algoadvance

Leetcode 2078. Two Furthest Houses With Different Colors

Problem Statement

This problem requires finding the maximum distance between two houses in a row that have different colors. The input is an array colors where each element represents the color of the house at that position.

Example:

Explanation:

Clarifying Questions

To be thorough, let’s confirm a few details:

  1. Can the array have fewer than two houses? (If there’s only one house, there’s no valid answer as there can’t be two houses with different colors).
  2. Are colors guaranteed to be integers?
  3. Can the same color appear more than once in the array?

For the purposes of this solution, we will assume:

Strategy

  1. Brute Force Approach:
    • Using a nested loop to compare the distance between every possible pair of houses with different colors.
    • This is inefficient as it would have a time complexity of O(n^2).
  2. Optimized Approach:
    • Realize that to maximize the distance, we should consider the houses at the ends of the array.
    • Check the distance between the first house and the furthest house from the end with a different color.
    • Similarly, check the distance between the last house and the furthest house from the start with a different color.
    • The answer will be the maximum of these two distances.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxDistance(std::vector<int>& colors) {
        int n = colors.size();
        int maxDist = 0;
        
        // Check from start to end
        for (int i = 0; i < n; ++i) {
            if (colors[i] != colors[0]) {
                maxDist = std::max(maxDist, i);
            }
        }
        
        // Check from end to start
        for (int i = n - 1; i >= 0; --i) {
            if (colors[i] != colors[n - 1]) {
                maxDist = std::max(maxDist, n - 1 - i);
            }
        }
        
        return maxDist;
    }
};

// Example usage
// int main() {
//     Solution sol;
//     std::vector<int> colors = {1,1,1,6,1,1,1};
//     std::cout << "Maximum distance: " << sol.maxDistance(colors) << std::endl;
//     return 0;
// }

Time Complexity

The time complexity of this solution is O(n), where n is the number of houses. This is because we are essentially traversing the list of houses twice, once from the beginning and once from the end. This is more optimal than the O(n^2) brute force approach.

Explanation of Code

  1. We initialize maxDist to zero.
  2. We perform a loop from the beginning of the array and check the distance from the start to the first house that has a different color than the first house.
  3. We then perform a reverse loop from the end of the array and check the distance from the end to the first house that has a different color than the last house.
  4. The resulting maxDist is the maximum of these two distances, which gives our final answer.

This approach ensures that we efficiently find the maximum distance between the furthest houses with different colors.

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