cswork / libraryOpen practice workspace

Coding questions · ByteDance

Return the Most Frequent Integer with a Stable Tie-Breaker

Implement a frequency-based selection over a large integer array: return the most common value, using the numerically smallest value to break ties. Preserve the input and return the value itself rather than its count or position.

Given a nonempty integer array, return the value that appears most often. If several values have the same highest frequency, return the numerically smallest one.

Function Contract

def most_frequent_smallest(values: list[int]) -> int:
    ...

Constraints

  • 1 <= len(values) <= 200_000
  • -10**9 <= values[i] <= 10**9
  • Do not mutate the input.
  • Return the integer value, not its frequency or index.

Examples

values = [4, 1, 4, 2, 2]
result = 2

Both 2 and 4 occur twice, so the smaller value is returned.

values = [-1, -1, 3]
result = -1

Return the Most Frequent Integer with a Stable Tie-Breaker

Implement most_frequent_smallest(values). Return the most frequent value in the non-empty integer array. When several values tie for the highest frequency, return the numerically smallest one. Do not mutate the input.

Hints

  1. Count each value with a hash map.
  2. Compare candidates first by larger count and then by smaller numeric value.

Approach

Build a frequency map in one pass. Scan its entries while maintaining the value with the greatest count, replacing it on a larger count or on an equal count paired with a smaller value.

  • Time complexity: O(n) expected time.
  • Space complexity: O(u) space for u distinct integers.