LeetCode 2784 - Check if Array is Good

LeetCode Problem 2784

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sorting

Solution

Problem Understanding

The problem defines a special type of array called a "good" array. A good array must be a permutation of:

$$base[n] = [1, 2, 3, ..., n-1, n, n]$$

This means the array must contain:

• Every integer from 1 to n - 1 exactly once
• The integer n exactly twice
• No other numbers
• Total length equal to n + 1

The input is an integer array nums, and we must determine whether it satisfies these conditions.

The key observation is that the largest number in the array must be n. Since n appears twice and all smaller values appear once, the expected array structure becomes fully determined once we know the maximum value.

For example:

• If the maximum value is 3, then the only valid good array is a permutation of [1, 2, 3, 3]
• If the maximum value is 1, then the only valid good array is [1, 1]

The constraints are very small:

• nums.length <= 100
• nums[i] <= 200

Because the input size is tiny, even sorting-based solutions are completely acceptable.

Several edge cases are important:

• Arrays with incorrect length relative to the maximum value
• Arrays missing some value between 1 and n - 1
• Arrays where the maximum value appears more than twice or fewer than twice
• Arrays containing duplicates of smaller numbers
• The smallest possible valid input, [1, 1]

A naive implementation can easily miss one of these conditions if it only checks frequencies partially.

Approaches

Brute Force Approach

A straightforward brute-force strategy is to generate the expected base[n] array and compare it against the given array after sorting both arrays.

The algorithm works as follows:

1. Find the maximum value n in nums
2. Construct the expected array:

$$[1, 2, 3, ..., n-1, n, n]$$ 3. Sort both arrays 4. Compare them element by element

This approach is correct because sorting removes ordering concerns. If both sorted arrays are identical, then nums must be a permutation of base[n].

Although this approach is already efficient enough for the constraints, it still performs sorting operations, which are not strictly necessary.

Optimal Approach

The better observation is that we only need to verify frequency conditions.

If n is the maximum element, then:

• Array length must equal n + 1
• Values 1 through n - 1 must appear exactly once
• Value n must appear exactly twice

We can count occurrences using a hash map or frequency array and validate these conditions directly.

This avoids sorting entirely and gives linear time complexity.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(n)	Sorts both arrays and compares them
Optimal	O(n)	O(n)	Uses frequency counting to validate required structure

Algorithm Walkthrough

Optimal Frequency Counting Algorithm

1. Find the maximum value in the array.

This maximum value represents the only possible candidate for n. Since a good array must contain numbers from 1 through n, with n repeated twice, the largest number determines the expected structure. 2. Check whether the array length equals n + 1.

A valid base[n] array always has exactly n + 1 elements because it contains:

• n - 1 distinct smaller numbers
• Two copies of n

If the length does not match, we can immediately return false. 3. Count the frequency of every number.

Use a hash map to store how many times each value appears. 4. Verify frequencies for values 1 through n - 1.

Every smaller number must appear exactly once. If any number is missing or appears multiple times, the array is invalid. 5. Verify the frequency of n.

The maximum value must appear exactly twice. 6. Return true if all checks pass.

Why it works

The algorithm directly validates the mathematical definition of a good array.

A good array is uniquely determined by its maximum value n. Once n is known, the required frequencies become fixed:

• Exactly one occurrence for every value from 1 to n - 1
• Exactly two occurrences of n

If every required frequency matches perfectly and the length is correct, then the array must be a permutation of base[n].

Python Solution

from typing import List
from collections import Counter

class Solution:
    def isGood(self, nums: List[int]) -> bool:
        n = max(nums)

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

        frequency = Counter(nums)

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

        return frequency[n] == 2

The implementation begins by finding the maximum value, which represents the only possible candidate for n.

Next, the code checks whether the array length matches the required size of n + 1. This quickly eliminates impossible cases.

The Counter class from Python's collections module provides an easy way to count frequencies.

The loop validates that every integer from 1 through n - 1 appears exactly once. Finally, the algorithm checks whether n appears exactly twice.

If every condition succeeds, the function returns True.

Go Solution

func isGood(nums []int) bool {
    n := 0

    for _, num := range nums {
        if num > n {
            n = num
        }
    }

    if len(nums) != n+1 {
        return false
    }

    frequency := make(map[int]int)

    for _, num := range nums {
        frequency[num]++
    }

    for value := 1; value < n; value++ {
        if frequency[value] != 1 {
            return false
        }
    }

    return frequency[n] == 2
}

The Go solution follows the same logic as the Python implementation.

Since Go does not provide a built-in Counter type, a map[int]int is used to track frequencies manually.

