Two Furthest Houses With Different Colors

Easy
1116.

Two Furthest Houses With Different Colors

Two Furthest Houses With Different Colors is an easy coding problem on arrays and greedy, asked in Amazon and Google interviews.

n houses stand in a row, and colors[i] is the colour of house i. The distance between houses i and j is |i - j|.

Return the largest distance between two houses of different colours. At least two houses have different colours.

Example 1

Input
colors = [2,2,5,2,2]
Output
2
Explanation
House 2 is the only one with colour 5; it is 2 away from both ends.

Example 2

Input
colors = [4,8]
Output
1

Example 3

Input
colors = [3,1,3,3,3,3]
Output
4
Explanation
Houses 1 and 5.

Constraints

  • 2 <= n <= 100
  • n == colors.length
  • 0 <= colors[i] <= 100
  • At least two houses have different colours
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} colors
 * @return {number}
 */
var maxDistance = function(colors) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Two Furthest Houses With Different Colors — Solution

Two Furthest Houses With Different Colors solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Two Furthest Houses With Different Colors is an easy coding problem on arrays and greedy, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays, Greedy
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

n houses stand in a row, and colors[i] is the colour of house i. The distance between houses i and j is |i - j|.

Return the largest distance between two houses of different colours. At least two houses have different colours.

Example 1

Input: colors = [2,2,5,2,2]
Output: 2
Explanation: House 2 is the only one with colour 5; it is 2 away from both ends.

Example 2

Input: colors = [4,8]
Output: 1

Example 3

Input: colors = [3,1,3,3,3,3]
Output: 4
Explanation: Houses 1 and 5.

Constraints

  • 2 <= n <= 100
  • n == colors.length
  • 0 <= colors[i] <= 100
  • At least two houses have different colours

Hints for Two Furthest Houses With Different Colors

  1. Hint 1

    One end of the best pair can always be the first house or the last house.

  2. Hint 2

    If the first and last houses differ, the answer is n - 1.

  3. Hint 3

    Otherwise compare: the furthest house from the left end whose colour differs from colors[0], and the furthest house from the right end whose colour differs from colors[n - 1].

How to solve Two Furthest Houses With Different Colors

An optimal pair can always be stretched to touch an end of the row, so only pairs involving house 0 or house n - 1 need checking.

Approach

  1. Find the largest j with colors[j] != colors[0]; it gives distance j.
  2. Find the smallest i with colors[i] != colors[n - 1]; it gives distance n - 1 - i.
  3. Return the larger of the two.

Why it works

Take an optimal pair i < j. If colors[j] != colors[0], the pair (0, j) is at least as long, and the first scan finds some j' >= j. If colors[i] != colors[n - 1], the pair (i, n - 1) is at least as long, and the second scan finds some i' <= i. Otherwise colors[0] == colors[j] and colors[n - 1] == colors[i], so the two ends differ and the first scan already returns n - 1, the largest distance there is.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Checking only pairs that use house 0 returns 1 on [2,1,2,2,2], whose answer is 3 — scan from both ends.
  • The brute-force double loop is fine for n ≤ 100, but the end-anchored scan is O(n).
  • Colours may be 0, so do not use 0 as a 'no colour' sentinel.

Reference solution

Python

from typing import List

def maxDistance(colors: List[int]) -> int:
    n = len(colors)
    best = 0
    for j in range(n - 1, -1, -1):
        if colors[j] != colors[0]:
            best = j
            break
    for i in range(n):
        if colors[i] != colors[n - 1]:
            best = max(best, n - 1 - i)
            break
    return best

Java

public static int maxDistance(int[] colors) {
    int n = colors.length, best = 0;
    for (int j = n - 1; j >= 0; j--) {
        if (colors[j] != colors[0]) { best = j; break; }
    }
    for (int i = 0; i < n; i++) {
        if (colors[i] != colors[n - 1]) { best = Math.max(best, n - 1 - i); break; }
    }
    return best;
}

C++

int maxDistance(vector<int>& colors) {
    int n = colors.size(), best = 0;
    for (int j = n - 1; j >= 0; j--) {
        if (colors[j] != colors[0]) { best = j; break; }
    }
    for (int i = 0; i < n; i++) {
        if (colors[i] != colors[n - 1]) { best = max(best, n - 1 - i); break; }
    }
    return best;
}

JavaScript

var maxDistance = function(colors) {
    var n = colors.length, best = 0;
    for (var j = n - 1; j >= 0; j--) {
        if (colors[j] !== colors[0]) { best = j; break; }
    }
    for (var i = 0; i < n; i++) {
        if (colors[i] !== colors[n - 1]) { best = Math.max(best, n - 1 - i); break; }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms