LeetCode Solution: 2784. Check if Array is Good

#leetcode #dsa #programming #tutorial

Cracking LeetCode 2784: Is This Array "Good"? Let's Find Out!

Hey everyone! Vansh2710 here, your friendly neighborhood competitive programmer and technical writing enthusiast! Today, we're diving into a fun little LeetCode problem that's perfect for beginners to sharpen their logical thinking: 2784. Check if Array is Good.

Don't let the "permutation" jargon scare you. We'll break it down step by step and discover an elegant solution together. Ready to level up your LeetCode game? Let's go!

🚀 Problem Explanation: What Makes an Array "Good"?

Imagine you have a special kind of array called base[n]. This base[n] array always looks like this:

[1, 2, ..., n - 1, n, n]

In plain English, it's an array of length n + 1 that contains:

All numbers from 1 up to n - 1 appear exactly once.
The number n appears exactly twice.

For example:

If n = 1, then base[1] = [1, 1]. (Length 1+1=2)
If n = 3, then base[3] = [1, 2, 3, 3]. (Length 3+1=4)
If n = 5, then base[5] = [1, 2, 3, 4, 5, 5]. (Length 5+1=6)

The problem asks us to determine if a given array nums is a permutation of one of these base[n] arrays. "Permutation" just means it contains the same numbers, just possibly in a different order.

Let's look at the examples:

nums = [2, 1, 3]
- The largest number is 3. So, if this were a base[n] array, n must be 3.
- base[3] should be [1, 2, 3, 3], which has 4 elements.
- But nums has only 3 elements. So, it cannot be base[3]. Output: false.
nums = [1, 3, 3, 2]
- The largest number is 3. So, n must be 3.
- base[3] is [1, 2, 3, 3].
- nums also has 4 elements, just like base[3].
- Can we rearrange [1, 3, 3, 2] to get [1, 2, 3, 3]? Yes! They contain the exact same numbers with the same counts. Output: true.
nums = [3, 4, 4, 1, 2, 1]
- Largest number is 4. So, n must be 4.
- base[4] should be [1, 2, 3, 4, 4], which has 5 elements.
- But nums has 6 elements. It's too long! Output: false.

See? It's all about checking the elements, their counts, and the array's length!

💡 Intuition: The "Aha!" Moment

When you're trying to figure out if an array is a "permutation" of another specific array structure, the first thing that often comes to mind is sorting. If two arrays are permutations of each other, they will be identical once sorted.

So, if nums is a "good" array, after sorting it, it should exactly match [1, 2, ..., n - 1, n, n].

But what is n? The problem examples give us a HUGE hint: n is always the maximum value present in the nums array. If the nums array is supposed to be base[n], then n is the highest number appearing twice, and n-1 is the next highest. So, n must be the largest element.

Once we figure out n (by finding the maximum value in nums), we can determine two key properties that nums must satisfy:

Length Check: nums must have n + 1 elements.
Content Check: After sorting, nums must look exactly like [1, 2, ..., n - 1, n, n].

If nums passes both these checks, it's a "good" array!

🧠 Approach: Step-by-Step Logic

Let's put our intuition into a concrete plan:

Determine the Candidate n:
- Find the maximum element in the input array nums. Let's call this max_val. This max_val is our candidate n from base[n].
Initial Length Check:
- The base[n] array always has a length of n + 1.
- Check if the nums.size() (the actual number of elements in nums) is equal to max_val + 1.
- If nums.size() is not equal to max_val + 1, then nums cannot be a permutation of base[max_val]. Immediately return false.
Sort the Array:
- Sort the nums array in non-decreasing order. This makes it easy to check the pattern [1, 2, ..., n - 1, n, n].
Verify Elements in Order:
- After sorting, we expect the elements to be 1, 2, ..., max_val - 1, max_val, max_val.
- Loop from i = 0 up to max_val - 2 (which means checking elements nums[0] through nums[max_val - 2]).
- In this loop, for each i, check if nums[i] is equal to i + 1. If it's not, it means we don't have the sequence 1, 2, 3, .... Return false.
- Special Case: What if max_val is 1? If max_val = 1, then base[1] = [1, 1]. The loop i from 0 to max_val - 2 (i.e., 0 to -1) won't run, which is correct. We only need to check the two 1s.
Verify the Duplicate n (or max_val):
- After the loop, we need to check the last two elements. These should both be max_val.
- Since nums.size() is max_val + 1, the elements are at indices 0 to max_val.
- So, we need to check if nums[max_val - 1] is equal to max_val AND nums[max_val] is equal to max_val.
- If both these conditions are true, then nums has the required duplicate max_val. If not, return false.
All Checks Passed:
- If we've made it this far, it means nums has the correct length, and its sorted elements match the base[max_val] pattern. Return true.

