Find minimum and most frequent number efficiently
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an unsorted integer array, write functions to:
(a) find the minimum value; and
(b) find any value that occurs most frequently (if multiple values tie for highest frequency, return any one). Provide a straightforward baseline, then analyze its time and space complexity. Follow-up: Reduce running time by trading additional memory (e.g., using auxiliary data structures); describe the trade-offs and implement the improved version.
Quick Answer: Find minimum and most frequent number efficiently evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Given an unsorted integer array `nums`, return a pair `(minValue, mostFrequentValue)` where:
- `minValue` is the smallest value in the array.
- `mostFrequentValue` is a value that occurs most frequently. If multiple values tie for the highest frequency, return the one that first reaches the running maximum count while scanning left to right (for an all-distinct array this is simply the first element).
If the array is empty, return `(None, None)` (in statically typed languages, return a representation of "no value", e.g. an empty result — see templates; tests use non-empty arrays for those).
This is the time/space trade-off variant: instead of an O(n^2) baseline that recounts each value, use a single pass with a hash map of counts (O(n) time, O(n) extra space) while simultaneously tracking the minimum.
Constraints
- 1 <= nums.length <= 10^5 (an empty array returns (None, None))
- -10^9 <= nums[i] <= 10^9
- Values may be negative, zero, or duplicated.
- On a frequency tie, returning any one of the tied values is acceptable; the reference returns the first to reach the running max count.
Examples
Input: ([4, 1, 2, 2, 3, 1, 1],)
Expected Output: (1, 1)
Explanation: Minimum is 1. Frequencies: 1->3, 2->2, others 1. Most frequent is 1.
Input: ([5],)
Expected Output: (5, 5)
Explanation: Single element: it is both the minimum and the most frequent.
Hints
- The O(n^2) baseline recounts the frequency of every element by scanning the array each time. Can you count all frequencies in one pass instead?
- A hash map from value to count gives O(1) amortized counting. Build it while you also track the running minimum so you only traverse the array once.
- Update the best (most frequent) candidate inline: whenever an element's new count strictly exceeds the current best count, make it the new best. This naturally yields the first value to reach each new maximum.
- Trade-off: you spend O(n) extra memory for the count map to bring time from O(n^2) down to O(n).