Skip to main content
Talentd

Check if Array is Good - Solution & Explanation

EasyArrayHash TableSorting19 min readAsked at: Microsoft, Google, Bloomberg
Practice this problem

Problem Statement

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 <= 100
  • 1 <= 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.

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].

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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).

Try this approach in the editor →

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].

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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:

  1. cnt[n] = 2, i.e., the largest element in the array appears twice;
  2. For 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.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Frequency Matching Approach

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).

Sorting and Comparison Approach

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.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Frequency Matching (Hash Table)O(n)O(n)Best general solution. Fast single pass with explicit frequency validation.
Sorting and ComparisonO(n log n)O(1)–O(log n)Useful when sorting is already required or when avoiding hash maps.

Video Solution

Leetcode | 2784. Check if Array is Good | Easy | Java Solution • Developer Docs • 1,020 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Check if Array is Good with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays