2784. Check if Array is Good

Array
Hash Table
Counting

TIME

O(n)

SPACE

O(n)

Intuition

If nums is good, then n must be the maximum value in the array. For that n, the required array has:

length n + 1
each value from 1 to n - 1 exactly once
value n exactly twice

So checking the maximum, length, and frequencies is sufficient.

Approach

Let n = max(nums).
If len(nums) != n + 1, return false.
Count the frequency of every value.
For each value from 1 to n - 1, verify frequency is 1.
Verify frequency of n is 2.

Complexity

Time: O(m), where m = len(nums)
Space: O(m), for the frequency table

Edge Cases

nums = [1, 1] -> valid base[1]
Wrong length -> immediately invalid
Missing values from 1..n-1
Maximum value appears fewer or more than two times

Code

from collections import Counter
from typing import List


class Solution:
    def isGood(self, nums: List[int]) -> bool:
        """
        2784. Check if Array is Good
        Time: O(n)
        Space: O(n)
        """
        n = max(nums)

        if len(nums) != n + 1:
            return False

        count = Counter(nums)

        for value in range(1, n):
            if count[value] != 1:
                return False

        return count[n] == 2

import java.util.HashMap;
import java.util.Map;

/**
 * 2784. Check if Array is Good
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    public boolean isGood(int[] nums) {
        int n = 0;
        for (int num : nums) {
            n = Math.max(n, num);
        }

        if (nums.length != n + 1) {
            return false;
        }

        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        for (int value = 1; value < n; value++) {
            if (count.getOrDefault(value, 0) != 1) {
                return false;
            }
        }

        return count.getOrDefault(n, 0) == 2;
    }
}