Class MajoritarianElement

java.lang.Object
topics.divideconquer.majoritarian.MajoritarianElement
public class MajoritarianElement extends Object

Majoritarian Element

Evaluates whether an array contains a "Majoritarian Element" (an element that appears strictly more than N/2 times). This class demonstrates the evolution of algorithmic efficiency from a brute-force approach to a linear Divide invalid input: '&' Conquer approach.

Author:
vicegd

  • Constructor Details

    • MajoritarianElement

      public MajoritarianElement()

  • Method Details

    • hasMajorityNaive

      public boolean hasMajorityNaive(int[] v)

      1. Naive Iterative Approach

      Checks every single element and counts its total occurrences across the entire array.

      • Time Complexity: O(N²) - Quadratic
      • Space Complexity: O(1) - Constant
      Parameters:
      v - Array of elements.
      Returns:
      True if a majoritarian element exists, false otherwise.

    • hasMajoritySorting

      public boolean hasMajoritySorting(int[] v)

      2. Sorting Approach

      Sorts the array first. If a majoritarian element exists, it must occupy the mathematical center of the sorted array (index N/2). We then just count how many times this central element appears.

      • Time Complexity: O(N log N) - Bound by the sorting step
      • Space Complexity: O(N) - Defensive copy to avoid mutating the input
      Parameters:
      v - Array of elements.
      Returns:
      True if a majoritarian element exists, false otherwise.

    • hasMajorityDivideAndConquer

      public boolean hasMajorityDivideAndConquer(int[] v)

      3. Divide invalid input: '&' Conquer Approach (Tournament/Pairing Method)

      Recursively eliminates pairs of elements. If adjacent elements are identical, one is kept for the next round. If they differ, both are discarded. This dramatically reduces the search space linearly.

      • Time Complexity: O(N) - Linear
      • Space Complexity: O(N) - Array cloning and call stack
      Parameters:
      v - Array of elements.
      Returns:
      True if a majoritarian element exists, false otherwise.