Leetcode 2784: Check if Array is Good

Input: The input consists of an integer array nums.

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

Constraints:

• 1 <= nums.length <= 100

• 1 <= nums[i] <= 200

Output: Return true if nums can be rearranged to form any base[n] array; otherwise, return false.

Example: Output: true

Constraints:

Goal: Check if nums matches the structure of a valid base[n] array.

Steps:

• Identify the maximum value n in nums.

• Verify that nums contains exactly two occurrences of n.

• Verify that nums contains all integers from 1 to n-1 exactly once.

• Ensure the length of nums is n+1.

Goal: Constraints imposed on the input values and size.

Steps:

• 1 <= nums.length <= 100

• 1 <= nums[i] <= 200

Assumptions:

• The input array may contain duplicates.

• The maximum value in the array determines the candidate base[n].

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

• Explanation: The array matches base[4] = [1, 2, 3, 4, 4], so the output is true.

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

• Explanation: The array does not match any valid base[n] structure, so the output is false.

Approach: Iterate through the array to validate its structure against a possible base[n].

Observations:

• The array must have a specific structure to be valid.

• The maximum value in nums determines the potential base[n].

• We need to check counts of numbers in nums to validate the match.

Steps:

• Count occurrences of each number in nums.

• Identify the maximum value n in nums.

• Validate the array length matches n+1.

• Ensure the number n appears exactly twice.

• Ensure all numbers from 1 to n-1 appear once.

Empty Inputs:

• Input: nums = []. Output: false.

Large Inputs:

• Input: nums = [1, 2, ..., 99, 100, 100]. Output: true.

Special Values:

• Input: nums = [1, 1]. Output: true.

Constraints:

• Handling arrays where nums.length != n+1 should return false.

bool isGood(vector<int>& nums) {
    int cnt[201] = {}, n = nums.size() - 1;
    for (auto num : nums)
        ++cnt[num];
    return all_of(begin(cnt) + 1, begin(cnt) + n, [](int c){ return c == 1; }) && cnt[n] == 2;
}

1 : Function Declaration

bool isGood(vector<int>& nums) {

This line defines the function `isGood` which takes a vector of integers `nums` and returns a boolean value indicating if the array meets the specified condition.

2 : Variable Initialization

    int cnt[201] = {}, n = nums.size() - 1;

Here, an array `cnt` of size 201 is initialized to track the frequency of each number in the `nums` vector. The variable `n` stores the size of the vector minus one, representing the largest number in the vector.

3 : Looping

    for (auto num : nums)

This for-each loop iterates through each element `num` in the `nums` vector.

4 : Frequency Update

        ++cnt[num];

For each number `num`, its corresponding frequency in the `cnt` array is incremented by one.

5 : Return Statement

    return all_of(begin(cnt) + 1, begin(cnt) + n, [](int c){ return c == 1; }) && cnt[n] == 2;

This return statement checks two conditions: 1) that all elements in the `cnt` array (except the last one) occur exactly once, using `all_of`, and 2) that the largest number occurs exactly twice. If both conditions are true, the function returns true, otherwise, it returns false.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: Iterate through the array and validate counts.

Best Case: O(1)

Worst Case: O(n)

Description: Use a count array or hashmap to store counts.

Leetcode 2784: Check if Array is Good

Explore →