Watch 9 video solutions for Check if Array is Good, a easy level problem involving Array, Hash Table, Sorting. This walkthrough by Tech Courses has 871 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |