LeetCode Entry

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

08.04.2025 easy 2025 kotlin rust

Count removals 3-prefixes to deduplicate

3396. Minimum Number of Operations to Make Elements in Array Distinct easy blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/952

Problem TLDR

Count removals 3-prefixes to deduplicate #easy

Intuition

Brute force is accepted.

Linear solution: start from the tail and stop on first duplicate.

Approach

Observations by golfing:

  • count works, after some border we always have duplicate (meaning, we also can do a binary search)
  • forward pass possible (and gives faster speed with CPU caches)
  • bitset can be used

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(max)\)

Code


    fun minimumOperations(nums: IntArray) = nums.indices
    .count { nums.drop(it * 3).let { it.distinct() != it }}



    fun minimumOperations(nums: IntArray): Int {
        val o = IntArray(101)
        return nums.withIndex().maxOf { (i, x) ->
            o[x].also { o[x] = 1 + i / 3 }
        }
    }



    fun minimumOperations(nums: IntArray): Int {
        val f = IntArray(101)
        for (i in nums.lastIndex downTo 0)
            if (f[nums[i]]++ > 0) return 1 + i / 3
        return 0
    }



    pub fn minimum_operations(nums: Vec<i32>) -> i32 {
        let mut o = [0; 101];
        nums.iter().enumerate().map(|(i, &x)| { let x = x as usize;
            let r = o[x]; o[x] = 1 + i as i32 / 3; r}).max().unwrap()
    }



    int minimumOperations(vector<int>& nums) {
        for (int i = size(nums) - 1, f[101]; i >= 0; --i)
            if (f[nums[i]]++ > 0) return 1 + i / 3;
        return 0;
    }