element – programmingpuzzles

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Note:

You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

[code lang="java"]
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        
    }
}
[code]

Idea – 1

We use a hash map to save the frequency of each element. Next we put the keys in a min heap of size k (whenever the heap becomes bigger than k we throw away top which is the least frequent element). At the end we have k most frequent elements in the heap. Time complexity is $O(n\cdot lg{k})$ and space complexity is $O(n)$ .

[code lang="java"]
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> ans = new ArrayList<>();
        int n = nums.length;
        
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int x : nums)
        {
            map.put( x, map.getOrDefault(x, 0)+1 );
        }
        
        PriorityQueue<Integer> minq = new PriorityQueue<>( (a, b) -> ( map.get(a)-map.get(b) ) );
        for(int key : map.keySet())
        {
            minq.offer(key);
            if(minq.size() > k)
            {
                minq.poll();
            }
        }
        
        while(!minq.isEmpty())
        {
            ans.add(minq.poll());
        }
        
        return ans;
    }
}
[code]

Runtime: 42 ms, faster than 42.71% of Java online submissions for Top K Frequent Elements.Memory Usage: 39.1 MB, less than 65.70% of Java online submissions for Top K Frequent Elements.

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

[code lang="java"]
class Solution {
    public int findKthLargest(int[] nums, int k) {
        
    }
}
[code]

Idea – 1

Sort in non-increasing order and return the k-th element. Time and space complexity are that of a comparison based sorting. With traditional mergesort time is $O(n\lg{n})$ ans space is be $O(n)$ . With quicksort average time is $O(n\lg{n})$ and average space is $O(lg{n})$ . With heapsort time is $O(n\lg{n})$ and space is $O(1)$ .

[code lang="java"]

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        
        Integer[] boxedArray = new Integer[n];
        for(int i = 0; i < n; ++i)
        {
            boxedArray[i] = nums[i];
        }
        
        Arrays.sort(boxedArray, (a, b) -> (b - a));
        
        return boxedArray[k-1];
    }
}
[code]

Runtime: 41 ms, faster than 11.26% of Java online submissions for Kth Largest Element in an Array.Memory Usage: 38 MB, less than 62.44% of Java online submissions for Kth Largest Element in an Array.

Idea – 2

We use quickselect: repeatedly partition the array around a random pivot and go right or left based on the rank of the pivot. Average time $O(n)$ and average space $O(\lg{n})$ . Worst case time is $O(n^2)$ and worst case space is $O(n)$ .

[code lang="java"]
class Solution {
    
    private static final Random rng = new Random(System.currentTimeMillis() % Integer.MAX_VALUE);
    
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        
        return partition(nums, 0, n-1, k);
    }
    
    private void swap(int[] A, int i, int j)
    {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
    
    private int partition(int[] A, int lo, int hi, int k)
    {
        int z = lo+rng.nextInt(hi-lo+1);
        int pivot = A[z];
        int i = lo-1, x = lo, j = hi;
        while(x <= j)
        {
            if(A[x] < pivot)
            {
                swap(A, ++i, x++);
            }
            else if(A[x] > pivot)
            {
                swap(A, x, j--);
            }
            else
            {
                ++x;
            }
        }
        
        // (i+1) is where pivot is right now
        int rank = A.length-(i+1);
        
        if(rank==k)
        {
            return pivot;
        }
        else if(rank < k)
        {
            return partition(A, lo, i, k);
        }
        else
        {
            return partition(A, i+2, hi, k);
        }
    }
}
[code]

Runtime: 1 ms, faster than 99.81% of Java online submissions for Kth Largest Element in an Array.Memory Usage: 35.6 MB, less than 97.57% of Java online submissions for Kth Largest Element in an Array.

programmingpuzzles

Tag: element

LeetCode – 347 : Top K Frequent Elements

Idea – 1

LeetCode – 215 : Kth Largest Element in an Array

Idea – 1

Idea – 2