Check if Array is Good — Solution in Python, Java & C++
Check if Array is Good solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Check if Array is Good is an easy coding problem on arrays, hash table and sorting, asked in Amazon, Google and TCS interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Sorting
- Asked at: Amazon, Google, TCS
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
For an integer n, the array base[n] is [1, 2, …, n - 1, n, n] — the numbers 1 through n in order, with n appearing twice, so it has n + 1 elements.
Return true if nums is a permutation of base[n] for some n.
Example 1
Input: nums = [2,1,3]
Output: false
Explanation: Length 3 implies `n = 2`, so `base[2] = [1,2,2]`, which this is not.
Example 2
Input: nums = [1,3,3,2]
Output: true
Explanation: A permutation of `base[3] = [1,2,3,3]`.
Example 3
Input: nums = [1,1]
Output: true
Explanation: `base[1] = [1,1]`.
Constraints
1 <= nums.length <= 1001 <= nums[i] <= 200
Hints for Check if Array is Good
Hint 1
The length fixes
n: an array ofmelements can only matchbase[m - 1].Hint 2
Then every value from 1 to
n - 1must appear once, andntwice.Hint 3
Any value outside
1 … ndisqualifies the array at once.
How to solve Check if Array is Good
The length determines n = nums.length - 1. Count the values and check the exact multiset: 1 … n - 1 once each and n twice.
Approach
- Set
n = nums.length - 1; reject immediately ifn < 1. - Count occurrences, rejecting any value outside
1 … n. - Require
count[v] == 1forvin1 … n - 1andcount[n] == 2.
Why it works
Fixing n from the length first is what makes the check a single scan — without it there is no candidate to compare against. The range check inside the counting loop also keeps the count array in bounds, since values may be as large as 200 while n may be much smaller.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Values above
nmust be rejected, not silently ignored. n = 1is the special case[1,1], where the "once each" range is empty.- Sorting and comparing also works, but the counts are clearer.
Reference solution
Python
from typing import List
from collections import Counter
def isGood(nums: List[int]) -> bool:
n = len(nums) - 1
if n < 1:
return False
count = Counter(nums)
if any(v < 1 or v > n for v in nums):
return False
for v in range(1, n):
if count[v] != 1:
return False
return count[n] == 2Java
public static boolean isGood(int[] nums) {
int n = nums.length - 1;
if (n < 1) return false;
int[] count = new int[n + 1];
for (int v : nums) {
if (v < 1 || v > n) return false;
count[v]++;
}
for (int v = 1; v < n; v++) if (count[v] != 1) return false;
return count[n] == 2;
}C++
bool isGood(vector<int>& nums) {
int n = (int) nums.size() - 1;
if (n < 1) return false;
vector<int> count(n + 1, 0);
for (int v : nums) {
if (v < 1 || v > n) return false;
count[v]++;
}
for (int v = 1; v < n; v++) if (count[v] != 1) return false;
return count[n] == 2;
}JavaScript
var isGood = function(nums) {
var n = nums.length - 1, i;
if (n < 1) return false;
var count = [];
for (i = 0; i <= n; i++) count.push(0);
for (i = 0; i < nums.length; i++) {
if (nums[i] < 1 || nums[i] > n) return false;
count[nums[i]]++;
}
for (var v = 1; v < n; v++) if (count[v] !== 1) return false;
return count[n] === 2;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets