Quick Overview

A short coding question: given a list of integers with repeated values, return each distinct value together with the number of times it appears, sorted by value. It tests frequency counting, handling negative numbers, and producing a deterministic output order.

Count Occurrences of Each Value in an Integer List, Sorted by Value

Company: Apple

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Given a list of integers that may contain repeated values, count how many times each distinct value appears. The report describes the task only as counting the occurrences of each number in a list with duplicates; this version fixes the output format so that the answer is unique. ### Function Signature ```python def count_occurrences(nums: list[int]) -> list[list[int]]: ``` ### Rules - Return one pair `[value, count]` for every distinct value in `nums`, where `count` is the number of times `value` appears in `nums`. - Sort the pairs by `value` in ascending numeric order. - Each distinct value appears in exactly one pair, so the counts add up to `len(nums)`. ### Constraints - `1 <= len(nums) <= 10^5` - `-10^9 <= nums[i] <= 10^9`; values may be negative, zero or repeated. - Every value and every count fits in a 32-bit signed integer. ### Examples **Example 1** ```text Input: nums = [3, 1, 3, 2, 1, 3] Output: [[1, 2], [2, 1], [3, 3]] ``` The value 1 appears twice, 2 once and 3 three times. **Example 2** ```text Input: nums = [-5, 0, -5, 7] Output: [[-5, 2], [0, 1], [7, 1]] ``` Negative values sort before zero. **Example 3** ```text Input: nums = [4, 4, 4, 4] Output: [[4, 4]] ``` A single distinct value produces a single pair.

Overview: A short coding question: given a list of integers with repeated values, return each distinct value together with the number of times it appears, sorted by value. It tests frequency counting, handling negative numbers, and producing a deterministic output order.

Read the full Apple Data Scientist interview experience this question came from

Given a list of integers `nums` that may contain repeated values, count how many times each distinct value appears. Return a list of pairs `[value, count]`, one pair for every distinct value in `nums`, where `count` is the number of times `value` appears in `nums`. Sort the pairs by `value` in ascending numeric order. Each distinct value appears in exactly one pair, so the counts add up to `len(nums)`. No value or count can exceed 2^31 - 1: every value and every count fits in a 32-bit signed integer. ### Constraints - `1 <= len(nums) <= 10^5` - `-10^9 <= nums[i] <= 10^9`; values may be negative, zero or repeated. - Every value and every count fits in a 32-bit signed integer. ### Example 1 ```text Input: nums = [3, 1, 3, 2, 1, 3] Output: [[1, 2], [2, 1], [3, 3]] ``` The value 1 appears twice, 2 once and 3 three times. ### Example 2 ```text Input: nums = [-5, 0, -5, 7] Output: [[-5, 2], [0, 1], [7, 1]] ``` Negative values sort before zero.

Constraints

  • 1 <= len(nums) <= 10^5
  • -10^9 <= nums[i] <= 10^9; values may be negative, zero or repeated.
  • Every value and every count fits in a 32-bit signed integer (none exceeds 2^31 - 1).

Examples

Input: ([5],)

Expected Output: [[5, 1]]

Explanation: Minimum valid: a single element gives one pair with count 1.

Input: ([-1000000000],)

Expected Output: [[-1000000000, 1]]

Explanation: Singleton at the lower value bound -10^9.

Hints

  1. Every distinct value gets exactly one pair, so the counts in your answer must add up to len(nums).
  2. Equal values are not necessarily next to each other in the input; make sure all occurrences of a value are counted together.
  3. The output order is fixed by the numeric value in each pair, not by input order or by count; negative values come before zero.

Loading coding console...

Show the approach

Approach

Sort a copy of nums in ascending numeric order, then scan it once. Invariant: after sorting, all occurrences of any value form one contiguous run, and runs appear in ascending value order. Each maximal run of equal values becomes one pair [value, run length], emitted in scan order, so the result has exactly one pair per distinct value, each pair carries that value's full count, and the pairs are already sorted by value; the run lengths sum to len(nums). The Python reference instead tallies counts in a dictionary and then walks the distinct keys in sorted order, which yields the same list. Edge cases: a single element gives [[x, 1]]; an all-equal list gives one pair whose count is len(nums); negatives, zero and the extremes -10^9 and 10^9 are compared as numbers, never as strings, so -10 precedes -2 and 9 precedes 10; the last run is emitted when the scan reaches the end. Every value and count fits in a 32-bit signed integer, so int suffices in Java and C++.

Time complexity:
O(n log n)
Space complexity:
O(n)