This approach covers all the conditions systematically and efficiently!

💻 Code: Bringing the Logic to Life

Here's the C++ implementation of our approach:

#include <vector>
#include <algorithm> // Required for std::sort and std::max_element

class Solution {
public:
    bool isGood(std::vector<int>& nums) {
        int current_size = nums.size();

        // Step 1: Determine the candidate 'n' (max_val)
        // If the array is empty, it can't be good (constraints say nums.length >= 1)
        // If only one element, max_element will still work.
        int max_val = 0;
        for (int x : nums) {
            if (x > max_val) {
                max_val = x;
            }
        }
        // An alternative using std::max_element (requires <algorithm>):
        // int max_val = *std::max_element(nums.begin(), nums.end());


        // Step 2: Initial Length Check
        // base[max_val] has length max_val + 1
        if (current_size != max_val + 1) {
            return false;
        }

        // Step 3: Sort the Array
        std::sort(nums.begin(), nums.end());

        // Step 4: Verify Elements 1 to (max_val - 1)
        // Loop up to max_val - 1 (exclusive, so indices 0 to max_val - 2)
        // For example, if max_val = 3, we check nums[0] == 1, nums[1] == 2.
        for (int i = 0; i < max_val - 1; ++i) {
            if (nums[i] != i + 1) {
                return false;
            }
        }

        // Step 5: Verify the Duplicate 'n' (max_val)
        // The last two elements should both be max_val.
        // These are at indices max_val - 1 and max_val (since current_size = max_val + 1)
        if (nums[max_val - 1] != max_val || nums[max_val] != max_val) {
            return false;
        }

        // Step 6: All Checks Passed
        return true;
    }
};

⏱️ Time & Space Complexity Analysis

Let's break down the efficiency of our solution:

Time Complexity:
- Finding max_val: We iterate through nums once. This takes O(N) time, where N is nums.size().
- Sorting nums: Using std::sort on a std::vector takes O(N log N) time on average.
- Checking elements after sorting: We loop through nums at most N times (specifically max_val times, which is roughly N). This takes O(N) time.
- Overall: The dominant factor is the sorting step. Therefore, the total time complexity is O(N log N).
Space Complexity:
- max_val and current_size variables: These use O(1) constant space.
- std::sort: For std::vector, std::sort typically uses an introspection sort algorithm, which has O(log N) auxiliary space complexity for its recursive calls (or O(N) in worst-case for heapsort partition, but often considered in-place or O(log N) for the stack). For competitive programming contexts, it's often effectively treated as O(1) additional space if it sorts in-place. Let's consider it as O(1) (ignoring recursion stack space if small enough, or O(log N) more precisely for a typical implementation).

🎯 Key Takeaways

Deconstruct the Problem: Break down complex definitions (like base[n]) into simpler rules (length, distinct elements, duplicate element).
Leverage Hints: The example explanations often provide crucial clues, like how to determine n (it's the max element!).
Sorting is Your Friend: For problems involving permutations or specific ordered structures, sorting is often the most straightforward way to normalize the input for easy validation.
Edge Cases Matter: Always consider small n values (like n=1) to ensure your logic holds. Our loop condition i < max_val - 1 correctly handles max_val = 1 by not running the loop, which is perfect as base[1] only needs [1, 1] checks.
Systematic Checks: Go through each requirement (length, distinct elements, duplicate elements) one by one. If any check fails, you can immediately return false.

This problem is a fantastic warm-up to understanding how to translate descriptive array properties into a clear, implementable algorithm. Keep practicing!

Vansh2710
Published: 2026-05-14 22:44:58