Check if Array is Good

Easy
993.

Check if Array is Good

Check if Array is Good is an easy coding problem on arrays, hash table and sorting, asked in Amazon, Google and TCS interviews.

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 <= 100
  • 1 <= nums[i] <= 200
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isGood = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • 1 <= nums[i] <= 200

Hints for Check if Array is Good

  1. Hint 1

    The length fixes n: an array of m elements can only match base[m - 1].

  2. Hint 2

    Then every value from 1 to n - 1 must appear once, and n twice.

  3. Hint 3

    Any value outside 1 … n disqualifies 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

  1. Set n = nums.length - 1; reject immediately if n < 1.
  2. Count occurrences, rejecting any value outside 1 … n.
  3. Require count[v] == 1 for v in 1 … n - 1 and count[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 n must be rejected, not silently ignored.
  • n = 1 is 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] == 2

Java

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