Problem Description

You need to determine if a given integer array nums is "good" based on a specific definition.

An array is considered good if it's a permutation of a special array called base[n], where:

• base[n] = [1, 2, ..., n-1, n, n]
• This means base[n] has length n + 1
• It contains each number from 1 to n-1 exactly once
• The number n appears exactly twice

For example:

• base[1] = [1, 1] (contains one 1 twice)
• base[3] = [1, 2, 3, 3] (contains 1 and 2 once each, and 3 twice)

Your task is to return true if the given array nums is a permutation of some base[n] array (meaning it has the same elements with the same frequencies, just possibly in a different order), and false otherwise.

The key requirements for a good array are:

1. The length must be n + 1 for some positive integer n
2. Numbers from 1 to n-1 must each appear exactly once
3. The number n must appear exactly twice
4. No other numbers should be present

Intuition

To check if an array is "good", we need to verify it matches the pattern of base[n] for some value of n.

First, let's figure out what n should be. Since base[n] has length n + 1, and our input array nums has a certain length, we can deduce that n = len(nums) - 1.

Now we need to verify two things:

1. The largest value n appears exactly twice
2. All values from 1 to n-1 appear exactly once

The most straightforward way to check these conditions is to count the occurrences of each element in nums. We can use a frequency counter to track how many times each number appears.

Once we have the counts:

• Check if cnt[n] == 2 (the largest element appears twice)
• Check if all numbers from 1 to n-1 appear exactly once

The beauty of this approach is that we don't need to explicitly check if each count equals 1 - we can simply verify that all counts from 1 to n-1 are non-zero (truthy). If any number in this range is missing, its count would be 0 (falsy). If any number appears more than once, we'd have too many total elements for our array length, which would be caught by our check of n appearing exactly twice.

This counting approach gives us a clean, efficient solution that directly validates the definition of a "good" array.

Learn more about Sorting patterns.

Solution Approach

The solution uses a counting approach with a hash table to verify if the array matches the required pattern.

Step 1: Count element frequencies

cnt = Counter(nums)

We use Python's Counter from the collections module to create a frequency map of all elements in nums. This gives us a dictionary where keys are the elements and values are their occurrence counts.

Step 2: Determine the value of n

n = len(nums) - 1

Since base[n] has length n + 1, and our array nums should match this pattern, we calculate n as len(nums) - 1.

Step 3: Verify the conditions

return cnt[n] == 2 and all(cnt[i] for i in range(1, n))

This return statement checks two critical conditions:

1. cnt[n] == 2: Verifies that the largest element n appears exactly twice in the array.

2. all(cnt[i] for i in range(1, n)): Checks that all numbers from 1 to n-1 exist in the array. The all() function returns True only if all elements in the iterable are truthy. Since cnt[i] returns the count of element i, this will be:

   • 0 (falsy) if element i is missing from the array
   • A positive number (truthy) if element i exists in the array

The combination of these two checks ensures:

• The array has the correct length (n + 1)
• Contains all required elements with correct frequencies
• No extra elements are present (since if we have all elements from 1 to n-1 once each, plus n twice, that accounts for all n + 1 elements)

Time Complexity: O(n) where n is the length of the input array, as we iterate through the array once to count elements and then check up to n values.

Space Complexity: O(n) for storing the frequency counter.

Example Walkthrough

Let's walk through the solution with nums = [1, 2, 3, 3]:

Step 1: Count element frequencies

cnt = Counter([1, 2, 3, 3])
# cnt = {1: 1, 2: 1, 3: 2}

We create a frequency map showing that 1 appears once, 2 appears once, and 3 appears twice.

Step 2: Determine the value of n

n = len([1, 2, 3, 3]) - 1 = 4 - 1 = 3

Since the array has length 4, we calculate n = 3. This means we're checking if the array is a permutation of base[3] = [1, 2, 3, 3].

Step 3: Verify the conditions

# Check cnt[n] == 2
cnt[3] == 2  # True (3 appears twice)

# Check all(cnt[i] for i in range(1, n))
# range(1, 3) gives us [1, 2]
cnt[1] = 1  # Truthy (1 exists in array)
cnt[2] = 1  # Truthy (2 exists in array)
all([1, 1]) = True  # All values are truthy

