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.
Note: A permutation of integers represents an arrangement of these numbers.
Example 1:
Input: nums = [2, 1, 3] Output: false Explanation: Since the maximum element of the array is 3, the only candidate n for which this array could be a permutation of base[n], is n = 3. However, base[3] has four elements but array nums has three. Therefore, it can not be a permutation of base[3] = [1, 2, 3, 3]. So the answer is false.
Example 2:
Input: nums = [1, 3, 3, 2] Output: true Explanation: Since the maximum element of the array is 3, the only candidate n for which this array could be a permutation of base[n], is n = 3. It can be seen that nums is a permutation of base[3] = [1, 2, 3, 3] (by swapping the second and fourth elements in nums, we reach base[3]). Therefore, the answer is true.
Example 3:
Input: nums = [1, 1] Output: true Explanation: Since the maximum element of the array is 1, the only candidate n for which this array could be a permutation of base[n], is n = 1. It can be seen that nums is a permutation of base[1] = [1, 1]. Therefore, the answer is true.
Example 4:
Input: nums = [3, 4, 4, 1, 2, 1] Output: false Explanation: Since the maximum element of the array is 4, the only candidate n for which this array could be a permutation of base[n], is n = 4. However, base[4] has five elements but array nums has six. Therefore, it can not be a permutation of base[4] = [1, 2, 3, 4, 4]. So the answer is false.
Constraints:
1 <= nums.length <= 1001 <= num[i] <= 200Problem Overview: You’re given an integer array nums. The array is considered good if, after rearranging, it exactly matches the sequence [1, 2, 3, ..., n-1, n-1]. That means every value from 1 to n-2 appears once, and n-1 appears twice. The task is to verify whether the given array satisfies this structure.
Approach 1: Frequency Matching Approach (O(n) time, O(n) space)
This method uses a frequency counter to verify the required counts of each number. First compute n = nums.length. A valid array must contain numbers only in the range [1, n-1]. Use a hash map or counting array to track how many times each value appears. Then iterate through the expected range: numbers 1 to n-2 must appear exactly once, while n-1 must appear exactly twice. If any number is missing, appears too many times, or an out-of-range value exists, the array is not good. The key insight is that the target configuration has a strict frequency pattern, which makes a single pass with a hash lookup sufficient. This approach is the most direct and runs in linear time using a hash table.
Approach 2: Sorting and Comparison Approach (O(n log n) time, O(1) or O(log n) space)
Another option is to sort the array first. After sorting, a valid array must look exactly like [1, 2, 3, ..., n-1, n-1]. Iterate through the sorted array and check that index i contains i+1 for all positions except the last one, and the final two elements should both be n-1. Sorting groups duplicates together and ensures the sequence is ordered, making verification straightforward. The tradeoff is the O(n log n) sorting cost. This approach works well when sorting is already part of a pipeline or when avoiding extra hash memory. It relies on standard sorting techniques applied to an array.
Recommended for interviews: The frequency matching approach is usually the expected solution. It demonstrates that you identified the exact frequency pattern required by the definition of a good array and implemented a linear scan with constant-time lookups. The sorting approach is still valid and easy to reason about, but the O(n) hash-based solution shows stronger algorithmic thinking and optimal complexity.
This approach builds on the concept of frequency matching. The task is to determine if the array nums is a permutation of base[n], which is essentially checking if the frequency of numbers in nums matches the expected frequency in base[n].
First, we find the maximum element in nums. Let's denote this value as n. The array base[n] has a length of n+1 and contains numbers from 1 to n-1 plus two occurrences of n. This implies that for nums to be a permutation of base[n], it should also contain numbers from 1 to n-1 exactly once and the number n twice.
This implementation uses a counting approach to track the frequency of each number in nums. It ensures every number from 1 to n-1 appears exactly once and the number n appears exactly twice. The array size should also match n + 1 for it to be a valid permutation of base[n].
Time Complexity: O(n) as it involves simply iterating over the array.
Space Complexity: O(1) since the frequency array size is constant (200, based on constraints).
This approach involves sorting and direct comparison. By sorting the array and comparing it with the base[n], we can determine if it is a permutation. Use the maximum value in the array to determine n and construct base[n]. Compare the sorted nums against base[n].
This C code sorts the array first, then checks sequentially if each number matches the expected value in base[n]. After sorting, the array should start with 1 up to n-1 and end with two n if it is good.
Time Complexity: O(n log n) due to sorting, followed by an O(n) comparative check.
Space Complexity: O(1) additional space since the sorting can be done in-place.
We can use a hash table or array cnt to record the number of occurrences of each element in the array nums. Then we determine whether the following conditions are met:
cnt[n] = 2, i.e., the largest element in the array appears twice;1 leq i leq n-1, it holds that cnt[i] = 1, i.e., except for the largest element, all other elements appear only once.If the above two conditions are met, then the array nums is a good array, otherwise it is not.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Frequency Matching Approach | Time Complexity: O(n) as it involves simply iterating over the array. |
| Sorting and Comparison Approach | Time Complexity: O(n log n) due to sorting, followed by an O(n) comparative check. |
| Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Matching (Hash Table) | O(n) | O(n) | Best general solution. Fast single pass with explicit frequency validation. |
| Sorting and Comparison | O(n log n) | O(1)–O(log n) | Useful when sorting is already required or when avoiding hash maps. |
2784. Check if Array is Good | Leetcode 2784 | BiWeekly 109 • Tech Courses • 871 views views
Watch 8 more video solutions →Practice Check if Array is Good with our built-in code editor and test cases.
Practice on FleetCode