# A O(nlogn) solution in Java

• Most solutions are O(n^2). This is a O(nlogn) way to solve this issue by using Heap.
Not very fast in practice though.

``````public class Solution {
public int maxProduct(String[] words) {
int n = words.length;
Arrays.sort(words, (a, b)->b.length() - a.length());
Queue<int[]> queue = new PriorityQueue<>((a, b)->words[b[0]].length()*words[b[1]].length() -  words[a[0]].length()*words[a[1]].length());
for(int i=0; i<n; i++)
queue.offer(new int[]{i, 0});
while(!queue.isEmpty()){
int[] curr = queue.poll();
int i = curr[0];
int j = curr[1];
if(i != j && (getCode(words[i]) & getCode(words[j])) == 0)
return words[i].length() * words[j].length();
if(j < n-1)
queue.offer(new int[]{i, j+1});
}
return 0;
}

private int getCode(String str){
int r = 0;
for(int i=0; i<str.length(); i++)
r |= 1<<(str.charAt(i) - 'a');
return r;
}
}
``````

• This isn't O(nlogn). Not even O(n^2). For example for `words = ["a"] * n` you go through n2 pairs and each costs O(logn) for the `queue.poll()`.

• @StefanPochmann Thanks for point it out. Good example!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.