Skip to main content
Talentd

Maximum Distance Between Unequal Words in Array II - Solution & Explanation

MediumPremiumFree on FleetCodeArrayString9 min read
Practice this problem

Problem Statement

You are given a string array words.

Find the maximum distance between two distinct indices i and j such that:

  • words[i] != words[j], and
  • the distance is defined as j - i + 1.

Return the maximum distance among all such pairs. If no valid pair exists, return 0.

 

Example 1:

Input: words = ["leetcode","leetcode","codeforces"]

Output: 3

Explanation:

In this example, words[0] and words[2] are not equal, and they have the maximum distance 2 - 0 + 1 = 3.

Example 2:

Input: words = ["a","b","c","a","a"]

Output: 4

Explanation:

In this example words[1] and words[4] have the largest distance of 4 - 1 + 1 = 4.

Example 3:

Input: words = ["z","z","z"]

Output: 0

Explanation:

​​​​​​​In this example all the words are equal, thus the answer is 0.

 

Constraints:

  • 1 <= words.length <= 105
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.

Approach Overview

Problem Overview: Given an array of words, return the maximum distance |i - j| such that words[i] != words[j]. The goal is to find the farthest pair of indices containing different strings.

Approach 1: Brute Force Pair Check (O(n²) time, O(1) space)

The direct solution checks every pair of indices (i, j). For each pair, compare the strings and update the maximum distance when they are different. This requires two nested loops: the outer loop fixes i, and the inner loop scans all j > i. While simple, the algorithm performs n(n-1)/2 comparisons in the worst case. With large arrays, this quickly becomes expensive. This approach still helps verify correctness before optimizing and demonstrates the core observation: only pairs with unequal strings contribute to the answer. The logic relies purely on sequential traversal of the array and string comparisons.

Approach 2: Two-End Scan Using Edge Differences (O(n) time, O(1) space)

The maximum distance between indices is always achieved using one of the array boundaries. If the first and last words differ (words[0] != words[n-1]), the answer is immediately n - 1. If they are equal, a full-span pair cannot be used, so search inward. Scan from the left to find the first index i where words[i] != words[0]. This pair produces distance (n - 1) - i. Then scan from the right to find the first index j where words[j] != words[n - 1]. This pair produces distance j - 0. The result is max(j, n - 1 - i). Only two linear passes are required, and no additional memory is needed.

The key insight: if the outer elements are equal, the optimal pair must include one boundary and the closest element from the opposite side that differs. Any interior pair will always produce a smaller distance. This makes a simple boundary scan sufficient.

Recommended for interviews: The two-end scan approach is the expected solution. It demonstrates that you reason about index distance rather than blindly checking all pairs. Mentioning the brute force method first shows understanding of the baseline, but deriving the O(n) boundary strategy signals strong array reasoning and efficient string comparison logic.

Solution

We can observe that at least one of the two words with maximum distance must be at either end of the array (i.e., at index 0 or n - 1). Otherwise, suppose the two words with maximum distance are at indices i and j where 0 < i < j < n - 1. Then words[0] must be the same as words[j], and words[n - 1] must be the same as words[i] (otherwise the distance would be greater). This means words[0] and words[n - 1] are different, and their distance n - 1 - 0 + 1 = n is definitely greater than j - i + 1, which contradicts our assumption. Therefore, at least one of the two words with maximum distance must be at either end of the array.

So, we only need to traverse the array, calculate the distance between each word and the words at both ends of the array, and update the maximum distance.

The time complexity is O(n), where n is the length of array words. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair ComparisonO(n²)O(1)Useful for understanding the problem or when the array size is very small
Two-End Boundary ScanO(n)O(1)Optimal solution for all inputs; minimizes comparisons while maximizing index distance

Video Solution

Maximum Distance Between Unequal Words In Array II • Owen Wu • 70 views views

Frequently Asked Questions

Is Maximum Distance Between Unequal Words in Array II easy or hard?
The problem is generally classified as Medium difficulty. The brute force idea is straightforward, but recognizing that the maximum distance must involve an array boundary is the key insight that leads to the optimal O(n) solution.
Maximum Distance Between Unequal Words in Array II Python/Java solution
The typical implementation uses two loops: one scanning from the left and another from the right to find the first unequal words relative to the boundaries. This logic translates directly into Python, Java, C++, Go, or TypeScript with constant space and linear time.
How to solve Maximum Distance Between Unequal Words in Array II in O(n)?
Check whether the first and last words differ. If they do, return n-1 immediately. If they are equal, scan from the left to find the first index with a different word and compute (n-1-i). Then scan from the right to find the first index different from the last word and compute j. The maximum of these two values is the answer.
What is the best approach for Maximum Distance Between Unequal Words in Array II?
The optimal approach scans the array edges. If the first and last words differ, the answer is n-1. Otherwise, scan from the left to find the first word different from words[0] and from the right to find the first word different from words[n-1]. The result is the larger of those two boundary distances. This runs in O(n) time with O(1) space.
Is Maximum Distance Between Unequal Words in Array II asked at Google/Amazon/Meta?
Problems that test array boundary reasoning and distance maximization commonly appear in interviews at companies like Amazon and Google. Variations of this question show up in coding rounds because the optimal solution requires recognizing a simple but non-obvious observation about array edges.
What data structure is used in Maximum Distance Between Unequal Words in Array II?
The solution uses a simple array traversal with string comparisons. No additional data structures such as hash maps or stacks are required. The algorithm relies on index scanning and constant extra variables.
What is the time complexity of Maximum Distance Between Unequal Words in Array II?
The optimal algorithm runs in O(n) time because it performs at most two linear scans of the array. Space complexity is O(1) since it only tracks a few indices. A naive brute force approach would require O(n²) comparisons.

Ready to solve this problem?

Practice Maximum Distance Between Unequal Words in Array II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays