How do you solve Check if Array is Good on LeetCode?

Check if Array is Good (LeetCode #2784) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The maximum element determines the expected structure of the array.

What is the brute force solution for Check if Array is Good?

The brute force approach for Check if Array is Good is Brute Force, with O(n²) time complexity and O(1) space complexity. We can generate the expected good array for the maximum number found in the input and then check if the input is a permutation of this array. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Check if Array is Good?

Check if Array is Good uses the following concepts: Array, Hash Table, Sorting. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Check if Array is Good?

Clarify the problem statement and constraints before jumping into coding. Think about edge cases, such as arrays of length 1 or 2. Explain your thought process clearly while coding; it shows your understanding.

What are common mistakes when solving Check if Array is Good?

Failing to check the length of the input array against the expected length of base[n]. Not correctly counting occurrences of numbers.

#2784

Check if Array is Good

Easy

ArrayHash TableSortingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Instead of generating and sorting arrays, we can use a frequency count to validate the conditions for a good array directly, which is more efficient.

⚙️

Algorithm

4 steps

1Step 1: Find the maximum element in the array, n.
2Step 2: Count the occurrences of each number in the array using a hash map.
3Step 3: Check if the count of n is exactly 2 and if all numbers from 1 to n-1 appear exactly once.
4Step 4: If both conditions are satisfied, return true; otherwise, return false.

solution.py8 lines

1# Full working Python code
2
3def isGoodArray(nums):
4    n = max(nums)
5    count = {}  
6    for num in nums:
7        count[num] = count.get(num, 0) + 1
8    return count.get(n, 0) == 2 and all(count.get(i, 0) == 1 for i in range(1, n))

ℹ

Complexity note: The time complexity is O(n) because we only traverse the array a couple of times. The space complexity is O(n) due to the hash map storing counts of the elements.

1The maximum element determines the expected structure of the array.
2A good array must have exactly two occurrences of the maximum element and one of all others.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.