# Check if Array is Good
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-array-is-good)
Canonical: https://scaleengineer.com/dsa/problems/check-if-array-is-good
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## 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 <= 100`
* `1 <= num[i] <= 200`

# Approaches
## Sorting and Full Comparison
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.
**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.
**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 the `base` array, in addition to the space used by the sorting algorithm.
### Explanation
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.

```java
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);
    }
}
```
### Algorithm
- Let `L` be the length of the input array `nums`.
- The target array `base[n]` has a length of `n + 1`. For `nums` to be a permutation of `base[n]`, their lengths must be equal. Thus, `n` must be `L - 1`.
- If `L <= 1`, it cannot be a good array, so we return `false`.
- Create the expected `base[n]` array, which is `[1, 2, ..., n-1, n, n]`.
- Sort the input array `nums` in non-decreasing order.
- Compare the sorted `nums` array with the `base[n]` array. If they are identical, `nums` is a good array. Otherwise, it is not.

## Sorting and In-place Check
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.
**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.
**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.
### Explanation
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:
1.  Sort `nums`.
2.  The first `n` elements of the sorted array should be `1, 2, ..., n`. We can check this by looping from `i = 0` to `n-1` and verifying that `nums[i] == i + 1`.
3.  The last element of the sorted array, `nums[n]`, must also be `n`.

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.

```java
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;
    }
}
```
### Algorithm
- Let `L` be the length of `nums` and set `n = L - 1`.
- If `L <= 1`, return `false`.
- Sort the input array `nums`.
- A sorted "good" array must look like `[1, 2, ..., n-1, n, n]`.
- Check if `nums[i]` equals `i + 1` for `i` from `0` to `n-1`.
- Check if the last element `nums[n]` equals `n`.
- If all these conditions are met, the array is good; otherwise, it's not.

## Frequency Counting
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Let `L` be the length of `nums` and set `n = L - 1`.
- If `L <= 1`, return `false`.
- Create a frequency array, `counts`, of size `n + 1` to store the occurrences of numbers from 1 to `n`.
- Iterate through `nums`. For each number `num`:
    - If `num` is outside the range `[1, n]`, the array cannot be good, so return `false`.
    - Increment the count for `num` in the `counts` array.
- After populating the counts, verify them:
    - Check if `counts[i]` is `1` for all `i` from `1` to `n-1`.
    - Check if `counts[n]` is `2`.
- If any check fails, return `false`. Otherwise, return `true`.

# Solutions
### CSharp

```csharp
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 ; } }
```

### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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())

```