Maximum Hamming Distances - Video Solutions

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.