Check if Array is Good
EasyPrompt
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] <= 200
Approaches
3 approaches with complexity analysis and trade-offs.
This approach relies on the property that two arrays which are permutations of each other will become identical when sorted. We first construct the theoretical base[n] array that nums should be a permutation of. Then, we sort the input nums and compare it element by element with the constructed base[n] array.
Algorithm
- Let
Lbe the length of the input arraynums. - The target array
base[n]has a length ofn + 1. Fornumsto be a permutation ofbase[n], their lengths must be equal. Thus,nmust beL - 1. - If
L <= 1, it cannot be a good array, so we returnfalse. - Create the expected
base[n]array, which is[1, 2, ..., n-1, n, n]. - Sort the input array
numsin non-decreasing order. - Compare the sorted
numsarray with thebase[n]array. If they are identical,numsis a good array. Otherwise, it is not.
Walkthrough
The core idea is to transform the permutation check into an equality check. A "good" array is a permutation of base[n] = [1, 2, ..., n-1, n, n]. The length of base[n] is n+1. So, for a given input nums of length L, the only candidate for n is L-1.
First, we determine this value of n. Then, we explicitly build the base[n] array. After that, we sort the input array nums. If nums is indeed a permutation of base[n], its sorted version must be identical to base[n] (which is already sorted by construction). We can then use a standard library function to compare the two arrays for equality.
For example, if nums = [1, 3, 3, 2], its length is 4, so n=3. The base[3] array is [1, 2, 3, 3]. After sorting, nums becomes [1, 2, 3, 3], which matches base[3]. Thus, the array is good.
import java.util.Arrays; class Solution { public boolean isGood(int[] nums) { int len = nums.length; if (len <= 1) { return false; } int n = len - 1; int[] base = new int[len]; for (int i = 0; i < n; i++) { base[i] = i + 1; } base[n] = n; Arrays.sort(nums); return Arrays.equals(nums, base); }}Complexity
Time
O(L log L), where L is the length of `nums`. The sorting step `Arrays.sort(nums)` is the dominant factor in the time complexity.
Space
O(L), where L is the length of `nums`. This is for storing the `base` array. The sorting algorithm might also use `O(log L)` to `O(L)` space, depending on the implementation.
Trade-offs
Pros
The logic is straightforward and easy to understand.
Implementation is simple, especially with built-in sorting and array comparison functions.
Cons
This approach has a time complexity of
O(L log L), which is not optimal.It requires extra space of
O(L)to store thebasearray, in addition to the space used by the sorting algorithm.
This approach is a space-optimized version of the previous sorting method. Instead of creating an entire base[n] array to compare against, we sort the input array nums and then directly verify if its elements follow the required pattern of a sorted base[n] array. This avoids the need for an auxiliary array for comparison.
Algorithm
- Let
Lbe the length ofnumsand setn = L - 1. - If
L <= 1, returnfalse. - Sort the input array
nums. - A sorted "good" array must look like
[1, 2, ..., n-1, n, n]. - Check if
nums[i]equalsi + 1forifrom0ton-1. - Check if the last element
nums[n]equalsn. - If all these conditions are met, the array is good; otherwise, it's not.
Walkthrough
After sorting, a "good" array nums of length L = n+1 must be identical to [1, 2, ..., n-1, n, n]. We can check this structure with a single pass over the sorted array.
The algorithm is as follows:
- Sort
nums. - The first
nelements of the sorted array should be1, 2, ..., n. We can check this by looping fromi = 0ton-1and verifying thatnums[i] == i + 1. - The last element of the sorted array,
nums[n], must also ben.
If both conditions hold, the array has the correct structure. For example, if nums = [1, 3, 3, 2], it's sorted to [1, 2, 3, 3]. Here n=3. The loop checks nums[0]==1, nums[1]==2, nums[2]==3. All pass. Then we check nums[3]==3, which also passes. So, the array is good.
import java.util.Arrays; class Solution { public boolean isGood(int[] nums) { int len = nums.length; int n = len - 1; if (len <= 1) { return false; } Arrays.sort(nums); // Check if the first n elements are 1, 2, ..., n for (int i = 0; i < n; i++) { if (nums[i] != i + 1) { return false; } } // Check if the last element is also n if (nums[n] != n) { return false; } return true; }}Complexity
Time
O(L log L), where L is the length of `nums`. Sorting is the bottleneck.
Space
O(log L) to O(L), depending on the implementation of the sorting algorithm. This is an improvement over the O(L) space required by the previous approach.
Trade-offs
Pros
More space-efficient than the full comparison approach as it avoids creating a new array.
The logic remains relatively simple and easy to follow.
Cons
The time complexity is still
O(L log L)due to sorting, which is less efficient than a linear-time solution.
This approach provides the most optimal time complexity by avoiding sorting altogether. It uses a frequency map (or an array, given the constraints on the values) to count the occurrences of each number in the input array. Then, it checks if the frequencies match the definition of a base[n] array: numbers 1 to n-1 appear once, and n appears twice.
Algorithm
- Let
Lbe the length ofnumsand setn = L - 1. - If
L <= 1, returnfalse. - Create a frequency array,
counts, of sizen + 1to store the occurrences of numbers from 1 ton. - Iterate through
nums. For each numbernum:- If
numis outside the range[1, n], the array cannot be good, so returnfalse. - Increment the count for
numin thecountsarray.
- If
- After populating the counts, verify them:
- Check if
counts[i]is1for allifrom1ton-1. - Check if
counts[n]is2.
- Check if
- If any check fails, return
false. Otherwise, returntrue.
Walkthrough
The definition of a "good" array is purely based on the counts of its elements. This suggests a direct counting approach. We can use an auxiliary array to act as a frequency map.
First, we establish that n must be nums.length - 1. We create a counts array of size n+1 (or larger, based on constraints) initialized to zeros. We iterate through nums, and for each number, we increment its corresponding index in the counts array. During this pass, we can also check if any number is out of the valid range [1, n], which would immediately disqualify the array.
After counting, we iterate from 1 to n-1 and check if counts[i] is exactly 1. Finally, we check if counts[n] is exactly 2. If all these conditions are satisfied, the array is good.
class Solution { public boolean isGood(int[] nums) { int len = nums.length; int n = len - 1; if (len <= 1) { return false; } // Frequencies for numbers 1 to n. Index 0 is unused. int[] counts = new int[n + 1]; for (int num : nums) { // If a number is out of the expected range [1, n], it's not good. if (num > n || num <= 0) { return false; } counts[num]++; } // Check counts for 1 to n-1 for (int i = 1; i < n; i++) { if (counts[i] != 1) { return false; } } // Check count for n if (counts[n] != 2) { return false; } return true; }}Complexity
Time
O(L), where L is the length of `nums`. We perform a constant number of passes through the array or arrays of a similar size.
Space
O(L) or O(n). We use a frequency array of size `n+1`. Since `n = L-1`, the space is linear with respect to the input size. Given the problem constraints, this is a small, fixed amount of space.
Trade-offs
Pros
Achieves optimal linear time complexity,
O(L).The logic directly verifies the definition of a "good" array.
Cons
Requires extra space for the frequency array, which is proportional to the length of the input array.
Solutions
Solution
public class Solution { public bool IsGood ( int [] nums ) { int n = nums . Length - 1 ; int [] cnt = new int [ 201 ]; foreach ( int x in nums ) { ++ cnt [ x ]; } if ( cnt [ n ] != 2 ) { return false ; } for ( int i = 1 ; i < n ; ++ i ) { if ( cnt [ i ] != 1 ) { return false ; } } return true ; } }class Solution {public boolean isGood(int[] nums) { int n = nums.length - 1; int[] cnt = new int[201]; for (int x : nums) { ++cnt[x]; } cnt[n] -= 2; for (int i = 1; i < n; ++i) { cnt[i] -= 1; } for (int x : cnt) { if (x != 0) { return false; } } return true; }}class Solution {public: bool isGood(vector<int> &nums) { int n = nums.size() - 1; vector<int> cnt(201); for (int x : nums) { ++cnt[x]; } cnt[n] -= 2; for (int i = 1; i < n; ++i) { --cnt[i]; } for (int x : cnt) { if (x) { return false; } } return true; }};class Solution: def isGood(self, nums: List[int]) -> bool: n = len(nums) - 1 cnt = Counter(nums) cnt[n] -= 2 for i in range(1, n): cnt[i] -= 1 return all(v == 0 for v in cnt . values())Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.