LeetCode 1938: Maximum Genetic Difference Query Solution

Master LeetCode problem 1938 (Maximum Genetic Difference Query), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1938. Maximum Genetic Difference Query

Hard

Array Hash Table Bit Manipulation Depth-First Search Trie

Problem Explanation

Explanation:

Algorithmic Idea:
1. Build a Trie data structure to represent the tree. Each node in the Trie will store the children nodes and their corresponding genetic values.
2. For each query, traverse the Trie starting from the node and find the maximum genetic difference by XORing the query value with the genetic values encountered along the path to the root.
Time Complexity: O(n + q), where n is the number of nodes and q is the number of queries.
Space Complexity: O(n) for storing the Trie structure.

Solution Code

class TrieNode {
    Map<Integer, TrieNode> children;
    
    public TrieNode() {
        children = new HashMap<>();
    }
}

class Solution {
    public int[] maxGeneticDifference(int[] parents, int[][] queries) {
        TrieNode root = new TrieNode();
        Map<Integer, List<Integer>> childrenMap = new HashMap<>();
        for (int i = 0; i < parents.length; i++) {
            childrenMap.putIfAbsent(parents[i], new ArrayList<>());
            childrenMap.get(parents[i]).add(i);
        }
        
        for (int i = 0; i < queries.length; i++) {
            int node = queries[i][0];
            int val = queries[i][1];
            TrieNode curr = root;
            int maxDiff = 0;
            while (node != -1) {
                int parentVal = node;
                for (int bit = 17; bit >= 0; bit--) {
                    int mask = 1 << bit;
                    int childVal = (val & mask) == 0 ? 1 : 0;
                    childVal ^= 1;
                    if (curr.children.containsKey(childVal)) {
                        maxDiff |= mask;
                        curr = curr.children.get(childVal);
                    } else {
                        curr = curr.children.get(childVal ^ 1);
                    }
                }
                node = parents[node];
            }
            queries[i][1] = maxDiff;
        }
        
        return Arrays.stream(queries).mapToInt(arr -> arr[1]).toArray();
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1938 (Maximum Genetic Difference Query)?

This page provides optimized solutions for LeetCode problem 1938 (Maximum Genetic Difference Query) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1938 (Maximum Genetic Difference Query)?

The time complexity for LeetCode 1938 (Maximum Genetic Difference Query) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1938 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1938 in Java, C++, or Python.

Back to LeetCode Solutions