Check if Array is Good

Easy

Asked by:

5 views

Topics:

Arrays

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array, and what is the range of possible integer values within the array?
Can the input array be empty or null?
Are there any constraints on modifying the input array in place, or should I create a copy for sorting?
If the array is not 'good' according to the definition, what should I return?
Are duplicate numbers allowed in the array, and how should they be handled when determining if the array is 'good'?

Brute Force Solution

Approach

The brute force approach to determine if an array is 'good' involves checking every possible arrangement of its elements. Essentially, we examine each potential combination to see if it fulfills the condition of being a 'good' array. This involves going through all possible scenarios, one by one.

Here's how the algorithm would work step-by-step:

Consider the first element of the array.
Compare it with every other element in the array to see if it meets some defined criteria (this comparison depends on what 'good' means for your specific array).
Repeat this comparison process for the second element, the third element, and so on, until you've compared every element with every other element.
Keep track of how many times the defined criteria are met during all these comparisons.
After checking all the pairs, decide if the array is 'good' based on whether the number of successful comparisons matches the criteria required to qualify as a 'good' array.

Code Implementation

def is_array_good_brute_force(number_array):
    array_length = len(number_array)
    successful_comparisons_count = 0

    # Iterate through each element of the array
    for first_index in range(array_length):
        for second_index in range(array_length):

            # Ensure we are not comparing the same element to itself
            if first_index != second_index:

                # Increment count if comparison passes
                if number_array[first_index] < number_array[second_index]:
                    successful_comparisons_count += 1

    # Defining 'good' as number of successful comparison being more than half of possible comparisons
    if successful_comparisons_count > (array_length * (array_length - 1)) / 2:
        return True

    # If it doesn't meet the condition, return false
    return False

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach involves comparing each element of the input array with every other element. For an array of size n, the outer loop iterates n times, and the inner comparison (or inner loop, although not explicitly described with loop syntax) effectively iterates approximately n times for each element in the outer loop. This results in roughly n * n comparisons or operations. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The provided plain English explanation describes a brute-force approach that iterates through the array, comparing each element with every other element. The algorithm only requires a few variables to keep track of indices or the count of successful comparisons. No auxiliary data structures that scale with the input size N are created. Therefore, the space complexity is constant.

Optimal Solution

Approach

The key insight is to recognize that the array is considered 'good' only if you can rearrange it so the most frequent number appears exactly as many times as its value. We can determine if rearrangement is possible by comparing the number of times a value appears in the array with the number itself.

Here's how the algorithm would work step-by-step:

First, count how many times each distinct number appears in the array.
Then, look at each number and its count. If the number is bigger than how many times it appears, the array can't be rearranged to be good.
If you find even one number that's bigger than its count, the array is not good, so the answer is no. If every number satisfies the rule (number count is larger or equal to the number itself), the array is good, and the answer is yes.

Code Implementation

def is_array_good(numbers):
    number_counts = {}
    for number in numbers:
        number_counts[number] = number_counts.get(number, 0) + 1

    # Iterate through distinct numbers to see if rearrangement is possible
    for number, count in number_counts.items():

        # If the number appears fewer times than its value, array isn't 'good'
        if number > count:
            return False

    return True

Big(O) Analysis

Time Complexity

O(n) – Counting the frequency of each number in the array involves iterating through the array once, which takes O(n) time where n is the number of elements in the array. After this counting phase, we iterate through the unique numbers found and compare them with their counts. In the worst case, every element is a unique number, making the size of this loop n. The complexity is therefore dominated by the initial O(n) frequency counting loop and a subsequent loop of size at most n. Hence, the overall time complexity of the algorithm is O(n).

Space Complexity

O(N) – The algorithm uses a hash map (or dictionary) to count the frequency of each distinct number in the input array. In the worst-case scenario, all N elements in the array are distinct, which means the hash map could store up to N key-value pairs, where N is the number of elements in the input array. Therefore, the auxiliary space used by the hash map grows linearly with the input size N. Consequently, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return false immediately as an empty array cannot satisfy the condition.
Array with one element	Return true if the single element is 0, false otherwise, as n-1 would be 0.
Array with all elements being the same value (e.g., all 0s)	If the array's length is 'n', and the last element after sorting is 'n-1', then it's a good array, otherwise, it is not.
Array with negative numbers	The sorting step will handle negative numbers correctly, placing them at the beginning of the sorted array; we just need to compare the last element with array length minus one.
Array with large integers that could potentially cause integer overflow if summed or multiplied.	The comparison logic only involves checking equality with the sorted array's last element and the array length minus one, so overflow is not a direct concern.
Array already sorted in non-decreasing order	The algorithm should still correctly check if the last element (nums[n-1]) is equal to n-1.
Array sorted in descending order	After sorting in non-decreasing order, the logic will then compare the new last element and see if that equals length-1.
Arrays containing duplicates of the number equal to (n-1)	Sorting will place all such duplicates before the last element. The solution only relies on the single last element equaling n-1 after sorting.

Null or empty input array

How to Handle:

Return false immediately as an empty array cannot satisfy the condition.

Array with one element

How to Handle:

Return true if the single element is 0, false otherwise, as n-1 would be 0.

Array with all elements being the same value (e.g., all 0s)

How to Handle:

If the array's length is 'n', and the last element after sorting is 'n-1', then it's a good array, otherwise, it is not.

Array with negative numbers

How to Handle:

The sorting step will handle negative numbers correctly, placing them at the beginning of the sorted array; we just need to compare the last element with array length minus one.

Array with large integers that could potentially cause integer overflow if summed or multiplied.

How to Handle:

The comparison logic only involves checking equality with the sorted array's last element and the array length minus one, so overflow is not a direct concern.

Array already sorted in non-decreasing order

How to Handle:

The algorithm should still correctly check if the last element (nums[n-1]) is equal to n-1.

Array sorted in descending order

How to Handle:

After sorting in non-decreasing order, the logic will then compare the new last element and see if that equals length-1.

Arrays containing duplicates of the number equal to (n-1)

How to Handle:

Sorting will place all such duplicates before the last element. The solution only relies on the single last element equaling n-1 after sorting.