Two Furthest Houses With Different Colors

🏠 ⬅️ ➡️

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.
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
✅ Correct 
program main
    implicit none

    integer, parameter :: n = 7
    integer, dimension(n) :: colors = (/ 1, 1, 1, 6, 1, 1, 1 /)
    integer :: max_distance

    max_distance = solve(colors)
    write (*, '(A, I0)') 'Maximum distance: ', max_distance

contains

    function solve(colors) result(max_distance)
        implicit none
        integer, intent(in) :: colors(:)
        integer :: i, j, distance, max_distance

        max_distance = 0
        do i = 1, size(colors) - 1
            do j = i + 1, size(colors)
                if (colors(i) /= colors(j)) then
                    distance = abs(i - j)
                    if (distance > max_distance) then
                        max_distance = distance
                    end if
                end if
            end do
        end do
    end function solve

end program main
✅ Compiled
❌ Executed
❌ Correct 
program maxDistance
      implicit none

      integer, parameter :: n = 100
      integer :: colors(n)
      integer :: i, j, maxDist

      read (*,*) colors

      maxDist = 0
      do i = 1, n - 1
          do j = i + 1, n
              if (colors(i) /= colors(j)) then
                  maxDist = max(maxDist, abs(i - j))
              end if
          end do
      end do

      write (*,*) maxDist

      end program maxDistance
🌐 Data from online sources 
from itertools import permutations

def maxCompatibilitySum(students, mentors):
    ans = 0
    for mentors_perm in permutations(mentors):
        cur_sum = sum(sum(a == b for a, b in zip(student, mentor)) for student, mentor in zip(students, mentors_perm))
        ans = max(ans, cur_sum)
    return ans

The algorithm first sorts both the students and the mentors arrays. Then, it finds all possible pairings between students and mentors. For each pairing, it calculates the compatibility score by counting the number of matching answers. The sum of the compatibility scores for each pairing is then calculated, and the maximum sum is returned as the final result.

In Python, the itertools.permutations function is used to generate all possible orderings of mentors. In Java, the arrays are sorted using compareTo on the string representation of the array. In JavaScript, the arrays are sorted using the join function to concatenate the array elements for comparison. For all languages, the helper function calculates the compatibility score sum and keeps track of the maximum sum found so far.

🌐 Data from online sources 
#include <vector>
#include <algorithm>

int maxCompatibilitySum(std::vector<std::vector<int>>& students, std::vector<std::vector<int>>& mentors) {
    std::sort(students.begin(), students.end());
    std::sort(mentors.begin(), mentors.end());
    int ans = 0;
    do {
        int cur_sum = 0;
        for (int i = 0; i < students.size(); i++) {
            int match = 0;
            for (int j = 0; j < students[i].size(); j++) {
                if (students[i][j] == mentors[i][j]) match++;
            }
            cur_sum += match;
        }
        ans = std::max(ans, cur_sum);
    } while (std::next_permutation(mentors.begin(), mentors.end()));
    return ans;
}

The algorithm first sorts both the students and the mentors arrays. Then, it finds all possible pairings between students and mentors. For each pairing, it calculates the compatibility score by counting the number of matching answers. The sum of the compatibility scores for each pairing is then calculated, and the maximum sum is returned as the final result.

In Python, the itertools.permutations function is used to generate all possible orderings of mentors. In Java, the arrays are sorted using compareTo on the string representation of the array. In JavaScript, the arrays are sorted using the join function to concatenate the array elements for comparison. For all languages, the helper function calculates the compatibility score sum and keeps track of the maximum sum found so far.