# LeetCode 169. Majority Element - Solution in Ruby

·

## Problem

169. Majority Element

Given an array `nums` of size `n`, 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.

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

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`.

## 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.