Class Mode

java.lang.Object
topics.divideconquer.mode.Mode
public class Mode extends Object

Mode Calculation

Finds the statistical mode (the most frequently occurring element) in an array, alongside its frequency. Demonstrates how preprocessing data (sorting) can optimize a quadratic problem into a linearithmic $O(N \log N)$ one.

Author:
vicegd

  • Constructor Details

    • Mode

      public Mode()

  • Method Details

    • calculateModeNaive

      public int[] calculateModeNaive(int[] v)

      1. Naive Iterative Approach

      Checks every single element against every other element to count frequencies.

      • Time Complexity: $O(N^2)$ - Quadratic.
      • Space Complexity: $O(1)$ - Constant.
      Parameters:
      v - Array of integers.
      Returns:
      An integer array of size 2 where: index 0 = Mode Value, index 1 = Number of Repetitions.

    • calculateModeSorting

      public int[] calculateModeSorting(int[] v)

      2. Sorting Approach (Divide invalid input: '&' Conquer)

      Leverages Quicksort to group identical elements together. Once sorted, finding the mode only requires a single linear pass $O(N)$ counting contiguous identical values.

      • Time Complexity: $O(N \log N)$ - Bound by the Quicksort step.
      • Space Complexity: $O(N)$ - To clone the array and prevent side-effects.
      Parameters:
      v - Array of integers.
      Returns:
      An integer array of size 2 where: index 0 = Mode Value, index 1 = Number of Repetitions.