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:
- Initialize an array
dist
of size2^m
to store the minimum Hamming distance for each possible number. Initially, all distances are set to -1. - Loop through
nums
, set a distance of 0 for each number indist
, and add these numbers to a processing queueq
. - 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. - For each number, the minimum distance from
dist
helps determine the maximum Hamming distance by subtracting this distance fromm
.
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:
-
Initialize Distance Array:
- Create an array
dist
of size2^m
, with each element initialized to-1
. This array will store the minimum Hamming distance from the complement of each number innums
to any number innums
.
- Create an array
-
Set Initial Distances:
- Traverse through each element
x
innums
. For everyx
, setdist[x] = 0
, effectively marking thatx
is already encountered.
- Traverse through each element
-
Breadth-First Search to Calculate Minimum Distances:
- Initialize a queue
q
with all elements ofnums
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 fromq
, generate all possible numbersy
by flipping each bit positioni
inx
usingy = x ^ (1 << i)
. - If
dist[y]
is still-1
, appendy
to the temporary queuet
, and markdist[y]
with the distancek
.
- Initialize a temporary queue
- Initialize a queue
-
Increment Hamming Distance for Next Level:
- Assign
q = t
and increasek
by 1 to process the next level of distances in the next BFS iteration.
- Assign
-
Calculate Maximum Hamming Distances:
- For each
x
innums
, calculate the maximum Hamming distance using the formulam - dist[x ^ ((1 << m) - 1)]
. Here,((1 << m) - 1)
represents the mask with allm
bits set to 1, effectively complementing the numberx
.
- For each
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 EvaluatorExample Walkthrough
Let's consider a simple example to walk through the solution approach. Suppose we have nums = [1, 2]
and m = 2
.
-
Initialize Distance Array:
- We'll create a
dist
array of size2^2 = 4
, initialized to[-1, -1, -1, -1]
.
- We'll create a
-
Set Initial Distances:
- For each number in
nums
, set its distance to 0:nums[0] = 1
, sodist[1] = 0
resulting indist = [-1, 0, -1, -1]
.nums[1] = 2
, sodist[2] = 0
resulting indist = [-1, 0, 0, -1]
.
- For each number in
-
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
, gives1 ^ 1 = 0
, updatedist = [1, 0, 0, -1]
, add0
to a temporary queuet
.1 ^ 2
, gives1 ^ 2 = 3
, updatedist = [1, 0, 0, 1]
, add3
to the temporary queuet
.
- Flip each bit:
-
For x = 2 (from the queue):
- Flip each bit:
2 ^ 1
, gives2 ^ 1 = 3
, already handled.2 ^ 2
, gives2 ^ 2 = 0
, already handled.
- Flip each bit:
-
Update queue
q = [0, 3]
and incrementk = 2
.
-
-
-
Calculate Maximum Hamming Distances:
- Final step is to calculate the maximum Hamming distance for each element in
nums
:- For
x = 1
, computedist[1 ^ 3] = dist[2] = 0
. Maximum Hamming distance =m - dist[2] = 2 - 0 = 2
. - For
x = 2
, computedist[2 ^ 3] = dist[1] = 0
. Maximum Hamming distance =2 - 0 = 2
.
- For
- Final step is to calculate the maximum Hamming distance for each element in
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.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donβt Miss This!