Go slices naturally handle dynamic array input, so no special handling is required for empty arrays because the constraints guarantee at least one element.

Integer overflow is not a concern because the values are very small.

Worked Examples

Example 1

Input: nums = [2, 1, 3]

Step 1: Find maximum value

Variable	Value
n	3

Step 2: Check length

Expected length:

$$n + 1 = 4$$

Actual length:

$$3$$

Since the lengths do not match, return false.

Example 2

Input: nums = [1, 3, 3, 2]

Step 1: Find maximum value

Variable	Value
n	3

Step 2: Check length

Expected	Actual
4	4

Valid so far.

Step 3: Count frequencies

Number	Frequency
1	1
2	1
3	2

Step 4: Validate numbers 1 through n - 1

Value	Expected	Actual
1	1	1
2	1	1

Step 5: Validate n

Value	Expected	Actual
3	2	2

All conditions pass, return true.

Example 3

Input: nums = [1, 1]

Step 1: Find maximum value

Variable	Value
n	1

Step 2: Check length

Expected	Actual
2	2

Step 3: Count frequencies

Number	Frequency
1	2

There are no values from 1 to n - 1, so only the final condition matters.

1 appears exactly twice, return true.

Example 4

Input: nums = [3, 4, 4, 1, 2, 1]

Step 1: Find maximum value

Variable	Value
n	4

Step 2: Check length

Expected	Actual
5	6

Lengths do not match, so return false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to find maximum, one pass to count frequencies, one pass to validate
Space	O(n)	Frequency map stores counts for array elements

The algorithm performs only linear scans over the input array. Every operation inside the loops runs in constant time, giving an overall time complexity of O(n).

The frequency map may store up to n distinct values, so the auxiliary space complexity is O(n).

Test Cases

solution = Solution()

# Provided examples
assert solution.isGood([2, 1, 3]) == False  # length mismatch
assert solution.isGood([1, 3, 3, 2]) == True  # valid good array
assert solution.isGood([1, 1]) == True  # smallest valid case
assert solution.isGood([3, 4, 4, 1, 2, 1]) == False  # extra duplicate

# Boundary cases
assert solution.isGood([2, 2, 1]) == True  # valid n = 2 case
assert solution.isGood([2, 1, 1]) == False  # maximum appears once only
assert solution.isGood([3, 3, 3, 1, 2]) == False  # maximum appears too many times

# Missing values
assert solution.isGood([1, 4, 4, 2]) == False  # missing 3
assert solution.isGood([2, 2]) == False  # missing 1

# Duplicate smaller values
assert solution.isGood([1, 2, 2, 3]) == False  # duplicate smaller number

# Unsorted valid input
assert solution.isGood([4, 1, 3, 2, 4]) == True  # permutation of base[4]

# Incorrect length
assert solution.isGood([1, 2, 3, 3, 4]) == False  # invalid size

Test Case Summary

Test	Why
[2, 1, 3]	Detects invalid length
[1, 3, 3, 2]	Standard valid example
[1, 1]	Smallest valid input
[3, 4, 4, 1, 2, 1]	Detects extra duplicate
[2, 2, 1]	Valid case for n = 2
[2, 1, 1]	Maximum appears only once
[3, 3, 3, 1, 2]	Maximum appears too many times
[1, 4, 4, 2]	Missing intermediate value
[2, 2]	Missing required smaller value
[1, 2, 2, 3]	Duplicate non-maximum value
[4, 1, 3, 2, 4]	Valid unsorted permutation
[1, 2, 3, 3, 4]	Invalid array length

Edge Cases

Smallest Possible Input

The array [1, 1] is the smallest valid good array. This case is important because there are no numbers from 1 to n - 1.

A buggy implementation might incorrectly assume that at least one smaller value must exist. The current implementation handles this correctly because the validation loop:

for value in range(1, n):

becomes an empty loop when n = 1.

Duplicate Smaller Values

An array like [1, 2, 2, 3] is invalid because the duplicate value is not the maximum.

This is a common source of mistakes if the implementation only checks whether the maximum appears twice. The frequency validation loop ensures every smaller number appears exactly once.

Missing Intermediate Values

An array such as [1, 4, 4, 2] is invalid because the number 3 is missing.

A naive implementation that only checks length and maximum frequency could incorrectly accept this array. The explicit verification of every value from 1 through n - 1 prevents this bug.

Incorrect Length

Arrays like [2, 1, 3] fail because the maximum value is 3, meaning the expected array size should be 4.

Length checking is important because even if frequencies look reasonable, the array cannot represent base[n] unless the size matches exactly. The implementation performs this validation immediately for early termination.