Comment by viccis

Yeah it just depends on whether your interviewer considers that "solved". To test this out, I wrote a one liner in Python (after imports) that solves it with a hashmap (under the hood for Counter, which uses a heap queue to find the most common one):

return Counter(nums).most_common(1)[0][0]

And that's 50th percentile for runtime and memory usage. Doing it with another one liner that's 87% percentile for time because it uses builtin Python sorting but is 20th percentile for memory:

return sorted(nums)[len(nums) // 2]

But the interviewer might be looking for the best approach, which beats "100%" of other solutions in runtime per Leetcode's analysis:

  m, c = -1, 0
  for x in nums:
      if not c:
          m = x
          c = 1
      elif m == x:
          c += 1
      else:
          c -= 1
  return m

If I were interviewing, I'd be happy with any of these except maybe the sorted() one, as it's only faster because of the native code doing the sort, which doesn't change that it's O(n log n) time and O(n) space. But I've had interviews where I gave answers that were "correct" to the assumptions and constraints I outlined but they didn't like them because they weren't the one from their rubric. I still remember a Google interview, in which we're supposed to "design to scale to big data", in which they wanted some fiddly array manipulation algorithm like this. I gave one that was O(n log n) but could be done in place with O(1) memory, and the interviewer said it was "incorrect" in favor of a much simpler O(n) one using dicts in Python that was O(n) memory. Had the interviewer specified O(n) memory was fine (not great for "big data" but ok) I would have given him the one liner that did it with dicts lol

I guess my point is that interviewers should be flexible and view it as a dialogue rather than asking for the "right answer". I much prefer "identify the bug in this self contained code snippet and fix it" type problems that can be completed in <15-30 minutes personally, but Leetcode ones can be fine if you choose the right problems for the job.