Rearrange an Array to Minimize the Sum of Distinct Counts over All Prefixes
Company: Goldman Sachs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
You are given an integer array `nums` and may rearrange its elements into any order. For an arrangement `a` of length `n`, its cost is the sum, over every prefix `a[0..i]` for `i` from `0` to `n - 1`, of the number of distinct values in that prefix. Return the minimum cost over all arrangements of `nums`.
### Function Signature
```python
def min_prefix_distinct_sum(nums: list[int]) -> int:
```
### Rules
- Every element is used exactly once; equal values are interchangeable.
- The number of distinct values in a prefix counts each value once, however many times it appears in that prefix.
- Return only the minimum cost, a single integer, not the arrangement, so the answer is unique even when several arrangements reach it.
### Constraints
- `1 <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
- The answer can exceed `2^31 - 1`: when all `n` values are distinct it is `n * (n + 1) / 2`, which is `5,000,050,000` for `n = 10^5`. Use a 64-bit integer; the answer always stays below `2^53`.
### Examples
**Example 1**
```text
Input: nums = [1, 2, 2, 3, 3, 3]
Output: 10
```
In the given order the prefix distinct counts are `1, 2, 2, 3, 3, 3`, a cost of `14`. The arrangement `[3, 3, 3, 2, 2, 1]` has counts `1, 1, 1, 2, 2, 3`, a cost of `10`, and no arrangement does better.
**Example 2**
```text
Input: nums = [4, 1, 4, 1]
Output: 6
```
The given order costs `1 + 2 + 2 + 2 = 7`; `[4, 4, 1, 1]` costs `1 + 1 + 2 + 2 = 6`, the minimum.
**Example 3**
```text
Input: nums = [9, -2, 5]
Output: 6
```
All values are distinct, so every arrangement costs `1 + 2 + 3 = 6`.
Overview: A coding problem: rearrange an integer array to minimize the sum, over every prefix, of the number of distinct values in that prefix, and return that minimum. It tests reasoning about how ordering affects prefix statistics, frequency counting, and handling answers that exceed 32-bit integers.
You are given an integer array `nums` and may rearrange its elements into any order. For an arrangement `a` of length `n`, its cost is the sum, over every prefix `a[0..i]` for `i` from `0` to `n - 1`, of the number of distinct values in that prefix. Return the minimum cost over all arrangements of `nums`.
**Rules**
- Every element is used exactly once; equal values are interchangeable.
- The number of distinct values in a prefix counts each value once, however many times it appears in that prefix.
- Return only the minimum cost, a single integer, not the arrangement, so the answer is unique even when several arrangements reach it.
**Example 1**
```text
Input: nums = [1, 2, 2, 3, 3, 3]
Output: 10
```
In the given order the prefix distinct counts are `1, 2, 2, 3, 3, 3`, a cost of `14`. The arrangement `[3, 3, 3, 2, 2, 1]` has counts `1, 1, 1, 2, 2, 3`, a cost of `10`, and no arrangement does better.
**Example 2**
```text
Input: nums = [4, 1, 4, 1]
Output: 6
```
The given order costs `1 + 2 + 2 + 2 = 7`; `[4, 4, 1, 1]` costs `1 + 1 + 2 + 2 = 6`, the minimum.
**Constraints**
- `1 <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
- The answer can exceed `2^31 - 1`: when all `n` values are distinct it is `n * (n + 1) / 2`, which is `5,000,050,000` for `n = 10^5`. Return it as a 64-bit integer (`long` in Java, `long long` in C++); the answer always stays below `2^53`.
Constraints
- 1 <= len(nums) <= 10^5
- -10^9 <= nums[i] <= 10^9
- The answer can exceed 2^31 - 1 (it is n * (n + 1) / 2 = 5,000,050,000 when all n = 10^5 values are distinct): return it as a 64-bit integer (long in Java, long long in C++); it always stays below 2^53.
Examples
Input: ([1, 2, 2, 3, 3, 3],)
Expected Output: 10
Explanation: Source example 1: frequencies 3, 2, 1 placed most frequent first give prefix counts 1+1+1+2+2+3 = 10; an ascending-frequency order would give 14.
Input: ([4, 1, 4, 1],)
Expected Output: 6
Explanation: Source example 2: two values tied at frequency 2; either grouped order costs 1+1+2+2 = 6, while the given interleaved order costs 7.
Hints
- A value is counted in every prefix from the position where it first appears through the end of the arrangement.
- Equal values are interchangeable, so ask which facts about nums can change the cost at all.
- Compare the given order and the better arrangement in Example 1: look at where each value appears for the first time.