Check if Array is Good - Practice Coding Problems

Check if Array is Good - 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.

Input & Output

Example 1 — Valid Good Array

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

› Output: true

💡 Note: This array has length 4, so we expect base[3] = [1,2,3,3]. The input is a permutation of base[3], containing: 1 once, 2 once, and 3 twice.

Example 2 — Invalid Array

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

› Output: true

💡 Note: This array has length 4, so we expect base[3] = [1,2,3,3]. The input is a permutation of [1,2,3,3], just in different order.

Example 3 — Wrong Pattern

$ Input: nums = [1,1]

› Output: true

💡 Note: This array has length 2, so we expect base[1] = [1,1]. The input matches exactly.

Constraints

1 ≤ nums.length ≤ 100
1 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,1,3,3] with length 4

Expected Pattern

base[3] = [1,2,3,3] (any permutation)

Verification

Check if frequencies match: 1→1, 2→1, 3→2

Key Takeaway

🎯 Key Insight: A good array must contain numbers 1 to n-1 exactly once, plus n exactly twice

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that a good array must be a permutation of base[n] = [1,2,...,n-1,n,n]. Best approach uses frequency counting to verify the pattern in O(n) time. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count with Hash Map	O(n)	O(n)	Use hash map to count frequencies and verify pattern
Sort and Compare	O(n log n)	O(1)	Sort array and compare with expected base[n] pattern
Brute Force - Count Each Number	O(n²)	O(1)	Manually count occurrences of each expected number

Frequency Count with Hash Map — Algorithm Steps

Step 1: Count frequency of each number
Step 2: Check array length is n+1
Step 3: Verify frequencies match good array pattern

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Build frequency map: {1:1, 2:1, 3:2}

Verify Pattern

Check if frequencies match base[3] pattern

Result

All frequencies are correct

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* nums, int numsSize) {
    if (numsSize < 2) return false;
    
    int expectedMax = numsSize - 1;
    int freq[1001] = {0}; // Assuming nums[i] <= 1000
    int distinctCount = 0;
    
    // Count frequencies
    for (int i = 0; i < numsSize; i++) {
        if (freq[nums[i]] == 0) distinctCount++;
        freq[nums[i]]++;
    }
    
    // Check if we have exactly the right numbers
    if (distinctCount != expectedMax) {
        return false;
    }
    
    // Check frequencies match pattern
    for (int i = 1; i < expectedMax; i++) {
        if (freq[i] != 1) {
            return false;
        }
    }
    
    // Check that expectedMax appears exactly twice
    return freq[expectedMax] == 2;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    bool result = solution(nums, numsSize);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count frequencies plus O(n) to verify pattern

✓ Linear Growth

Space Complexity

O(n)

Hash map stores frequency count for up to n distinct numbers

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~15 min Avg. Time

340 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count with Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler