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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if Array is Good

Number: 2892

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an integer array nums, determine if it is a permutation of a special array base[n], where base[n] is defined as [1, 2, ..., n - 1, n, n] (an array of length n + 1 that contains every number from 1 to n - 1 exactly once and the number n exactly twice). In other words, verify whether nums can be rearranged to match base[n].

Key Insights

  • The maximum element in nums determines the candidate n.
  • The length of nums must be exactly n + 1.
  • All numbers from 1 to n - 1 should appear exactly once.
  • The number n must appear exactly twice.
  • Using a frequency count (hash table) is an efficient approach to verify these conditions.

Space and Time Complexity

Time Complexity: O(n) – We iterate through the array to count frequencies. Space Complexity: O(n) – Additional data structure (hash table) to store counts.

Solution

We first determine the candidate n by finding the maximum value from nums. Next, we check whether the length of nums is n + 1. If not, we immediately return false since it cannot match base[n]. Then we use a hash table (or dictionary) to count the frequency of each element. For each number i from 1 to n - 1, we check if its frequency is exactly 1. For n, we check if its frequency is exactly 2. If all conditions hold, the array is a valid permutation of base[n]; otherwise, it is not.

Code Solutions

# Python solution for checking if the array is good
def isGoodArray(nums):
    # Determine n as the maximum element in the array
    n = max(nums)
    
    # The length of the array must be n + 1 (base[n] length)
    if len(nums) != n + 1:
        return False
    
    # Count frequencies using a dictionary
    frequency = {}
    for num in nums:
        frequency[num] = frequency.get(num, 0) + 1
    
    # Check that every number from 1 to n-1 appears exactly once
    for i in range(1, n):
        if frequency.get(i, 0) != 1:
            return False

    # Check that n appears exactly twice
    if frequency.get(n, 0) != 2:
        return False
    
    return True

# Example usage:
print(isGoodArray([1, 3, 3, 2]))  # Expected output: True
← Back to All Questions