Understanding the Good Array Problem

The HackerRank problem asks you to count how many elements in an array are "good." An element is considered good if, after removing it, all the remaining elements are equal. It sounds simple enough on paper, but the implementation has a few quirks that trip people up. Here is the approach. First, you need to know what the majority value is in the array. If you remove one element and all remaining elements must be equal, then that single value is the only possible candidate for the result. The most frequent element in the array is your starting point, because it's the only value that can satisfy the condition after a deletion. My first attempt at this was naive. I literally removed each element one by one and checked if all remaining were equal. That is O(n^2), which fails on anything beyond small inputs. The correct approach runs in O(n) by doing two passes.

The first pass counts frequencies using a hash map or frequency array. The second pass checks each candidate removal. Here is the logic breakdown: If the array has only one unique element, every position is good, so the answer is n. If there are exactly two unique elements, the more frequent one must appear count - 1 times, and the less frequent one must appear exactly once. If those conditions hold, the answer is the count of the rarer element (which is 1). Otherwise, the answer is zero.

If there are three or more unique elements, you can never make all remaining elements equal by removing just one, so the answer is zero. I ran into a specific edge case during a contest that I still remember clearly. The input array was something like [2, 2, 2, 3, 3]. Two unique values, the most frequent is 2 with count 3, and 3 has count 2. My initial logic said "check if freq[majority] == freq[minority] + 1" and that failed here because removing one 2 leaves three elements that are not all equal. The correct check is whether removing any single element makes everything uniform, which means you need to verify that every element except possibly one is the same value. In this case the answer should be zero because removing a 2 still leaves two 3s mixed in. The workaround was to explicitly track the second most frequent element and validate its count as well, rather than assuming the frequency relationship alone was sufficient.

Get the Full Details

Day 11 2D Array Hackerrank Solution in C++ & Java | 30 Days
Day 11 2D Array Hackerrank Solution in C++ & Java | 30 Days

Here is the working implementation in Python:

def good_array(arr):
    from collections import Counter
    n = len(arr)
    if n = 1:
        return n
    freq = Counter(arr)
    unique = len(freq)
    if unique == 1:
        return n
    if unique == 2:
        counts = sorted(freq.values())
        if counts[1] == counts[0] + 1:
            return counts[0]
        return 0
    return 0

One counter-intuitive thing beginners miss: the most frequent element isn't always the one you remove. When there are exactly two unique values, you might remove the minority element, not the majority. The key constraint is that the remaining elements after removal must all be identical, so you're checking whether the majority count is exactly one more than the minority count, or whether the minority count is exactly one (meaning removing that single outlier leaves all majority elements). The time complexity is O(n) for the Counter pass and O(1) for the rest since we're only dealing with up to a few unique values. Space is O(n) in the worst case for the frequency map, though it collapses to O(1) if you know the value range upfront. This solution won't work if the constraints involve extremely large value ranges with sparse distributions where a hash map becomes memory-intensive. In those cases a sorted array approach with a sliding window check can substitute, trading some code complexity for better cache behavior on certain inputs.