#2784

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Check if Array is Good

Determine if a given integer array is a permutation of base[n], containing 1 to n-1 once and n twice, using scanning and hash lookup.

array hash table sorting

Problem Statement

You are given an integer array nums. An array is considered good if it is a permutation of base[n], where base[n] consists of numbers from 1 to n-1 appearing exactly once and n appearing exactly twice. For example, base[1] = [1, 1], base[3] = [1, 2, 3, 3].

Return true if nums is a good array. Otherwise, return false. The array length ranges from 1 to 100, and each element is between 1 and 200. Identify the candidate n by the maximum number in nums and verify the permutation using scanning plus hash lookup.

Examples

Example 1

Input: nums = [2, 1, 3]

Output: false

Since the maximum element of the array is 3, the only candidate n for which this array could be a permutation of base[n], is n = 3. However, base[3] has four elements but array nums has three. Therefore, it can not be a permutation of base[3] = [1, 2, 3, 3]. So the answer is false.

Example 2

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

Output: true

Since the maximum element of the array is 3, the only candidate n for which this array could be a permutation of base[n], is n = 3. It can be seen that nums is a permutation of base[3] = [1, 2, 3, 3] (by swapping the second and fourth elements in nums, we reach base[3]). Therefore, the answer is true.

Example 3

Input: nums = [1, 1]

Output: true

Since the maximum element of the array is 1, the only candidate n for which this array could be a permutation of base[n], is n = 1. It can be seen that nums is a permutation of base[1] = [1, 1]. Therefore, the answer is true.

Constraints

1 <= nums.length <= 100
1 <= num[i] <= 200

Solution Approach

Find Maximum Element

Scan the array to find the maximum value n. This identifies the candidate base[n] the array could match, which is critical for early elimination if the array length does not match n + 1.

Use Hash Table for Counting

Create a hash map to count occurrences of each number. Verify that numbers 1 to n-1 appear exactly once and n appears exactly twice. Any discrepancy immediately returns false, ensuring correct adherence to the good array pattern.

Validate Array Length and Values

Check that the array length equals n + 1 and that all numbers fall between 1 and n. This ensures that out-of-range elements or extra/missing numbers are detected before deeper computation, aligning with the array scanning plus hash lookup pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(N) for scanning and counting, where N is the array length. Space complexity is O(N) due to the hash table storing counts for numbers up to n.

What Interviewers Usually Probe

Expect candidates to find the maximum element first.
Look for use of hash table or frequency array to verify counts efficiently.
Check if candidate quickly returns false on early mismatches to save time.

Common Pitfalls or Variants

Common pitfalls

Failing to check that array length matches n + 1, leading to incorrect true results.
Miscounting occurrences of the maximum element, allowing invalid arrays to pass.
Not validating that numbers 1 to n-1 appear exactly once, missing duplicates or missing numbers.

Follow-up variants

Check if array is good when numbers 1 to n-1 can appear multiple times but n appears exactly twice.
Check if array is good under larger constraints, up to length 1000, requiring more efficient hash or bitmap usage.
Check if array is good when numbers may be negative, requiring adjusted counting or hash lookup.

FAQ

What is the main pattern to solve Check if Array is Good?

The key pattern is array scanning plus hash lookup: find the maximum element, then count occurrences to verify the array matches base[n].

Can this approach handle arrays with length up to 100?

Yes, scanning the array once and using a hash table keeps time and space within acceptable limits for length up to 100.

What if nums contains numbers outside 1 to n?

Any number outside the range 1 to n immediately invalidates the good array pattern, so the function should return false.

Why do we need to check the array length?

The length must be n + 1 to match base[n], so verifying it prevents false positives where elements appear correct but count is insufficient.

Is there a simpler alternative to hash tables?

A counting array can replace a hash table since nums elements are bounded, allowing constant-time access for frequency checks.

terminal

Solution

Solution 1: Counting

We can use a hash table or array $cnt$ to record the number of occurrences of each element in the array $nums$. Then we determine whether the following conditions are met:

1

2

3

4

5

class Solution:
    def isGood(self, nums: List[int]) -> bool:
        cnt = Counter(nums)
        n = len(nums) - 1
        return cnt[n] == 2 and all(cnt[i] for i in range(1, n))

Continue Practicing

#2780 minimum index of a valid split #2766 relocate marbles #2813 maximum elegance of a k length subsequence