Facebook Pixel

3141. Maximum Hamming Distances πŸ”’


Problem Description

Given an array nums and an integer m, each element nums[i] satisfies 0 <= nums[i] < 2^m. You need to return an array answer where each 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 the number of positions at which the corresponding bits differ (add leading zeros if necessary).

Intuition

To solve the problem, we utilize a conceptual approach where we reverse the thinking process. Instead of directly calculating the maximum Hamming distance for each number in nums, consider the complement of each number. The idea is to determine the minimum Hamming distance between the complement of a number and other elements in nums. The maximum Hamming distance is then calculated as m minus this minimum distance.

The solution involves using a Breadth-First Search (BFS) technique to explore the distances efficiently:

  1. Initialize an array dist of size 2^m to store the minimum Hamming distance for each possible number. Initially, all distances are set to -1.
  2. Loop through nums, set a distance of 0 for each number in dist, and add these numbers to a processing queue q.
  3. Use BFS to traverse through the queue q, flipping each bit position iteratively to find the minimum Hamming distances for new numbers added to the search queue.
  4. For each number, the minimum distance from dist helps determine the maximum Hamming distance by subtracting this distance from m.

This approach ensures that we efficiently compute the complementary distances and derive the maximum Hamming distances effectively.

Learn more about Breadth-First Search patterns.

Solution Approach

The solution utilizes the Breadth-First Search (BFS) algorithm along with a bit manipulation technique to efficiently determine the maximum Hamming distances. Here is a step-by-step breakdown of the implementation:

  1. Initialize Distance Array:

    • Create an array dist of size 2^m, with each element initialized to -1. This array will store the minimum Hamming distance from the complement of each number in nums to any number in nums.
  2. Set Initial Distances:

    • Traverse through each element x in nums. For every x, set dist[x] = 0, effectively marking that x is already encountered.
  3. Breadth-First Search to Calculate Minimum Distances:

    • Initialize a queue q with all elements of nums to start the BFS.
    • Set k = 1 to keep track of the current minimum Hamming distance.
    • While the queue q is not empty, perform the following:
      • Initialize a temporary queue t.
      • For each number x dequeued from q, generate all possible numbers y by flipping each bit position i in x using y = x ^ (1 << i).
      • If dist[y] is still -1, append y to the temporary queue t, and mark dist[y] with the distance k.
  4. Increment Hamming Distance for Next Level:

    • Assign q = t and increase k by 1 to process the next level of distances in the next BFS iteration.
  5. Calculate Maximum Hamming Distances:

    • For each x in nums, calculate the maximum Hamming distance using the formula m - dist[x ^ ((1 << m) - 1)]. Here, ((1 << m) - 1) represents the mask with all m bits set to 1, effectively complementing the number x.

This BFS method efficiently finds the minimum distances from each complement, enabling the computation of maximum Hamming distances by utilizing bit manipulation techniques.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple example to walk through the solution approach. Suppose we have nums = [1, 2] and m = 2.

  1. Initialize Distance Array:

    • We'll create a dist array of size 2^2 = 4, initialized to [-1, -1, -1, -1].
  2. Set Initial Distances:

    • For each number in nums, set its distance to 0:
      • nums[0] = 1, so dist[1] = 0 resulting in dist = [-1, 0, -1, -1].
      • nums[1] = 2, so dist[2] = 0 resulting in dist = [-1, 0, 0, -1].
  3. Breadth-First Search to Calculate Minimum Distances:

    • Prepare a queue q initialized with [1, 2].

    • Start with k = 1, indicating the current minimum Hamming distance.

    • BFS Iteration:

      • For x = 1 (from the queue):

        • Flip each bit:
          • 0 ^ 1, gives 1 ^ 1 = 0, update dist = [1, 0, 0, -1], add 0 to a temporary queue t.
          • 1 ^ 2, gives 1 ^ 2 = 3, update dist = [1, 0, 0, 1], add 3 to the temporary queue t.
      • For x = 2 (from the queue):

        • Flip each bit:
          • 2 ^ 1, gives 2 ^ 1 = 3, already handled.
          • 2 ^ 2, gives 2 ^ 2 = 0, already handled.
      • Update queue q = [0, 3] and increment k = 2.

  4. Calculate Maximum Hamming Distances:

    • Final step is to calculate the maximum Hamming distance for each element in nums:
      • For x = 1, compute dist[1 ^ 3] = dist[2] = 0. Maximum Hamming distance = m - dist[2] = 2 - 0 = 2.
      • For x = 2, compute dist[2 ^ 3] = dist[1] = 0. Maximum Hamming distance = 2 - 0 = 2.

