Check if Array is Good

Difficulty: Easy | Acceptance: 48.80% | Paid: No Topics: Array, Hash Table, Sorting

You are given an integer array nums. We consider an array good if it is a permutation of an array base[n] where base[n] = [1, 2, ..., n - 1, n, n]. In other words, it is an array of length n + 1 that contains all integers from 1 to n (inclusive) exactly once, and the number n exactly twice. Return true if nums is good, otherwise return false.

• Examples
• Constraints
• Sorting
• Frequency Map
• Boolean Array

Examples

Example 1

Input:

nums = [2, 1, 3]

Output:

false

Explanation: 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

Explanation: 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

Explanation: 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.

Example 4

Input:

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

Output:

false

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

Constraints

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

Sorting

Intuition If we sort the array, a “good” array will strictly follow the pattern [1, 2, ..., n, n]. We can simply sort the input and compare it against this expected pattern element by element.

Steps

• Calculate n as nums.length - 1.
• Sort the array nums in ascending order.
• Iterate through the array with index i from 0 to n:
  • For indices 0 to n-1, the value should be i + 1.
  • For the last index n, the value should be n.
• If any element does not match the expected value, return false.
• If the loop completes, return true.

class Solution:
    def isGood(self, nums: list[int]) -> bool:
        n = len(nums) - 1
        nums.sort()
        for i in range(n):
            if nums[i] != i + 1:
                return False
        return nums[n] == n

Complexity

• Time: O(n log n) due to sorting.
• Space: O(1) or O(n) depending on the sorting algorithm’s implementation.
• Notes: Modifies the input array.

Frequency Map

Intuition A “good” array has specific frequency requirements: every number from 1 to n-1 appears exactly once, and n appears exactly twice. We can count the frequency of each number and verify these conditions.

Steps

• Calculate n as nums.length - 1.
• Create a frequency map (hash table) to count occurrences of each number in nums.
• Iterate from 1 to n:
  • If the current number i is less than n, its count must be 1.
  • If the current number i is equal to n, its count must be 2.
  • If any count is incorrect, return false.
• Return true.

from collections import Counter

class Solution:
    def isGood(self, nums: list[int]) -> bool:
        n = len(nums) - 1
        count = Counter(nums)
        for i in range(1, n + 1):
            if i < n:
                if count.get(i, 0) != 1:
                    return False
            else:
                if count.get(i, 0) != 2:
                    return False
        return True

Complexity

• Time: O(n) for iterating through the array and the map.
• Space: O(n) to store the frequency map.
• Notes: Does not modify the input array.

Boolean Array

Intuition Since the constraints specify that nums[i] <= 100, we can use a fixed-size boolean array (or a bitset) to track which numbers we have seen. This is more space-efficient than a hash map for small integer ranges. We specifically need to ensure n appears twice and others appear once.

Steps

• Calculate n as nums.length - 1.
• Initialize a boolean array seen of size n + 1 with false.
• Initialize a counter countN to 0.
• Iterate through nums:
  • If the current number val is greater than n, return false.
  • If val equals n, increment countN.
  • Otherwise, if seen[val] is already true, it means we have a duplicate of a number that should appear only once, so return false.
  • Mark seen[val] as true.
• After the loop, check if countN == 2.
• Return true if all checks pass.

class Solution:
    def isGood(self, nums: list[int]) -> bool:
        n = len(nums) - 1
        seen = [False] * (n + 1)
        count_n = 0
        for val in nums:
            if val > n:
                return False
            if val == n:
                count_n += 1
            else:
                if seen[val]:
                    return False
                seen[val] = True
        return count_n == 2

Complexity

• Time: O(n) for a single pass through the array.
• Space: O(n) for the boolean array.
• Notes: Efficient for small integer ranges; avoids the overhead of a hash map.