Условие

Дан массив arr. Нужно определить, уникальны ли количества встречающихся элементов.

Примеры

Input: [1, 2, 2, 1, 1, 3] Output: true Explanation: Число 1 встречается 3 раза, 2 — 2 раза, а 3 — 1 раз. Ни у двух чисел нет одинакового количества вхождений.

Input: [1, 2] Output: false

Input: [-3, 0, 1, -3, 1, 1, -3, 10, 0] Output: true

Решение

fun uniqueOccurrences(arr: IntArray): Boolean {
    val countMap = IntArray(2001) // Считаем количество вхождений (-1000 до 1000)
    for (num in arr) countMap[num + 1000]++

    val seen = BooleanArray(1001) // Храним, какие количества уже встречались
    for (count in countMap) {
        if (count > 0) {
            if (seen[count]) return false
            seen[count] = true
        }
    }
    return true
}

Временная сложность

O(n), где n — длина массива arr.

Пространственная сложность

O(1), так как используются фиксированные массивы длиной 2001 и 1001.