# Final result: True and True = True

The array passes both checks:

• The largest element (3) appears exactly twice ✓
• All elements from 1 to 2 appear at least once ✓

Therefore, [1, 2, 3, 3] is a good array.

Counter-example: Let's try nums = [1, 1, 3, 3]:

cnt = {1: 2, 3: 2}
n = 4 - 1 = 3
cnt[3] == 2  # True
all(cnt[i] for i in range(1, 3))  # range gives [1, 2]
# cnt[1] = 2 (truthy), but cnt[2] = 0 (falsy, since 2 is missing)
# all([2, 0]) = False

# Result: True and False = False

This array fails because element 2 is missing, making it not a valid permutation of base[3].

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums.

• Creating the Counter object requires iterating through all elements in nums, which takes O(n) time.
• Computing n = len(nums) - 1 takes O(1) time.
• Checking cnt[n] == 2 takes O(1) time.
• The all() function with the generator expression cnt[i] for i in range(1, n) iterates through values from 1 to n-1, checking each value in the Counter. This takes O(n) time in the worst case.
• Overall, the dominant operation is O(n), so the total time complexity is O(n).

The space complexity is O(n), where n is the length of the array nums.

• The Counter object stores at most n unique elements from the input array, requiring O(n) space in the worst case.
• The variable n and other temporary variables use O(1) space.
• The generator expression in all() doesn't create additional data structures, just iterates.
• Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Handling Edge Cases for Empty or Single Element Arrays

The current solution doesn't properly handle edge cases where the array is empty or has only one element. For an empty array, n would be calculated as -1, and for a single element array, n would be 0. Neither of these represents valid "good" arrays since:

• base[0] doesn't exist (n must be positive)
• An empty array cannot be a permutation of any base[n]

Fix:

def isGood(self, nums: List[int]) -> bool:
    # Handle edge cases
    if len(nums) <= 1:
        return False
  
    frequency_counter = Counter(nums)
    n = len(nums) - 1
  
    # Rest of the logic remains the same
    has_n_twice = frequency_counter[n] == 2
    has_all_numbers = all(frequency_counter[i] == 1 for i in range(1, n))
  
    return has_n_twice and has_all_numbers

Pitfall 2: Incorrect Frequency Checking Logic

The original code uses all(frequency_counter[i] for i in range(1, n)) which only checks if elements exist (non-zero count) but doesn't verify they appear exactly once. This would incorrectly validate arrays where numbers from 1 to n-1 appear more than once.

Example of failure: [1, 1, 2, 3, 3] would pass the original check even though 1 appears twice (should appear once).

Fix:

def isGood(self, nums: List[int]) -> bool:
    if len(nums) <= 1:
        return False
      
    frequency_counter = Counter(nums)
    n = len(nums) - 1
  
    # Explicitly check that each number from 1 to n-1 appears exactly once
    has_n_twice = frequency_counter[n] == 2
    has_all_numbers_once = all(frequency_counter[i] == 1 for i in range(1, n))
  
    # Also verify no extra numbers exist
    expected_sum = sum(range(1, n)) + 2 * n  # Sum of base[n]
    actual_sum = sum(nums)
  
    return has_n_twice and has_all_numbers_once and expected_sum == actual_sum

Pitfall 3: Not Validating Array Contains Only Valid Numbers

The solution doesn't check if the array contains numbers outside the valid range [1, n]. An array like [0, 1, 2, 2] or [1, 2, 5, 5] might pass some checks but shouldn't be considered "good".

Fix:

def isGood(self, nums: List[int]) -> bool:
    if len(nums) <= 1:
        return False
      
    frequency_counter = Counter(nums)
    n = len(nums) - 1
  
    # Check that we have exactly the right set of keys
    # Should have numbers 1 through n, no more, no less
    if set(frequency_counter.keys()) != set(range(1, n + 1)):
        return False
  
    # Now check frequencies
    has_n_twice = frequency_counter[n] == 2
    has_all_numbers_once = all(frequency_counter[i] == 1 for i in range(1, n))
  
    return has_n_twice and has_all_numbers_once