Scale Engineer

Check if Array is Good

Easy
#2496Time: O(L log L), where L is the length of `nums`. The sorting step `Arrays.sort(nums)` is the dominant factor in the time complexity.Space: O(L), where L is the length of `nums`. This is for storing the `base` array. The sorting algorithm might also use `O(log L)` to `O(L)` space, depending on the implementation.
Algorithms
Sorting
Data structures
ArrayHash Table

Prompt

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.

 

Example 1:

Input: nums = [2, 1, 3]
Output: false
Explanation: Since the maximum element of the array is 3, the only candidate n for which this array could be a permutation of base[n], is n = 3. However, base[3] has four elements but array nums has three. Therefore, it can not be a permutation of base[3] = [1, 2, 3, 3]. So the answer is false.

Example 2:

Input: nums = [1, 3, 3, 2]
Output: true
Explanation: Since the maximum element of the array is 3, the only candidate n for which this array could be a permutation of base[n], is n = 3. It can be seen that nums is a permutation of base[3] = [1, 2, 3, 3] (by swapping the second and fourth elements in nums, we reach base[3]). Therefore, the answer is true.

Example 3:

Input: nums = [1, 1]
Output: true
Explanation: Since the maximum element of the array is 1, the only candidate n for which this array could be a permutation of base[n], is n = 1. It can be seen that nums is a permutation of base[1] = [1, 1]. Therefore, the answer is true.

Example 4:

Input: nums = [3, 4, 4, 1, 2, 1]
Output: false
Explanation: Since the maximum element of the array is 4, the only candidate n for which this array could be a permutation of base[n], is n = 4. However, base[4] has five elements but array nums has six. Therefore, it can not be a permutation of base[4] = [1, 2, 3, 4, 4]. So the answer is false.

 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= num[i] <= 200

Approaches

3 approaches with complexity analysis and trade-offs.

This approach relies on the property that two arrays which are permutations of each other will become identical when sorted. We first construct the theoretical base[n] array that nums should be a permutation of. Then, we sort the input nums and compare it element by element with the constructed base[n] array.

Algorithm

  • Let L be the length of the input array nums.
  • The target array base[n] has a length of n + 1. For nums to be a permutation of base[n], their lengths must be equal. Thus, n must be L - 1.
  • If L <= 1, it cannot be a good array, so we return false.
  • Create the expected base[n] array, which is [1, 2, ..., n-1, n, n].
  • Sort the input array nums in non-decreasing order.
  • Compare the sorted nums array with the base[n] array. If they are identical, nums is a good array. Otherwise, it is not.

Walkthrough

The core idea is to transform the permutation check into an equality check. A "good" array is a permutation of base[n] = [1, 2, ..., n-1, n, n]. The length of base[n] is n+1. So, for a given input nums of length L, the only candidate for n is L-1.

First, we determine this value of n. Then, we explicitly build the base[n] array. After that, we sort the input array nums. If nums is indeed a permutation of base[n], its sorted version must be identical to base[n] (which is already sorted by construction). We can then use a standard library function to compare the two arrays for equality.

For example, if nums = [1, 3, 3, 2], its length is 4, so n=3. The base[3] array is [1, 2, 3, 3]. After sorting, nums becomes [1, 2, 3, 3], which matches base[3]. Thus, the array is good.

import java.util.Arrays; class Solution {    public boolean isGood(int[] nums) {        int len = nums.length;        if (len <= 1) {            return false;        }        int n = len - 1;         int[] base = new int[len];        for (int i = 0; i < n; i++) {            base[i] = i + 1;        }        base[n] = n;         Arrays.sort(nums);         return Arrays.equals(nums, base);    }}

Complexity

Time

O(L log L), where L is the length of `nums`. The sorting step `Arrays.sort(nums)` is the dominant factor in the time complexity.

Space

O(L), where L is the length of `nums`. This is for storing the `base` array. The sorting algorithm might also use `O(log L)` to `O(L)` space, depending on the implementation.

Trade-offs

Pros

  • The logic is straightforward and easy to understand.

  • Implementation is simple, especially with built-in sorting and array comparison functions.

Cons

  • This approach has a time complexity of O(L log L), which is not optimal.

  • It requires extra space of O(L) to store the base array, in addition to the space used by the sorting algorithm.

Solutions

public class Solution { public bool IsGood ( int [] nums ) { int n = nums . Length - 1 ; int [] cnt = new int [ 201 ]; foreach ( int x in nums ) { ++ cnt [ x ]; } if ( cnt [ n ] != 2 ) { return false ; } for ( int i = 1 ; i < n ; ++ i ) { if ( cnt [ i ] != 1 ) { return false ; } } return true ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem