3.48 Maximum Number of Repetitions

3.48.1 Problem Metadata

Platform: Firecode
Difficulty: Medium
URL: N/A
Tags:
Techniques: Counting, Array

3.48.2 Description

Given an array of integers where each value lies in [0, n-1], return the integer that appears most frequently. The algorithm must run in O(n) time and O(1) extra space.

3.48.3 Examples

Input: [3,1,2,2,3,4,4,4]
Output: 4

3.48.4 Constraints

1 <= n <= 10^5
Values are in [0, n-1]

3.48.5 Solution - In-place Counting

3.48.5.1 Walkthrough

Exploit the bounded value range by using the input array itself as a hash table. For each value a[i], increment a[a[i] % n] by n. After one pass, the count of value v equals a[v] / n. Track the index with the maximum total.

3.48.5.2 Analysis

Time Complexity: O(n)
Space Complexity: O(1)

3.48.5.3 Implementation Steps

Let k = n (or any value = n).
For each index i, add k to arr[arr[i] % n].
Scan the array to find the index with the largest value; that index is the answer.

3.48.5.4 Code - Java

public int getMaxRepetition(int[] nums) {
    int n = nums.length;
    int k = n;

    for (int i = 0; i < n; i++) {
        nums[nums[i] % n] += k;
    }

    int maxIdx = 0;
    for (int i = 1; i < n; i++) {
        if (nums[i] > nums[maxIdx]) {
            maxIdx = i;
        }
    }

    return maxIdx;
}