3396. Minimum Number of Operations to Make Elements in Array Distinct

MediumView on LeetCode

Array Hash Table Sorting

Time: O(n)

Space: O(n)

Problem Overview

Each operation removes the first 3 elements of the current array.

Intuition

Each operation removes the first 3 elements of the current array. Scan from the right; when you see a duplicate, the prefix up to and including that index must be cleared in chunks of 3 — answer is ceil((i+1)/3) operations. If no duplicate, 0.

Algorithm

1Use a set while iterating i from n-1 down to 0.
2On first duplicate (set.Add fails): return (i + 1 + 2) / 3 using integer ceiling.
3If loop finishes, return 0.

Example Walkthrough

Input: nums = [1,2,3,4,2,3,4,4]

1.Scan right: first repeat is 2 at some index; prefix length needing cleanup → ceil(len/3) ops.

Output: operations needed

Common Pitfalls

•Right-to-left finds the earliest duplicate in the suffix sense for minimal ops.
•Formula (i+1+2)/3 is integer ceil of (i+1)/3.
•Distinct entire array → 0 operations.

3396.cs

// Approach: Scan from right in groups of 3; stop when first duplicate encountered; ops = ceil remaining.
// Time: O(n) Space: O(n)

public class Solution
{
    public int MinimumOperations(int[] nums)
    {
        var set = new HashSet<int>();
        for (int i = nums.Length - 1; i >= 0; i--)
        {
            if (!set.Add(nums[i]))
                return (i + 1 + 2) / 3;
        }

        return 0;
    }
}

Was this solution helpful?