2024-02-12 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

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

February LeetCoding Challenge 12

Description

Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

 

Example 1:

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

Example 2:

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

 

Constraints:

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

 

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

Solution

class Solution {
public:
  int majorityElement(vector<int>& nums) {
    int answer = !nums.front();
    int count = 0;
    for(auto n : nums) {
      if(answer == n) {
        count += 1;
      } else {
        if(!count) {
          answer = n;
        } else {
          count -= 1;
        }
      }
    }
    return answer;
  }
};

// Accepted
// 50/50 cases passed (11 ms)
// Your runtime beats 83.7 % of cpp submissions
// Your memory usage beats 24.81 % of cpp submissions (22.1 MB)
Algorithm