Majority Element solution using TypeScript

Below is my TypeScript solution to the LeetCode "Majority Element" question.

Algorithm: The majority element in the array can be found by iterating over each element in the array. For each element:

  • Store the element in a Hash Map, where it's value represents the number of times that element has occurred in the array so far.
  • Check if the current element has occurred more than any other element so far.
    • If so, update the majority element to be the current value.
    • Otherwise, keep iterating.
  • Once an element has been found that represents more than half the elements in the array, stop iterating and return the element.

Time Complexity: Because the majority element represents a value that makes up more than half of the values in the array, we only need to iterate over the array at most, one time. This makes the time complexity O(n) where n represents the number of elements in the array.

Space Complexity: Because this approach will store, at most, each unique element of the array in a hash map, the space complexity is O(n) where n represents the number of elements in the array.

 * Majority Element
 * Given an array of size n, find the majority 
 * element. The majority element is the element 
 * that appears more than n/2 times.
 * Time Complexity: O(n)
 * Space Complexity: O(n);
 * majorityElement([2,2,1,1,1,2,2]) // 2
 * majorityElement([3,2,3]) // 3
 * majorityElement([1]) // 1
function majorityElement(nums: number[]): number {
    const half = Math.floor(nums.length / 2);
    const map = new Map();
    let pointer = 0;
    let majority = {
        element: -1,
        count: -1
    // iterate array until a majority element is found
    while(majority.count <= half) {
        const current = {
            element: nums[pointer],
            count: (map.get(nums[pointer]) || 0) + 1
        map.set(current.element, current.count);
        majority = majority.count < current.count
            ? current
            : majority
        pointer += 1;
    return majority.element;

more LeetCode posts