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;
}

Like the blog? Subscribe for updates

Email Address

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