Problem
Given an array
numsof sizen, return the majority element.The majority element is the element that appears more than
⌊n / 2⌋times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
Explanation
The problem is asking you to find the majority element in an array, which is the element that appears more than ⌊n / 2⌋ times, where n is the size of the array. You can assume that the majority element always exists in the array.
Input
You are given an array nums of size n. The array nums contains elements of any data type, such as integers, strings, or any other objects.
Majority element
The majority element is the element that appears more than ⌊n / 2⌋ times, where n is the size of the array. "⌊n / 2⌋" denotes the floor division, which means you take the integer part of n divided by 2.
For example, if the array has 9 elements (n = 9), then the majority element must appear more than ⌊9 / 2⌋ = 4 times in the array.
Task
Your task is to find and return the majority element from the given array nums.
Assumptions
The problem statement explicitly states that you may assume the majority element always exists in the array.
This means you don't need to handle the case where there might be no majority element or where multiple elements have the same frequency.
Example
Take the following nums as an example:
nums = [9, 2, 2, 1, 8, 2, 1, 2, 2]
In the previous example, the length/size of nums is 9. So, n is equal to 9, which means that the majority element must appear more than 4 times, since 9/2 is equal to 4, considering only the integer part.
In the previous array, the majority element is the number 2, since it appears 5 times.
Initial blueprint
# @param {Integer[]} nums
# @return {Integer}
def majority_element(nums)
end
Solution steps
In case you just want to jump to the GitHub code, click here.
Tests are available here.
Input
The method majority_element takes an array nums as input. This array contains elements of any data type, such as numbers or strings.
# @param {Integer[]} nums
# @return {Integer}
def majority_element(nums)
end
nums is already provided by LeetCode, so, we don't need to do anything so far.
Count occurrences
The first step inside the method is to count the occurrences of each element in the input array nums.
To do this, we create a new variable occurrences and use the tally method on the nums array.
The tally method counts the occurrences of each element and returns a hash where the keys are the elements, and the values are their corresponding counts.
Let's consider the following nums array:
nums = [3, 1, 9, 1, 2, 1]
The tally method is going to return a brand new hash, considering the array elements as its keys, and their occurrences as its values.
nums.tally
=> {3=>1, 1=>3, 9=>1, 2=>1}
So far, this is what we have:
# @param {Integer[]} nums
# @return {Integer}
def majority_element(nums)
occurrences = nums.tally
end
Find the maximum count value
Next, we find the element with the highest count in the occurrences hash. We do this by using the values.max method, which returns the maximum count from the hash values.
This means we get the count of the element that appears the most in the input array.
By using the values.max method, we would get the following result:
nums
=> [3, 1, 9, 1, 2, 1]
2.7.2 :028 > occurrences
=> {3=>1, 1=>3, 9=>1, 2=>1}
2.7.2 :029 > occurrences.values.max
=> 3
So far, this is our solution:
occurrences = nums.tally
occurrences.values.max
Retrieve the majority element
Now that we have the maximum count of an element, we want to find the element itself.
To do this, we use the key method on the occurrences hash, passing the maximum count as an argument.
The key method returns the element (key) corresponding to the given value (count) in the hash.
nums
=> [3, 1, 9, 1, 2, 1]
2.7.2 :028 > occurrences
=> {3=>1, 1=>3, 9=>1, 2=>1}
2.7.2 :029 > occurrences.values.max
=> 3
2.7.2 :030 > occurrences.key(occurrences.values.max)
=> 1
So far, this is what we have:
# @param {Integer[]} nums
# @return {Integer}
def majority_element(nums)
occurrences = nums.tally
occurrences.key(occurrences.values.max)
end
Return the majority element
# @param {Integer[]} nums
# @return {Integer}
def majority_element(nums)
occurrences = nums.tally
return occurrences.key(occurrences.values.max)
end
Final solution
# @param {Integer[]} nums
# @return {Integer}
def majority_element(nums)
occurrences = nums.tally
occurrences.key(occurrences.values.max)
end
Tests
# spec/majority_element_spec.rb
subject { majority_element(nums) }
context 'when the array nums is sorted' do
let(:nums) {[1, 2, 2, 2, 3, 4]}
it 'returns the majority element' do
is_expected.to eq(2)
end
end
context 'when the array nums is unsorted' do
let(:nums) {[2, 2, 1, 2, 4, 3]}
it 'returns the majority element' do
expect(subject).to eq(2)
end
end
context 'when the array nums is made of negative numbers' do
let(:nums) {[-2, -9, -2, -1, -2, -3]}
it 'returns the majority element' do
expect(subject).to eq(-2)
end
end
The complete rspec test code can be found here.
Algorithm efficiency
Algorithm Efficiency Algorithm efficiency is essential for achieving faster execution, scalability, optimal resource utilization, energy efficiency, scalable system design, and gaining a competitive advantage in specific domains.
An algorithm is considered efficient when it has both low time complexity and low space complexity, allowing it to execute quickly and use minimal memory resources for various input sizes. Achieving efficiency is essential in developing high-performance software applications and systems.
Time complexity
def majority_element(nums)
occurrences = nums.tally
occurrences.key(occurrences.values.max)
end
The tally method in Ruby iterates over the input array nums to count the occurrences of each element, resulting in a hash where the keys are the elements and the values are their corresponding counts.
The time complexity of the tally method is O(n), where n is the size of the input array.
After obtaining the hash occurrences, the code uses the values.max method to find the maximum count, which involves iterating over all the values in the hash. This operation also has a time complexity of O(n), as it needs to examine each value to determine the maximum.
Finally, the key method is called on the hash occurrences to retrieve the element corresponding to the maximum count. This operation has an average time complexity called of O(1), known as linear time, because hash lookup operations are typically very fast, regardless of the size of the hash.
In conclusion, the overall time complexity of the majority_element method is linear time, known as O(n), where n is the size of the input array.
This is because the most time-consuming operations, namely counting occurrences and finding the maximum count, have linear time complexities concerning the size of the input.
Space time complexity
The space complexity of the given majority_element method is dependent on the additional data structures used and the amount of memory required to store the intermediate results.
In the given method, the primary data structure that affects space complexity is the occurrences hash. The tally method creates a hash where the keys are the elements from the input array nums, and the values are their corresponding counts.
The space required to store this hash depends on the unique elements in nums and the counts associated with them. If we assume that the number of unique elements in nums is m, then the space complexity of storing the occurrences hash would be O(m). This is because the hash needs to store a key-value pair for each unique element.
In addition to the ` occurrences` hash, the space complexity also includes the memory required to store any intermediate variables used within the method.
However, since the method does not use any additional significant data structures, the space complexity contribution from these variables can be considered constant or negligible.
Therefore, the overall space complexity of the majority_element method is O(m), where m represents the number of unique elements in the input array nums.
Celebrate
Let's become friends
Final thoughts
I hope this article helped you. Let me know if you have any questions. Your thoughts, suggestions and corrections are more than welcome.
By the way, feel free to drop your suggestions on new blog articles.
Hope to see you next time.