Check if Array is Good

The problem can be solved by checking two conditions:

The array nums must have n+1 elements, where n is the maximum element in the array.
n must occur exactly twice, and the remaining elements must occur exactly once.

Here is a Python solution that follows this approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def is_good(nums):
    n = max(nums)  # the maximum element
    if len(nums) != n + 1:
        return False  # Condition 1
    
    counts = [0] * (n + 1)  # count the occurrences of each number
    for num in nums:
        counts[num] += 1

    for i in range(1, n + 1):
        if i < n and counts[i] != 1:
            return False  # numbers 1 to n-1 should occur once
        if i == n and counts[i] != 2:
            return False  # n should occur twice

    return True

In this solution, we first calculate the maximum element n in the array nums. Then we check Condition 1: the length of nums must be n+1. If not, we return False.

Next, we count the number of occurrences of each number in nums. We use a list counts of size n+1 for this, where counts[i] is the number of occurrences of i in nums.

Finally, we iterate through the numbers from 1 to n and check Condition 2: numbers 1 to n-1 must occur exactly once, and n must occur exactly twice. If any of these conditions is not met, we return False. If both conditions are met for all numbers, we return True.

This solution has a time complexity of O(n) where n is the length of nums, and a space complexity of O(n) for the counts array.

Ruby solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def is_good(nums)
    n = nums.max  # the maximum element
    return false if nums.length != n + 1  # Condition 1
    
    counts = Array.new(n + 1, 0)  # count the occurrences of each number
    nums.each do |num|
        counts[num] += 1
    end

    (1..n).each do |i|
        return false if i < n && counts[i] != 1  # numbers 1 to n-1 should occur once
        return false if i == n && counts[i] != 2  # n should occur twice
    end

    true
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def is_good(nums)
    n = nums.max  # the maximum element
    return false if nums.length != n + 1  # Condition 1
    
    counts = Array.new(n + 1, 0)  # count the occurrences of each number
    nums.each do |num|
        counts[num] += 1
    end

    for i in (1..n) 
      return false if i < n && counts[i] != 1  # numbers 1 to n-1 should occur once
      return false if i == n && counts[i] != 2  # n should occur twice  
    end

    true
end

In Ruby, we use the max method to find the maximum element in nums and we define counts as an Array with default values of zero. The .each method is used for iterating through the elements in nums and the range (1..n). We use the && operator for logical AND, and the if keyword for conditionals. The rest of the code is structurally the same as the Python version.

This solution still has a time complexity of O(n) and a space complexity of O(n), where n is the length of nums.

1
2
3
4
5
6
7
8
9
def is_good(nums)
    v = Array.new(202, 0)
    nums.each { |n| v[n] += 1 }
    return false if v[nums.size-1] != 2
    (1...(nums.size-1)).each do |i|
        return false if v[i] != 1
    end
    return true
end

Bit easier to read:

Key Takeaways

The term permutation should not mislead you
Check the given conditions individually without trying to see if the given input is a permutation
Don’t try to over-engineer the solution