Skip to main content
Talentd

Maximum Hamming Distances - Solution & Explanation

HardPremiumFree on FleetCodeArrayBit ManipulationBreadth-First Search12 min read
Practice this problem

Problem Statement

Given an array nums and an integer m, with each element nums[i] satisfying 0 <= nums[i] < 2m, return an array answer. The answer array should be of the same length as nums, where each element answer[i] represents the maximum Hamming distance between nums[i] and any other element nums[j] in the array.

The Hamming distance between two binary integers is defined as the number of positions at which the corresponding bits differ (add leading zeroes if needed).

 

Example 1:

Input: nums = [9,12,9,11], m = 4

Output: [2,3,2,3]

Explanation:

The binary representation of nums = [1001,1100,1001,1011].

The maximum hamming distances for each index are:

  • nums[0]: 1001 and 1100 have a distance of 2.
  • nums[1]: 1100 and 1011 have a distance of 3.
  • nums[2]: 1001 and 1100 have a distance of 2.
  • nums[3]: 1011 and 1100 have a distance of 3.

Example 2:

Input: nums = [3,4,6,10], m = 4

Output: [3,3,2,3]

Explanation:

The binary representation of nums = [0011,0100,0110,1010].

The maximum hamming distances for each index are:

  • nums[0]: 0011 and 0100 have a distance of 3.
  • nums[1]: 0100 and 0011 have a distance of 3.
  • nums[2]: 0110 and 1010 have a distance of 2.
  • nums[3]: 1010 and 0100 have a distance of 3.

 

Constraints:

  • 1 <= m <= 17
  • 2 <= nums.length <= 2m
  • 0 <= nums[i] < 2m

Approach Overview

Problem Overview: Given an array of integers where each value fits within m bits, compute the maximum Hamming distance between each number and any other number in the array. The Hamming distance counts how many bit positions differ between two numbers.

Approach 1: Pairwise Comparison (Brute Force) (Time: O(n^2 * m), Space: O(1))

The most direct method checks every pair of numbers and computes their Hamming distance using popcount(a ^ b). Iterate through the array, compare each element with all others, and track the maximum distance for each index. This approach is easy to implement and demonstrates the definition of Hamming distance clearly. However, the nested iteration makes it impractical for large arrays because every pair is evaluated explicitly. It works only when n is small.

Approach 2: Reverse Thinking + Multi-Source BFS on Bitmasks (Time: O(m * 2^m), Space: O(2^m))

The optimized solution treats every possible m-bit number as a node in a hypercube graph. Two nodes are connected if their bitmasks differ by exactly one bit. Instead of searching for the farthest number directly, reverse the thinking: compute the minimum Hamming distance from every bitmask to the closest value in the array. Initialize a multi-source BFS from all numbers in nums with distance 0. From each mask, generate neighbors by flipping one bit (mask ^ (1 << bit)) and propagate distances. This BFS effectively fills the entire 2^m state space.

To obtain the maximum Hamming distance for a number x, use its bitwise complement within the m-bit space: target = mask ^ x where mask = (1 << m) - 1. The BFS already computed the minimum distance from target to any number in the array. Because Hamming(x, y) = m - Hamming(~x, y), the answer becomes m - dist[target]. This trick converts a "maximum distance" problem into a "minimum distance" search over the bitmask graph.

The approach relies heavily on efficient bit operations and a queue-based traversal similar to standard Breadth-First Search. Each state flips one bit using Bit Manipulation, and the input values come from an Array. Because the total state space is bounded by 2^m, the BFS remains feasible when m is small (commonly ≤ 17).

Recommended for interviews: The brute force approach demonstrates understanding of Hamming distance using XOR and popcount, but interviewers expect the reverse-thinking BFS optimization. Recognizing the hypercube structure and converting a maximum-distance query into a minimum-distance BFS shows strong problem-solving skills with bitmasks and graph traversal.

Solution

The problem requires us to find the maximum Hamming distance between each element and other elements in the array. We can think in reverse: for each element, we take its complement and find the minimum Hamming distance to other elements in the array. Then, the maximum Hamming distance we are looking for is m minus this minimum Hamming distance.

We can use Breadth-First Search (BFS) to find the minimum Hamming distance from each complemented element to other elements.

The specific steps are as follows:

  1. Initialize an array dist with a length of 2^m to record the minimum Hamming distance from each complemented element to other elements. Initially, all are set to -1.
  2. Traverse the array nums, set the complement of each element to 0, and add it to the queue q.
  3. Starting from k = 1, continuously traverse the queue q. Each time, take out the elements in the queue, perform m complement operations on them, add the complemented elements to the queue t, and set the minimum Hamming distance to the original element to k.
  4. Repeat step 3 until the queue is empty.

Finally, we traverse the array nums, take the complement of each element as the index, and take out the corresponding minimum Hamming distance from the dist array. Then, m minus this value is the maximum Hamming distance we are looking for.

The time complexity is O(2^m), and the space complexity is O(2^m), where m is the integer given in the problem.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Pairwise Comparison (Brute Force)O(n^2 * m)O(1)Small arrays where simplicity matters more than performance
Reverse Thinking + Multi-Source BFSO(m * 2^m)O(2^m)General case when bit length is limited and optimal performance is required

Video Solution

3141. Maximum Hamming Distances (Leetcode Hard) • Programming Live with Larry • 374 views views

Frequently Asked Questions

Is Maximum Hamming Distances easy or hard?
Maximum Hamming Distances is classified as a Hard problem. The challenge is recognizing that maximizing Hamming distance can be transformed into a minimum-distance BFS over all bitmasks, which is not immediately obvious from the problem statement.
Maximum Hamming Distances Python/Java solution
Implement the BFS using a queue and a distance array of size 2^m. Initialize all input numbers with distance 0, push them into the queue, and expand neighbors by flipping each bit. After BFS finishes, compute the result for each number using m - dist[mask ^ x]. The same logic works in Python, Java, C++, Go, and TypeScript.
How to solve Maximum Hamming Distances in O(m * 2^m)?
Treat every m-bit integer as a node in a graph and connect nodes that differ by one bit. Perform a multi-source BFS starting from all numbers in the array to compute the minimum distance to each mask. For a number x, compute mask ^ x (its complement) and return m - dist[mask ^ x].
What is the best approach for Maximum Hamming Distances?
The most efficient approach uses reverse thinking with multi-source BFS over all m-bit masks. Start BFS from every number in the array and compute the minimum Hamming distance to each mask. For each value x, check the distance of its m-bit complement and compute m - dist[mask ^ x]. This runs in O(m * 2^m) time.
Is Maximum Hamming Distances asked at Google/Amazon/Meta?
Bitmask BFS and Hamming distance problems appear in interviews at companies like Google, Amazon, and Meta because they test bit manipulation, graph modeling, and optimization thinking. Variants of hypercube BFS and XOR distance problems are common in advanced interview rounds.
What data structure is used in Maximum Hamming Distances?
The optimized solution uses a queue for BFS traversal, an array to store distances for all bitmasks, and bit manipulation operations like XOR and bit flips. The conceptual graph is a hypercube where each node represents an m-bit number.
What is the time complexity of Maximum Hamming Distances?
The optimal solution runs in O(m * 2^m) time and O(2^m) space, where m is the number of bits used to represent values. A brute force solution that compares every pair requires O(n^2 * m) time.

Ready to solve this problem?

Practice Maximum Hamming Distances with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays