We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check if Array is Good

Difficulty: Easy

Problem Description

You are given an integer array nums. We consider an array good if it is a permutation of an array base[n].

base[n] = [1, 2, ..., n - 1, n, n] (in other words, it is an array of length n + 1 which contains 1 to n - 1 exactly once, plus two occurrences of n). For example, base[1] = [1, 1] and base[3] = [1, 2, 3, 3].

Return true if the given array is good, otherwise return false.

Key Insights

  • The maximum element in the array determines the candidate n.
  • The length of the array must be exactly n + 1 for it to be a valid permutation of base[n].
  • The elements of the array must contain all integers from 1 to n - 1 exactly once and include n twice.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To determine if the given array nums is a good array:

  1. Find the maximum element in nums, which will be our candidate n.
  2. Check if the length of nums is equal to n + 1.
  3. Create a frequency map (or count array) to track the occurrences of each number from 1 to n.
  4. Ensure that each number from 1 to n - 1 appears exactly once and n appears exactly twice.
  5. If all conditions are met, return true. Otherwise, return false.

Code Solutions

def isGoodArray(nums):
    n = max(nums)  # Find the maximum element
    if len(nums) != n + 1:  # Check if the length is n + 1
        return False
    
    count = [0] * (n + 1)  # Initialize a count array to track occurrences
    for num in nums:
        if num > n:  # If any number is greater than n, return False
            return False
        count[num] += 1  # Increment count for the number
    
    # Check the conditions for a good array
    for i in range(1, n):
        if count[i] != 1:  # Each number from 1 to n-1 must appear exactly once
            return False
    if count[n] != 2:  # The number n must appear exactly twice
        return False
    
    return True  # All conditions are satisfied
← Back to All Questions