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.

Description Hints 5 Solution Video 41:39

3141. Maximum Hamming Distances

Hard50.0% acceptancePremium elsewhere, free here

Given an array nums and an integer m, with each element nums[i] satisfying 0 <= nums[i] < 2^m, 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 <= 2^m
0 <= nums[i] < 2^m

Topics

Hints open one at a time

Hint 1

For each nums[i], complement it (for each bit, if it is 1, it becomes 0 and vice-versa).

Hint 2

Instead of finding the maximum Hamming distance from x = nums[i], let's think of finding the minimum Hamming distance from the complement of x to any element of the array.

Hint 3

Create a graph with V = {0, 1, ..., 2^m - 1}. Put an edge between two vertices if they differ in exactly one bit.

Hint 4

Run a multi-source BFS from elements of nums.

Hint 5

Now for each x, to find its minimum Hamming distance from elements of the array, simply calculate its shortest path from array elements.

41:39

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[9,12,9,11]
4

Input

[3,4,6,10]
4

Your code is saved on this device.Solution