Daily Coding Problem: Find the majority element in an array

My solution to a “Daily Coding Problem” that I received in my mail today.

Given a list of elements, find the majority element, which appears more than half the time (> floor(len(lst) / 2.0)).

You can assume that such element exists.

For example, given [1, 2, 1, 1, 3, 4, 0], return 1.

Here’s my solution in,

oneFiftyFive(arr: number[]):number {
  if (arr == null || arr == undefined) {
      return 0;
  }
  let half = Math.floor(arr.length / 2);
  //find max occurance
  let occurenceMap = new Map<number, number>();
  let maxOccurence = 0;
  for(let i = 0; i < arr.length; i++) {
    let n = arr[i];
    if(occurenceMap.has(n)) {
      let val = occurenceMap.get(n) + 1;
      //we get out the moment we find the max occurence
      //what if 2 numbers have the same frequency of occurence?
      if(val >= half) {
        maxOccurence = val;
        break;
      }
      occurenceMap.set(n, val);
    } else {
      occurenceMap.set(n, 1);
    }
  }
  return maxOccurence;
}

As usual, if you find any of my posts useful support me by buying or even trying one of my apps on the App Store.

https://mydaytodo.com/apps/

Also, if you can leave a review on the App Store or Google Play Store, that would help too.

Categories: ALGORITHMSTYPESCRIPT