2784. Check if Array is Good

Time: O(n)

Space: O(n)

Intuition

A "good" array must have a specific structure: indices [1, n-1] each paired with exactly one value, and index n paired with two values (forming a square pattern). Counting frequencies and validating against this structure is straightforward.

Algorithm

1Count the frequency of each element using a hash map.
2Check that all integers from 1 to n-1 appear exactly once.
3Check that n (the maximum expected value) appears exactly twice.
4If all checks pass, the array is good; otherwise, it's not.

Example Walkthrough

Input: nums = [1, 3, 4, 2, 2]

1.n = 5 - 1 = 4.
2.Count: {1:1, 3:1, 4:1, 2:2}.
3.Check [1, 3]: all present with freq=1.
4.Check 4: present with freq=2.
5.All conditions met → good array.

Output: true

Common Pitfalls

•Do not confuse "good" with "sorted". A good array has a specific frequency pattern, not order.
•Ensure that n appears exactly twice, not just at least twice.
•Edge case: if the array has fewer than 2 elements, it cannot be good (since n appears twice).

2784.cs

// Approach: Count the frequency of each element. A "good" array has exactly [1, n-1] appearing once each, and n appearing twice.
// Check frequency counts against these constraints.
// Time: O(n) Space: O(n)

public class Solution
{
    public bool IsGood(int[] nums)
    {
        int n = nums.Length - 1;
        var count = new Dictionary<int, int>();
        foreach (var num in nums)
        {
            if (count.ContainsKey(num))
                count[num]++;
            else
                count[num] = 1;
        }
        for (int i = 1; i < n; i++)
        {
            if (!count.ContainsKey(i) || count[i] != 1)
                return false;
        }

        return count.ContainsKey(n) && count[n] == 2;
    }
}

Was this solution helpful?