Boyer Moore

Table of Contents

• 169. Majority Element (Easy)
• 229. Majority Element II (Medium)
• 287. Find the Duplicate Number (Medium)
• 1150. Check If a Number Is Majority Element in a Sorted Array (Easy) 👑
• 1157. Online Majority Element In Subarray (Hard)
• 495. Teemo Attacking (Easy)

169. Majority Element

• LeetCode | LeetCode CH (Easy)

• Tags: array, hash table, divide and conquer, sorting, counting

• Return the majority element in an array. The majority element is the element that appears more than n // 2 times.

num	count	res
2	1	2
2	2	2
1	1	2
1	0	2
1	1	1
2	0	1
2	1	2

169. Majority Element - Python Solution

from collections import defaultdict
from typing import List


# Hash Map
def majorityElementHashMap(nums: List[int]) -> int:
    n = len(nums)
    freq = defaultdict(int)

    for num in nums:
        freq[num] += 1
        if freq[num] > n // 2:
            return num


# Array - Boyer-Moore Voting Algorithm
def majorityElementArray(nums: List[int]) -> int:
    res = None
    count = 0

    for num in nums:
        if count == 0:
            res = num
        count += 1 if num == res else -1

    return res


# | Algorithm | Time Complexity | Space Complexity |
# |-----------|-----------------|------------------|
# | HashMap   | O(N)            | O(N)             |
# | Array     | O(N)            | O(1)             |
# |-----------|-----------------|------------------|


nums = [2, 2, 1, 1, 1, 2, 2]
print(majorityElementArray(nums))  # 2
print(majorityElementHashMap(nums))  # 2

229. Majority Element II

• LeetCode | LeetCode CH (Medium)

• Tags: array, hash table, sorting, counting

229. Majority Element II - Python Solution

from collections import Counter
from typing import List


# Hash Map
def majorityElementHash(nums: List[int]) -> List[int]:
    counts = Counter(nums)
    target = len(nums) // 3
    res = []

    for num in nums:
        if counts[num] > target and num not in res:
            res.append(num)

    return res


# Boyer-Moore
def majorityElementMoore(nums: List[int]) -> List[int]:
    if not nums:
        return []

    cdt1, cnt1 = None, 0
    cdt2, cnt2 = None, 0

    for num in nums:
        if num == cdt1:
            cnt1 += 1
        elif num == cdt2:
            cnt2 += 1
        elif cnt1 == 0:
            cdt1, cnt1 = num, 1
        elif cnt2 == 0:
            cdt2, cnt2 = num, 1
        else:
            cnt1 -= 1
            cnt2 -= 1

    return [n for n in (cdt1, cdt2) if nums.count(n) > len(nums) // 3]


nums = [3, 2, 3]
print(majorityElementHash(nums))  # [3]
print(majorityElementMoore(nums))  # [3]

287. Find the Duplicate Number

• LeetCode | LeetCode CH (Medium)

• Tags: array, two pointers, binary search, bit manipulation

• Find the duplicate number in an array containing n + 1 integers where each integer is between 1 and n inclusive.
• Floyd's Tortoise and Hare (Cycle Detection)
  • 1. Linked List Cycle
  • 1. Linked List Cycle II
• Time Complexity: O(n)
• Space Complexity: O(1)

Example: nums = [1, 3, 4, 2, 2]

0	1	2	3	4
1	3	4	2	2

graph LR
0((0)) --> 1((1))
1 --> 3((3))
2((2))--> 4((4))
3 --> 2
4 --> 2

287. Find the Duplicate Number - Python Solution

from typing import List


# Floyd Cycle Detection Algorithm
def findDuplicate(nums: List[int]) -> int:
    fast, slow = nums[0], nums[0]

    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow


nums = [1, 3, 4, 2, 2]
print(findDuplicate(nums))  # 2

1150. Check If a Number Is Majority Element in a Sorted Array

• LeetCode | LeetCode CH (Easy)

• Tags: array, binary search

1157. Online Majority Element In Subarray

• LeetCode | LeetCode CH (Hard)

• Tags: array, binary search, design, binary indexed tree, segment tree

495. Teemo Attacking

• LeetCode | LeetCode CH (Easy)

• Tags: array, simulation

Comments