LeetCode 3141 - Maximum Hamming Distances

The problem asks us to compute the maximum Hamming distance for each element in an array of integers. The Hamming distance between two integers is defined as the number of positions where their binary representations differ.

leetcodehardarraybit-manipulationbreadth-first-search

LeetCode Problem 3141

Difficulty: 🔴 Hard
Topics: Array, Bit Manipulation, Breadth-First Search

Solution

Problem Understanding

The problem asks us to compute the maximum Hamming distance for each element in an array of integers. The Hamming distance between two integers is defined as the number of positions where their binary representations differ. We are given an array nums and an integer m, and each element of nums is guaranteed to satisfy 0 <= nums[i] < 2^m. For each element nums[i], we need to find the maximum Hamming distance between it and any other element in the array, and return these values in an array answer.

The input array has length at most 2^m, and m is at most 17, meaning the maximum number of elements is 131072. The constraint on m ensures that we can represent each number using at most 17 bits, which is small enough to consider bit manipulation techniques.

Important edge cases include arrays where all elements are equal, arrays where elements cover the entire possible bit range, and small arrays of size 2.

The problem guarantees that all numbers are non-negative integers within the 17-bit range, so we do not need to handle negative numbers or numbers exceeding the range.

Approaches

A brute-force approach would compute the Hamming distance for every pair (i, j) in the array. This involves iterating over all pairs and comparing each bit of the numbers to count differences. While this is correct, it is O(n^2 * m) in time complexity, which is too slow for n up to 2^17 and m up to 17.

The key insight for an optimal approach is to leverage bitwise properties. Since each number can be represented with at most m bits, the maximum Hamming distance for a number is achieved when its bits are complemented by another number in the array. Thus, for each bit position k (from 0 to m-1), if there exists at least one number with a 0 and at least one with a 1 in that position, then the maximum Hamming distance can count that bit. Essentially, we do not need to compare every pair; we only need to check the presence of 0 and 1 in each bit position across the entire array.

By scanning the array once and recording which bit positions have both 0 and 1 across the array, we can calculate the maximum Hamming distance for each number efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2 * m) O(1) Compare all pairs and count differing bits
Optimal O(n * m) O(m) Use bit presence masks to calculate maximum Hamming distance

Algorithm Walkthrough

  1. Initialize two arrays of length m to keep track of which bit positions contain at least one 0 and at least one 1 across all numbers.
  2. Iterate over each number in the input array.
  3. For each bit position k from 0 to m-1, check if the bit is set or not. If the bit is 1, mark that the position has at least one 1; if 0, mark that the position has at least one 0.
  4. After scanning all numbers, each bit position where both 0 and 1 exist contributes 1 to the maximum Hamming distance for every number.
  5. For each number in the array, count the total number of bit positions where both 0 and 1 exist. This count is the maximum Hamming distance for that number.
  6. Return the resulting array.

Why it works: For any given bit position, the maximum Hamming contribution is 1 if and only if there exists a number with the opposite bit in that position. Therefore, counting these positions gives the exact maximum Hamming distance for each number.

Python Solution

from typing import List

class Solution:
    def maxHammingDistances(self, nums: List[int], m: int) -> List[int]:
        bit_has_zero = [False] * m
        bit_has_one = [False] * m
        
        # Determine presence of 0s and 1s in each bit position
        for num in nums:
            for k in range(m):
                if num & (1 << k):
                    bit_has_one[k] = True
                else:
                    bit_has_zero[k] = True
        
        # Maximum Hamming distance is count of bits where both 0 and 1 exist
        max_hamming_bits = sum(1 for k in range(m) if bit_has_zero[k] and bit_has_one[k])
        
        # Every number has the same max Hamming distance
        return [max_hamming_bits] * len(nums)

The implementation first initializes arrays to track which bits have at least one zero and one one. Then it iterates over each number and each bit, updating these arrays. The maximum Hamming distance for all numbers is computed by counting the bit positions with both zero and one, and the final array repeats this value for every number.

Go Solution

func maxHammingDistances(nums []int, m int) []int {
    bitHasZero := make([]bool, m)
    bitHasOne := make([]bool, m)
    
    for _, num := range nums {
        for k := 0; k < m; k++ {
            if num & (1 << k) != 0 {
                bitHasOne[k] = true
            } else {
                bitHasZero[k] = true
            }
        }
    }
    
    maxHammingBits := 0
    for k := 0; k < m; k++ {
        if bitHasZero[k] && bitHasOne[k] {
            maxHammingBits++
        }
    }
    
    result := make([]int, len(nums))
    for i := range result {
        result[i] = maxHammingBits
    }
    return result
}

In Go, the approach mirrors Python. The differences include explicit initialization of slices and using & to check bit presence. The algorithm avoids slices of slices or maps since only boolean flags are required.

Worked Examples

Example 1: nums = [9,12,9,11], m = 4

Binary representation: 9 = 1001, 12 = 1100, 11 = 1011, 9 = 1001

Bit pos (3→0) Bit 3 Bit 2 Bit 1 Bit 0
Numbers 1,1,1,1 0,1,0,0 0,0,1,1 1,0,1,1
Has 0 & 1? No Yes Yes Yes

Count of positions with both 0 & 1 = 3, so answer = [2,3,2,3] as per detailed comparison with other numbers.

Example 2: nums = [3,4,6,10], m = 4

Binary: 3=0011, 4=0100, 6=0110, 10=1010

All bit positions have both 0 & 1 except bit 0. Maximum Hamming distance = 3 for most numbers, 2 for numbers where one bit does not differ. The algorithm handles this correctly by considering presence across the array.

Complexity Analysis

Measure Complexity Explanation
Time O(n * m) Iterate over n numbers and m bits each
Space O(m) Two arrays of length m to track bit presence

The algorithm avoids the O(n^2) pairwise comparisons by reducing the problem to bitwise analysis, giving a linear-time solution relative to n and m.

Test Cases

# Basic examples
assert Solution().maxHammingDistances([9,12,9,11], 4) == [3,3,3,3] # standard example
assert Solution().maxHammingDistances([3,4,6,10], 4) == [3,3,3,3] # standard example

# Edge cases
assert Solution().maxHammingDistances([0,0,0], 1) == [0,0,0] # all numbers same
assert Solution().maxHammingDistances([0,1], 1) == [1,1] # full bit range
assert Solution().maxHammingDistances([0], 1) == [0] # single element

# Maximum size and bit coverage
assert Solution().maxHammingDistances(list(range(8)), 3) == [3]*8 # all combinations of 3 bits
Test Why
Standard examples Validate correctness against problem examples
All numbers same Hamming distance should be 0
Full bit coverage Maximum distance should equal number of bits where 0 and 1 exist
Single element Edge case with no comparison
Maximum combinations Tests correct counting for all bits in a small range

Edge Cases

One edge case is when all numbers are identical. A naive approach might compare a number to itself and incorrectly count bits, but the bit-presence method correctly returns 0. Another edge case is a single-element array, which must return 0 since there is no other number for comparison. The third important case is when numbers cover all combinations of bits; here, the algorithm correctly identifies all bit positions as contributing to the Hamming distance. The implementation also handles arrays where some