leetcode-javascript/solutions/0229-majority-element-ii.js at development · Anuj9826/leetcode-javascript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Majority Element II
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
var majorityElement = function (nums) {
  if (nums.length === 0) {
    return [];
  }

  let firstCandidate = 0;
  let secondCandidate = 0;
  let firstCount = 0;
  let secondCount = 0;

  for (const currentNumber of nums) {
    if (currentNumber === firstCandidate) {
      firstCount++;
    } else if (currentNumber === secondCandidate) {
      secondCount++;
    } else if (firstCount === 0) {
      firstCandidate = currentNumber;
      firstCount = 1;
    } else if (secondCount === 0) {
      secondCandidate = currentNumber;
      secondCount = 1;
    } else {
      firstCount--;
      secondCount--;
    }
  }

  let verifiedCountOne = 0;
  let verifiedCountTwo = 0;

  for (const elementValue of nums) {
    if (elementValue === firstCandidate) {
      verifiedCountOne++;
    } else if (elementValue === secondCandidate) {
      verifiedCountTwo++;
    }
  }

  const thresholdFrequency = nums.length / 3;
  const resultList = [];

  if (verifiedCountOne > thresholdFrequency) {
    resultList.push(firstCandidate);
  }

  if (
    verifiedCountTwo > thresholdFrequency &&
    firstCandidate !== secondCandidate
  ) {
    resultList.push(secondCandidate);
  }

  return resultList;
};