Solution For Majority Element

The problem statement is as follows:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊n/2⌋ times.

You may assume that the array is non-empty and the majority element always exists in the array.

To solve this problem, we will use a hash table to keep track of the count of each element. We will iterate through the array and update the count of each element in the hash table. Once the iteration is complete, we will iterate through the hash table and check if the count of any element is greater than ⌊n/2⌋. If we find such an element, we return it as the majority element.

Here is the detailed solution:

1. Create an empty hash table to keep track of the count of each element.

2. Iterate through the array and update the count of each element in the hash table.

3. If the element is already in the hash table, increment its count by 1.

4. If the element is not in the hash table, add it to the hash table with a count of 1.

5. Iterate through the hash table and check if the count of any element is greater than ⌊n/2⌋.

6. If we find such an element, return it as the majority element.

7. If we don’t find such an element, the array does not have a majority element.

Here is the Python code implementing the above solution:

“`
def majorityElement(nums):
counts = {}
for num in nums:
if num in counts:
counts[num] += 1
else:
counts[num] = 1

for num, count in counts.items():
    if count > len(nums) // 2:
        return num

return None

“`

The time complexity of this solution is O(n) as we are iterating through the array and the hash table only once. The space complexity is also O(n) as we are using a hash table to store the count of each element.

Step by Step Implementation For Majority Element

public class Solution {
    public int majorityElement(int[] nums) {
        
        // create a map to store the number of times each element appears in the array
        Map map = new HashMap<>();
        
        // iterate through the array and update the map
        for(int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        
        // iterate through the map and return the element that appears the most
        for(int i : map.keySet()) {
            if(map.get(i) > nums.length / 2) {
                return i;
            }
        }
        
        // if no majority element is found, return -1
        return -1;
    }
}

def majorityElement(nums):
    
    # create a dictionary to store the count of each element
    dict = {}
    
    # iterate over the list
    for i in nums:
        
        # if the element is not in the dictionary, add it with a count of 1
        if i not in dict:
            dict[i] = 1
            
        # if the element is in the dictionary, increment the count by 1
        else:
            dict[i] += 1
            
    # iterate over the dictionary to find the element with the majority count
    for key, value in dict.items():
        
        # if the count is greater than or equal to n/2, where n is the length of the list, return the element
        if value >= len(nums)/2:
            return key

var majorityElement = function(nums) {
    
    // create a map to store the number of times an element appears in the array
    let map = {};
    
    // iterate through the array and store the number of times each element appears in the map
    for (let i = 0; i < nums.length; i++) {
        if (map[nums[i]]) {
            map[nums[i]]++;
        } else {
            map[nums[i]] = 1;
        }
    }
    
    // iterate through the map and return the element that appears the most
    for (let key in map) {
        if (map[key] > nums.length / 2) {
            return key;
        }
    }
    
};

int majorityElement(vector& nums) {
        int majority_index = 0, count = 1;
        for(int i = 1; i < nums.size(); i++) {
            if(nums[majority_index] == nums[i])
                count++;
            else
                count--;
            if(count == 0) {
                majority_index = i;
                count = 1;
            }
        }
        return nums[majority_index];
    }

public class Solution {
    public int MajorityElement(int[] nums) {
        //Create a dictionary to store the number of times each element appears in the array
        Dictionary dict = new Dictionary();
        
        //Iterate through the array and update the dictionary accordingly
        for(int i = 0; i < nums.Length; i++){
            if(dict.ContainsKey(nums[i])){
                dict[nums[i]]++;
            }
            else{
                dict[nums[i]] = 1;
            }
        }
        
        //Find the key with the maximum value
        int majorityElement = 0;
        foreach(var key in dict.Keys){
            if(dict[key] > dict[majorityElement]){
                majorityElement = key;
            }
        }
        
        return majorityElement;
    }
}