Check if Array is Good solution and explanation
Google
9 more videos on this problem
Leetcode | 2784. Check if Array is Good | Easy | Java SolutionDeveloper Docs · 5:08 · 1K views
2784. Check if Array is Good | Leetcode 2784 | BiWeekly 109Tech Courses · 3:19 · 981 views
2784. Check if Array is Good (Leetcode Easy)Programming Live with Larry · 2:39 · 540 views
2784. Check if Array is Good | Leetcode Daily - PythonLeetcode Daily · 5:04 · 372 views
Check if array is good | leetcode 2784 | hash mapAman Anand · 7:21 · 204 views
Check if Array is Good | LeetCode 2784Streak To Scale · 2:58 · 167 views
Boost Your Coding Skills: LeetCode 2784. Check if Array is Good Challenge in PythonvanAmsen · 3:54 · 161 views
Check if Array is Good | LeetCode 2784 - Pythonimpoldev · 4:46 · 133 views
leetcode 2784 | Check if Array is Good | Frequency counting | leetcode POTD | Easy solutionCode With Vick · 13:15 · 129 views
Master C++ with Real-Life Coding Challenge | Solve LeetCode 2784. Check if Array is GoodvanAmsen · 5:13 · 98 views
The problem
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
Approach overview
Problem 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 1: Frequency Matching Approach
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.
def is_good_array(nums):
from collections import Counter
count = Counter(nums)
max_num = max(nums)
if len(nums) != max_num + 1:
return False
for i in range(1, max_num):
if count[i] != 1:
return False
if count[max_num] != 2:
return False
return True
print(is_good_array([1, 3, 3, 2])) # Trueimport java.util.HashMap;
class Solution {
public boolean isGoodArray(int[] nums) {
HashMap<Integer, Integer> count = new HashMap<>();
int max = 0;
for (int num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
if (num > max) max = num;
}
if (nums.length != max + 1) return false;
for (int i = 1; i < max; i++) {
if (count.getOrDefault(i, 0) != 1) return false;
}
return count.getOrDefault(max, 0) == 2;
}
public static void main(String[] args) {
Solution s = new Solution();
int[] nums = {1, 3, 3, 2};
System.out.println(s.isGoodArray(nums)); // true
}
}#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;
bool isGoodArray(vector<int>& nums) {
unordered_map<int, int> count;
int max = 0;
for (int num : nums) {
count[num]++;
if (num > max) max = num;
}
if (nums.size() != max + 1) return false;
for (int i = 1; i < max; i++) {
if (count[i] != 1) return false;
}
if (count[max] != 2) return false;
return true;
}
int main() {
vector<int> nums = {1, 3, 3, 2};
cout << (isGoodArray(nums) ? "true" : "false") << endl;
return 0;
}function isGoodArray(nums) {
let count = {};
let max = 0;
for (let num of nums) {
if (!count[num]) count[num] = 0;
count[num]++;
if (num > max) max = num;
}
if (nums.length !== max + 1) return false;
for (let i = 1; i < max; i++) {
if (count[i] !== 1) return false;
}
return count[max] === 2;
}
console.log(isGoodArray([1, 3, 3, 2])); // true#include <stdbool.h>
#include <stdio.h>
#include <string.h>
bool isGoodArray(int* nums, int numsSize) {
int max = 0;
int count[201] = {0};
for (int i = 0; i < numsSize; i++) {
count[nums[i]]++;
if (nums[i] > max) max = nums[i];
}
if (numsSize != max + 1) return false;
for (int i = 1; i < max; i++) {
if (count[i] != 1) return false;
}
if (count[max] != 2) return false;
return true;
}
int main() {
int nums[] = {1, 3, 3, 2};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%s\n", isGoodArray(nums, size) ? "true" : "false");
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public bool IsGoodArray(int[] nums) {
Dictionary<int, int> count = new Dictionary<int, int>();
int max = 0;
foreach (int num in nums) {
if (!count.ContainsKey(num)) count[num] = 0;
count[num]++;
if (num > max) max = num;
}
if (nums.Length != max + 1) return false;
for (int i = 1; i < max; i++) {
if (!count.ContainsKey(i) || count[i] != 1) return false;
}
return count.TryGetValue(max, out int val) && val == 2;
}
static void Main() {
Solution solution = new Solution();
int[] nums = {1, 3, 3, 2};
Console.WriteLine(solution.IsGoodArray(nums)); // true
}
}The Python implementation uses the Counter class from the collections module to efficiently tally the count of each number. This is then checked against the condition that drives a good array.
Time Complexity: O(n), derived from using Counter and iterating through nums.
Space Complexity: O(n) due to storage required for Counter.
Approach 2: Sorting and Comparison Approach
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].
def is_good_array(nums):
nums.sort()
max_num = nums[-1]
if len(nums) != max_num + 1:
return False
for i in range(1, max_num):
if nums[i - 1] != i:
return False
return nums[max_num - 1] == max_num and nums[max_num] == max_num
print(is_good_array([1, 3, 3, 2])) # Trueimport java.util.Arrays;
class Solution {
public boolean isGoodArray(int[] nums) {
Arrays.sort(nums);
int max = nums[nums.length - 1];
if (nums.length != max + 1) return false;
for (int i = 1; i < max; i++) {
if (nums[i - 1] != i) return false;
}
return nums[max - 1] == max && nums[max] == max;
}
public static void main(String[] args) {
Solution s = new Solution();
int[] nums = {1, 3, 3, 2};
System.out.println(s.isGoodArray(nums)); // true
}
}#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool isGoodArray(vector<int>& nums) {
sort(nums.begin(), nums.end());
int max = nums.back();
if (nums.size() != max + 1) return false;
for (int i = 1; i < max; i++) {
if (nums[i - 1] != i) return false;
}
return nums[max - 1] == max && nums[max] == max;
}
int main() {
vector<int> nums = {1, 3, 3, 2};
cout << (isGoodArray(nums) ? "true" : "false") << endl;
return 0;
}function isGoodArray(nums) {
nums.sort((a, b) => a - b);
let max = nums[nums.length - 1];
if (nums.length !== max + 1) return false;
for (let i = 1; i < max; i++) {
if (nums[i - 1] !== i) return false;
}
return nums[max - 1] === max && nums[max] === max;
}
console.log(isGoodArray([1, 3, 3, 2])); // true#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
bool isGoodArray(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), compare);
int max = nums[numsSize - 1];
if (numsSize != max + 1) return false;
for (int i = 1; i < max; i++) {
int index = i - 1;
if (nums[index] != i) return false;
}
if (nums[numsSize - 2] != max || nums[numsSize - 1] != max) return false;
return true;
}
int main() {
int nums[] = {1, 3, 3, 2};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%s\n", isGoodArray(nums, size) ? "true" : "false");
return 0;
}using System;
class Solution {
public bool IsGoodArray(int[] nums) {
Array.Sort(nums);
int max = nums[nums.Length - 1];
if (nums.Length != max + 1) return false;
for (int i = 1; i < max; i++) {
if (nums[i - 1] != i) return false;
}
return nums[max - 1] == max && nums[max] == max;
}
static void Main() {
Solution solution = new Solution();
int[] nums = {1, 3, 3, 2};
Console.WriteLine(solution.IsGoodArray(nums)); // true
}
}Python's built-in sort is leveraged, and a straightforward comparison confirms the sorted sequence matches base[n].
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is done in-place.
Approach 3: Counting
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;- For
1 leq i leq n-1, it holds thatcnt[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.
function isGood(nums: number[]): boolean {
const n = nums.length - 1;
const cnt: number[] = Array(201).fill(0);
for (const x of nums) {
++cnt[x];
}
if (cnt[n] !== 2) {
return false;
}
for (let i = 1; i < n; ++i) {
if (cnt[i] !== 1) {
return false;
}
}
return true;
}func isGood(nums []int) bool {
n := len(nums) - 1
cnt := [201]int{}
for _, x := range nums {
cnt[x]++
}
if cnt[n] != 2 {
return false
}
for i := 1; i < n; i++ {
if cnt[i] != 1 {
return false
}
}
return true
}Complexity comparison
| Approach | Complexity |
|---|---|
| Frequency Matching Approach | Time Complexity: O(n), derived from using |
| Sorting and Comparison Approach | Time Complexity: O(n log n) due to sorting. |
| Counting | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Check if Array is Good easy or hard?
Check if Array is Good is classified as an Easy problem. The logic mainly involves recognizing the expected sequence [1, 2, ..., n-1, n-1] and verifying element frequencies or comparing against a sorted array.
Check if Array is Good Python/Java solution
Python and Java solutions typically implement the frequency approach using a dictionary or integer array for counting. Both languages can solve the problem in O(n) time by validating counts of numbers from 1 to n-1.
How to solve Check if Array is Good in O(n)?
Use a frequency array or hash map. Count occurrences of each value while ensuring numbers stay within the range 1 to n-1. After counting, verify that numbers 1 through n-2 appear exactly once and n-1 appears exactly twice.
What is the best approach for Check if Array is Good?
The best approach is frequency matching using a hash map or counting array. Count how many times each number appears and verify that values 1 to n-2 appear once while n-1 appears twice. This runs in O(n) time with O(n) space and directly validates the required structure.
Is Check if Array is Good asked at Google/Amazon/Meta?
Problems involving frequency counting and array validation patterns appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the underlying skills—hash table counting and constraint validation—are common interview topics.
What data structure is used in Check if Array is Good?
A hash table or counting array is commonly used to store frequencies of each number. This allows constant-time updates and checks while scanning the array, enabling the optimal O(n) solution.
What is the time complexity of Check if Array is Good?
The optimal solution runs in O(n) time by scanning the array once and tracking frequencies in a hash table. A sorting-based solution takes O(n log n) time because the array must be sorted before verifying the expected sequence.