2023-10-05 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge
|

Today I have done leetcode's October LeetCoding Challenge with cpp.

October LeetCoding Challenge 5

Description

Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

 

Example 1:

Input: nums = [3,2,3]
Output: [3]

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

Input: nums = [1,2]
Output: [1,2]

 

Constraints:

  • 1 <= nums.length <= 5 * 104
  • -109 <= nums[i] <= 109

 

Follow up: Could you solve the problem in linear time and in O(1) space?

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
public:
  vector<int> majorityElement(vector<int>& nums) {
    int elements[2];
    int count[2] = {};
    for(auto c : nums) {
      if(c == elements[0]) {
        count[0] += 1;
      } else if(c == elements[1]) {
        count[1] += 1;
      } else if(!count[0]) {
        elements[0] = c;
        count[0] = 1;
      } else if(!count[1]) {
        elements[1] = c;
        count[1] = 1;
      } else {
        count[0] -= 1;
        count[1] -= 1;
      }
    }
    vector<int> answer;
    for(auto candidate : elements) {
      int count = 0;
      for(auto i : nums) {
        count += i == candidate;
      }
      if(count * 3 > nums.size()) {
        answer.push_back(candidate);
      }
    }
    return answer;
  }
};

// Accepted
// 87/87 cases passed (10 ms)
// Your runtime beats 57.9 % of cpp submissions
// Your memory usage beats 9.77 % of cpp submissions (16.5 MB)
Algorithm