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.

&nbsp;
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.


&nbsp;
Constraints:


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


class Solution:
    def maxDistance(self, colors: List[int]) -> int:
        p, res = inf, 0
        for i, c in enumerate(colors):
            if (c != colors[0]):
                res = i
                p = min(p, i)
            else:
                res = max(res, i - p)
        return res
class Solution {
    public int maxDistance(int[] colors) {
        int l = 0, r = colors.length-1;
        while(colors[colors.length-1] == colors[l]) l++;
        while(colors[0] == colors[r]) r--;
        return Math.max(r, colors.length - 1 - l);
    }
}
class Solution {
public:
    int maxDistance(vector<int>& colors) {
        int Max = INT_MIN;
        int N = colors.size();
        
        // find the first house from the end which does not match the color of house at front
        int j=N;
        while(--j>=0 && colors[0]==colors[j]) { }   // worst-case O(n)
        Max = abs(j-0);
        
        // find the first house from the front which does not match the color of house at back
        j=-1;
        while(++j<N && colors[N-1]==colors[j]) { }  // worst-case O(n)
        Max = max(Max, abs(j-(N-1)));
        
        return Max;
    }
};
var maxDistance = function(colors) {
    // using two pointers from start and end
    // Time complexity O(n)
    // Space complexity O(1)
    
    const start = 0;
    const end = colors.length - 1;

    // maximum distance possible is length of arr, so start with two pointer
	// one at the start and one at the end
    const startColor = colors[start];
    const endColor = colors[end];
    
	// base condition, to check if they are not already equal
    if (startColor !== endColor) {
        return end;
    }
    
	// move the forward pointer till we find the differend color
    let forwardPtr = start;
    while (startColor === colors[forwardPtr]) {
        ++forwardPtr;
    }
    
    // move the backward pointer till we find the differend color
    let backwardPtr = end;
    while(endColor === colors[backwardPtr]) {
        --backwardPtr;
    }
    
    // Till here, We already know that startColor === endColor
    // hence we did two things,
 	// 1. we kept startColor fixed and moved backwardPtr till we find different color
    // 2. similarly, we kept endColor fixed and moved the forwardPtr till we find the different color.
   // we will return the max different out of two now.
    return Math.max(Math.abs(start - backwardPtr), Math.abs(end - forwardPtr));
    
};
Two Furthest Houses With Different Colors