Question 1
Given a non-empty array of integers, return the kth least common elements. If multiple elements are kh common,
return the answer in any order. You may assume k is always valid, 1<=k<=
number of unique elements.
Input
Output
nums = [1,1,1,2,2,3), k = 2
nums = [1,2,2,3,3,3), k= 2
nums
= [1,1,1,2,2,2,3,3] k= 2
[1, 2]
nums = [1], k=1
[1]
A.
Time Complexity:
Space Complexity:
B. Code
Answers
Answer:
Given a non-empty array of integers, return the kth least common elements. If multiple elements are kh common,
return the answer in any order. You may assume k is always valid, 1<=k<=
number of unique elements.
Input
Output
nums = [1,1,1,2,2,3), k = 2
nums = [1,2,2,3,3,3), k= 2
nums
= [1,1,1,2,2,2,3,3] k= 2
[1, 2]
nums = [1], k=1
[1]
A.
Time Complexity:
Space Complexity:
B. CodeGiven an array of size n and a number k, find all elements that appear more than n/k times
Given an array of size n, find all elements in array that appear more than n/k times. For example, if the input arrays is {3, 1, 2, 2, 1, 2, 3, 3} and k is 4, then the output should be [2, 3]. Note that size of array is 8 (or n = 8), so we need to find all elements that appear more than 2 (or 8/4) times. There are two elements that appear more than two times, 2 and 3. A simple method is to pick all elements one by one. For every picked element, count its occurrences by traversing the array, if count becomes more than n/k, then print the element. Time Complexity of this method would be O(n2).
A better solution is to use sorting. First, sort all elements using a O(nLogn) algorithm. Once the array is sorted, we can find all required elements in a linear scan of array. So overall time complexity of this method is O(nLogn) + O(n) which is O(nLogn).
Following is an interesting O(nk) solution:
We can solve the above problem in O(nk) time using O(k-1) extra space. Note that there can never be more than k-1 elements in output (Why?). There are mainly three steps in this algorithm.
1) Create a temporary array of size (k-1) to store elements and their counts (The output elements are going to be among these k-1 elements). Following is structure of temporary array elements.
struct eleCount {
int element;
int count;
};
struct eleCount temp[];
This step takes O(k) time.
2) Traverse through the input array and update temp[] (add/remove an element or increase/decrease count) for every traversed element. The array temp[] stores potential (k-1) candidates at every step. This step takes O(nk) time.
3) Iterate through final (k-1) potential candidates (stored in temp[]). or every element, check if it actually has count more than n/k. This step takes O(nk) time.
The main step is step 2, how to maintain (k-1) potential candidates at every point? The steps used in step 2 are like famous game: Tetris. We treat each number as a piece in Tetris, which falls down in our temporary array temp[]. Our task is to try to keep the same number stacked on the same column (count in temporary array is incremented).
Consider k = 4, n = 9
Given array: 3 1 2 2 2 1 4 3 3
i = 0
3 _ _
temp[] has one element, 3 with count 1
i = 1
3 1 _
temp[] has two elements, 3 and 1 with
counts 1 and 1 respectively
i = 2
3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 1 respectively.
i = 3
- - 2
3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 2 respectively.
i = 4
- - 2
- - 2
3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 3 respectively.
i = 5
- - 2
- 1 2
3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 2 and 3 respectively.
Now the question arises, what to do when temp[] is full and we see a new element – we remove the bottom row from stacks of elements, i.e., we decrease count of every element by 1 in temp[]. We ignore the current element.