A O(nlogn) solution in Java


  • 1
    S

    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;
        }
    }
    

  • 1

    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().


  • 0
    S

    @StefanPochmann Thanks for point it out. Good example!


Log in to reply
 

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