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

Approach

Using the brute force approach, we first declare an object to store the frequency of each element. After saving the frequencies, we find the element with the largest count.

const obj = {}

nums.forEach(x => {
    if(obj.hasOwnProperty(x)){
        obj[x] = obj[x] + 1
    }else{
        obj[x] = 1
    }
})

const largetValue = Math.max(...Object.values(obj))

return Object.keys(obj).find(x => obj[x] === largetValue)

• Time Complexity: O(n) - Iterating through the array once to count frequencies: O(n), where n is the number of elements in the array nums.
• Auxiliary Space: O(n) - Storing frequencies in an object: O(n), as it requires additional space proportional to the number of distinct elements in the array.

Optimized Approach

First, we sort the array, and since we know there will be more than n/2 elements, after sorting, we return the element at index n/2. This is because there will be more than n/2 elements.

nums.sort()
return nums[Math.floor(nums.length/2)]

• Time Complexity: O(nlogn) - Sorting the array nums using an efficient sorting algorithm typically takes O(n log n) time complexity, where n is the number of elements in the array.
• Auxiliary Space: O(1) - Sorting algorithms like quicksort or mergesort often use O(log n) additional space for recursion or iteration overhead. However, in this case, since you're using the .sort() method, which sorts in-place, the space complexity is O(1) since it doesn't require additional space proportional to the input size.