Result: The answer array is [2, 2].

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxHammingDistances(self, nums: List[int], m: int) -> List[int]:
5        # Initialize distances array with -1, indicating unvisited nodes
6        dist = [-1] * (1 << m)
7      
8        # Set the distance of nodes present in `nums` to 0
9        for x in nums:
10            dist[x] = 0
11      
12        # Initialize the queue with elements from nums
13        q = nums
14        k = 1  # Distance increment for each level
15      
16        # Perform a breadth-first search (BFS) like update over bit positions
17        while q:
18            temp = []  # Temporary list to hold next nodes to visit
19            for x in q:
20                for i in range(m):
21                    # Toggle the i-th bit of x
22                    y = x ^ (1 << i)
23                    # If `y` has not been visited, update distance and add to temp
24                    if dist[y] == -1:
25                        temp.append(y)
26                        dist[y] = k
27          
28            # Move to next level of BFS
29            q = temp
30            k += 1
31      
32        # Calculate and return the maximum Hamming distances
33        return [m - dist[x ^ ((1 << m) - 1)] for x in nums]
34
1import java.util.Arrays;
2import java.util.Deque;
3import java.util.ArrayDeque;
4
5class Solution {
6    /**
7     * Calculates the maximum Hamming distances for each element in the nums array.
8     *
9     * @param nums an array of integers
10     * @param m an integer representing the number of bits
11     * @return an array of maximum Hamming distances for each element in nums
12     */
13    public int[] maxHammingDistances(int[] nums, int m) {
14        // Initialize the distance array with size 2^m and fill it with -1
15        int[] dist = new int[1 << m];
16        Arrays.fill(dist, -1);
17
18        // A queue to store elements that are processed to find their Hamming distance
19        Deque<Integer> queue = new ArrayDeque<>();
20
21        // Set initial distance for given numbers in nums as 0 and add them to queue
22        for (int num : nums) {
23            dist[num] = 0;
24            queue.offer(num);
25        }
26
27        // Perform breadth-first search to compute the Hamming distances
28        for (int k = 1; !queue.isEmpty(); ++k) {
29            int size = queue.size();
30            for (int t = 0; t < size; ++t) {
31                int current = queue.poll();
32                // Try flipping each bit to find new numbers
33                for (int i = 0; i < m; ++i) {
34                    int flipped = current ^ (1 << i);
35                    // If this number has not been encountered yet, set its distance and add to queue
36                    if (dist[flipped] == -1) {
37                        queue.offer(flipped);
38                        dist[flipped] = k;
39                    }
40                }
41            }
42        }
43
44        // Calculate the maximum Hamming distance and update the nums array
45        for (int i = 0; i < nums.length; ++i) {
46            nums[i] = m - dist[nums[i] ^ ((1 << m) - 1)];
47        }
48      
49        return nums;
50    }
51}
52
1class Solution {
2public:
3    vector<int> maxHammingDistances(vector<int>& nums, int m) {
4        // Array to store distance for each possible number in the range [0, 2^m).
5        int dist[1 << m];  
6      
7        // Initialize all distances to -1.
8        memset(dist, -1, sizeof(dist));  
9      
10        // Queue for breadth-first search (BFS).
11        queue<int> bfsQueue;  
12      
13        // Set initial distances for numbers in `nums` and add them to the queue.
14        for (int x : nums) {  
15            dist[x] = 0;  // Distance for numbers in `nums` starts at 0.
16            bfsQueue.push(x);
17        }
18      
19        // Perform BFS from each number in `nums`.
20        for (int k = 1; !bfsQueue.empty(); ++k) {
21            // Process each level in the BFS.
22            for (int nodesInCurrentLevel = bfsQueue.size(); nodesInCurrentLevel > 0; --nodesInCurrentLevel) {
23                int current = bfsQueue.front();
24                bfsQueue.pop();
25              
26                // Try flipping each bit to generate new numbers.
27                for (int i = 0; i < m; ++i) {
28                    int neighbor = current ^ (1 << i);
29                    // If the neighbor hasn't been visited, set its distance and add it to the queue.
30                    if (dist[neighbor] == -1) {
31                        dist[neighbor] = k;  
32                        bfsQueue.push(neighbor);
33                    }
34                }
35            }
36        }
37      
38        // Calculate the maximum Hamming distance for each number in `nums`.
39        for (int& x : nums) {
40            x = m - dist[x ^ ((1 << m) - 1)];
41        }
42      
43        return nums;  // Return the modified array with max Hamming distances.
44    }
45};
46
1/**
2 * Function to calculate maximum Hamming distances for each number in the array.
3 * @param nums - An array of numbers for which to calculate the max Hamming distances.
4 * @param m - The number of bits.
5 * @returns An array containing the max Hamming distances for each number.
6 */
7function maxHammingDistances(nums: number[], m: number): number[] {
8    // Initialize a distance array with -1 of size 2^m
9    const dist: number[] = Array.from({ length: 1 << m }, () => -1);
10
11    // Initialize a queue for processing numbers
12    const q: number[] = [];
13
14    // Fill initial distances and populate the queue
15    for (const x of nums) {
16        dist[x] = 0;
17        q.push(x);
18    }
19
20    // Perform BFS to compute distances for all values
21    for (let k = 1; q.length; ++k) {
22        const t: number[] = []; // Temporary queue for next layer
23
24        // Process each number in the current queue
25        for (const x of q) {
26            // Flip each bit and check new values
27            for (let i = 0; i < m; ++i) {
28                const y = x ^ (1 << i); // Flip the i-th bit
29
30                // If not visited, update distance and add to temporary queue
31                if (dist[y] === -1) {
32                    dist[y] = k;
33                    t.push(y);
34                }
35            }
36        }
37
38        // Move to the next layer
39        q.splice(0, q.length, ...t);
40    }
41
42    // Calculate final max Hamming distances
43    for (let i = 0; i < nums.length; ++i) {
44        nums[i] = m - dist[nums[i] ^ ((1 << m) - 1)];
45    }
46
47    return nums;
48}
49

Time and Space Complexity

The time complexity of the code is O(2^m). This is due to the operations involved in exploring the Hamming distances, where each possible integer within the range 0 to 2^m - 1 is considered. Specifically, each potential combination of m bits is processed, and bitwise operations are applied over an exhaustive bit pattern set.

The space complexity is also O(2^m). The array dist is initialized to contain 2^m elements, each representing the maximum possible distinct integers that can be formed with m bits. The intermediate queue q in the BFS (breadth-first search) process similarly can grow to hold that many nodes at any instant.

Learn more about how to find time and space complexity quickly.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Depth first search is equivalent to which of the tree traversal order?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!


Load More