Check if Array is Good

Check if Array is Good

What is this problem about?

The "Check if Array is Good interview question" asks you to verify if an array of length $n+1$ contains exactly the numbers $1, 2, ..., n-1$ once, and the number $n$ exactly twice. For example, if $n=3$, the "good" array would be [1, 2, 3, 3].

Why is this asked in interviews?

Bloomberg asks the "Check if Array is Good coding problem" as a basic test of array manipulation and counting. It evaluates whether you can verify a specific permutation-like property. It checks if you can use "Hash Table interview pattern" or "Sorting" to validate the distribution of numbers in an array.

Algorithmic pattern used

This problem follows the Frequency Counting or Sorting pattern.

1. Frequency Array:
   • Find the maximum value $n$ in the array.
   • The array length must be $n+1$.
   • Count occurrences of each number.
   • Check if $1$ to $n-1$ appear once, and $n$ appears twice.
2. Sorting: Sort the array and check if arr[i] == i+1 for all $i < n$, and arr[n] == n.

Example explanation

Array: [1, 3, 3, 2]

1. Length is 4. Max possible $n$ should be $4-1=3$.
2. Sorted: [1, 2, 3, 3].
3. $i=0: 1 == 1$.
4. $i=1: 2 == 2$.
5. $i=2: 3 == 3$.
6. $i=3: 3 == 3$. Result: True.

Common mistakes candidates make

• Wrong Length: Forgetting to check if the length of the array is exactly max_val + 1.
• Duplicate Logic: Checking if the array contains $1..n$ but forgetting that $n$ must specifically appear twice, not any other number.
• Off-by-one: Mistakes in loop boundaries when checking the $1$ to $n-1$ sequence.

Interview preparation tip

When checking if an array contains a specific set of numbers, think about using a frequency array if the values are small, or sorting if you need a constant space solution (though sorting modifies the input). This is a core "Array interview pattern."