grid47 Exploring patterns and algorithms
Oct 15, 2024
7 min read
Solution to LeetCode 229: Majority Element II Problem
Given an integer array, find all elements that appear more than ⌊n/3⌋ times, where n is the length of the array. Your task is to return a list of all such elements.
Problem
Approach
Steps
Complexity
Input: The input consists of an array `nums` of integers, where the length of the array is between 1 and 5 * 10^4. The elements in the array can range from -10^9 to 10^9.
Example: Input: nums = [1, 1, 1, 2, 3, 3]
Constraints:
• 1 <= nums.length <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9
Output: The output should be a list of integers representing the elements that appear more than ⌊n/3⌋ times in the input array.
Example: Output: [1]
Constraints:
Goal: The goal is to identify elements that appear more than ⌊n/3⌋ times in the array efficiently.
Steps:
• Initialize counters and candidate variables for the two most frequent elements.
• Traverse the array to count occurrences and determine the two most frequent elements.
• Perform a second pass through the array to confirm the exact counts of the candidates.
• Return the elements that meet the frequency condition.
Goal: The solution needs to be efficient in terms of time complexity, with a constraint of linear time and constant space.
Steps:
Assumptions:
• The input array will always have at least one element.
• The array length will not exceed 50,000 elements.
• Input: Input: nums = [1, 1, 1, 2, 3, 3]
• Explanation: The length of the array is 6, and ⌊6/3⌋ = 2. The number 1 appears three times, which is greater than 2, so it is included in the result. The number 3 appears twice, which is equal to ⌊6/3⌋, so it is not included in the result.
• Input: Input: nums = [4, 4, 4, 5, 5, 6, 7]
• Explanation: For this example, ⌊7/3⌋ = 2. The number 4 appears three times, which is greater than 2, so it is included. The number 5 appears twice, which equals ⌊7/3⌋, and is not included. The numbers 6 and 7 each appear once, so they are not included.
Approach: We can use a two-pass approach to solve this problem in linear time and constant space.
Observations:
• We need to find elements that appear more than ⌊n/3⌋ times. This suggests we may need to check the counts of the most frequent elements.
• A simple counting approach can be used to identify potential candidates. After identifying candidates, we need to count their actual occurrences in the array.
Steps:
• Initialize two variables for potential candidates and their respective counts.
• Traverse the array to count the frequency of elements and determine the two most frequent candidates.
• In a second pass, count the exact occurrences of these candidates in the array.
• Return the elements whose counts exceed ⌊n/3⌋.
Empty Inputs:
• An empty input is not allowed according to the constraints.
Large Inputs:
• The solution must efficiently handle arrays of up to 50,000 elements.
Special Values:
• If all elements are the same, that element will always appear more than ⌊n/3⌋ times.
Constraints:
• The solution must work within linear time and constant space.
vector<int> majorityElement(vector<int>& nums) {
std::vector<int> result;
int n = nums.size();
if (n ==0) return result;
int cnt1 =0, cnt2 =0;
int cnd1 =0, cnd2 =0;
for (int i =0; i < n; i++) {
int val = nums[i];
if (val == cnd1) cnt1++;
elseif (val == cnd2) cnt2++;
elseif (cnt1 ==0) { cnt1 =1; cnd1 = val; }
elseif (cnt2 ==0) { cnt2 =1; cnd2 = val; }
else { cnt1--; cnt2--; }
}
cnt1 =0;
cnt2 =0;
for (int i =0; i < n; i++) {
int val = nums[i];
if (val == cnd1) cnt1++;
elseif (val == cnd2) cnt2++;
}
n = n /3;
if (cnt1 > n) result.push_back(cnd1);
if (cnt2 > n) result.push_back(cnd2);
return result;
}
1 : Function Definition
vector<int> majorityElement(vector<int>& nums) {
Defines the function `majorityElement` which takes a reference to a vector of integers and returns a vector of integers that appear more than n/3 times in the array.
2 : Variable Initialization
std::vector<int> result;
Initializes an empty vector `result` to store the elements that appear more than n/3 times.
3 : Variable Initialization
int n = nums.size();
Stores the size of the input vector `nums` in the variable `n`.
4 : Edge Case Check
if (n ==0) return result;
Checks if the input array is empty and returns an empty result if true.
5 : Variable Initialization
int cnt1 =0, cnt2 =0;
Initializes two counters `cnt1` and `cnt2` for tracking the occurrences of two candidate elements.
6 : Variable Initialization
int cnd1 =0, cnd2 =0;
Initializes two candidate elements `cnd1` and `cnd2` to track the most frequent elements.
7 : Main Loop
for (int i =0; i < n; i++) {
Starts a loop to iterate over all elements of the array.
8 : Element Check
int val = nums[i];
Assigns the current element of the array to the variable `val`.
9 : Voting Logic
if (val == cnd1) cnt1++;
If the current element equals the first candidate `cnd1`, increment `cnt1`.
10 : Voting Logic
elseif (val == cnd2) cnt2++;
If the current element equals the second candidate `cnd2`, increment `cnt2`.
11 : Candidate Assignment
elseif (cnt1 ==0) { cnt1 =1; cnd1 = val; }
If `cnt1` is 0, assign the current element to `cnd1` and set `cnt1` to 1.
12 : Candidate Assignment
elseif (cnt2 ==0) { cnt2 =1; cnd2 = val; }
If `cnt2` is 0, assign the current element to `cnd2` and set `cnt2` to 1.
13 : Voting Logic
else { cnt1--; cnt2--; }
If neither candidate matches, decrement both `cnt1` and `cnt2`.
14 : Recounting Phase
cnt1 =0;
Resets the count of `cnd1` for a second pass through the array.
15 : Recounting Phase
cnt2 =0;
Resets the count of `cnd2` for a second pass through the array.
16 : Recounting Phase
for (int i =0; i < n; i++) {
Starts a second loop to recount occurrences of the candidates.
17 : Element Count
int val = nums[i];
Assigns the current element of the array to the variable `val` again.
18 : Element Count
if (val == cnd1) cnt1++;
Increments the count for `cnd1` if the current element matches `cnd1`.
19 : Element Count
elseif (val == cnd2) cnt2++;
Increments the count for `cnd2` if the current element matches `cnd2`.
20 : Final Check
n = n /3;
Calculates n/3 to determine the threshold for a majority element.
21 : Result Construction
if (cnt1 > n) result.push_back(cnd1);
If `cnd1` appears more than n/3 times, add it to the result vector.
22 : Result Construction
if (cnt2 > n) result.push_back(cnd2);
If `cnd2` appears more than n/3 times, add it to the result vector.
23 : Return Result
return result;
Returns the vector `result`, which contains the majority elements.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we perform two passes over the array (one for candidate identification and one for count verification).
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) since we only store a constant number of variables to track the two potential candidates.
