Check if Array is Good — Easy Problem & Solution

Problem statement

For an integer n, the array base[n] is [1, 2, …, n - 1, n, n] — the numbers 1 through n in order, with n appearing twice, so it has n + 1 elements.

Return true if nums is a permutation of base[n] for some n.

Example 1

Input: nums = [2,1,3]
Output: false
Explanation: Length 3 implies `n = 2`, so `base[2] = [1,2,2]`, which this is not.

Example 2

Input: nums = [1,3,3,2]
Output: true
Explanation: A permutation of `base[3] = [1,2,3,3]`.

Example 3

Input: nums = [1,1]
Output: true
Explanation: `base[1] = [1,1]`.

Constraints

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

How to solve Check if Array is Good

The length determines n = nums.length - 1. Count the values and check the exact multiset: 1 … n - 1 once each and n twice.

Approach

1. Set n = nums.length - 1; reject immediately if n < 1.
2. Count occurrences, rejecting any value outside 1 … n.
3. Require count[v] == 1 for v in 1 … n - 1 and count[n] == 2.

Why it works

Fixing n from the length first is what makes the check a single scan — without it there is no candidate to compare against. The range check inside the counting loop also keeps the count array in bounds, since values may be as large as 200 while n may be much smaller.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Values above n must be rejected, not silently ignored.
• n = 1 is the special case [1,1], where the "once each" range is empty.
• Sorting and comparing also works, but the counts are clearer.

Reference solution

Python

from typing import List
from collections import Counter

def isGood(nums: List[int]) -> bool:
    n = len(nums) - 1
    if n < 1:
        return False
    count = Counter(nums)
    if any(v < 1 or v > n for v in nums):
        return False
    for v in range(1, n):
        if count[v] != 1:
            return False
    return count[n] == 2

JavaScript

var isGood = function(nums) {
    var n = nums.length - 1, i;
    if (n < 1) return false;
    var count = [];
    for (i = 0; i <= n; i++) count.push(0);
    for (i = 0; i < nums.length; i++) {
        if (nums[i] < 1 || nums[i] > n) return false;
        count[nums[i]]++;
    }
    for (var v = 1; v < n; v++) if (count[v] !== 1) return false;
    return count[n] === 2;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy