We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Operations to Make Elements in Array Distinct

Number: 3656

Difficulty: Easy

Paid? No

Companies: Bloomberg

Problem Description

Given an integer array nums, you can remove 3 elements from the beginning of the array in one operation (or all remaining elements if fewer than 3 exist). The goal is to perform the minimum number of such operations so that the remaining array (which can be empty) contains only distinct elements.

Key Insights

  • After each operation, the subarray we consider is formed by removing a prefix of length (operations * 3).
  • An empty array is trivially distinct.
  • Simply iterate over the possible numbers of operations and check if the subarray (i.e., nums[operations*3:]) has all unique elements.
  • The first occurrence where the subarray is distinct gives the minimum number of operations required.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case since for each potential operation (up to n/3 iterations) we check the distinct property in O(n) time. Space Complexity: O(n) to store the subarray conversion to a set during distinct check.

Solution

We simulate the process by iterating through possible numbers of operations. For each count, we compute the remaining subarray by slicing nums from index (operations * 3) to the end. We then check if the subarray contains distinct elements by comparing the length of the subarray and the set constructed from it. The first operation count that yields a distinct subarray is our answer.

Code Solutions

def minOperations(nums):
    # Calculate the total number of elements in the array
    n = len(nums)
    # Start with 0 operations
    ops = 0
    # Iterate until removing (ops * 3) exceeds the length (empty array is distinct)
    while ops * 3 <= n:
        # Get the remaining subarray after performing ops operations
        subarray = nums[ops * 3:]
        # Check if the subarray has all distinct elements using a set
        if len(subarray) == len(set(subarray)):
            return ops
        # Increment the number of operations
        ops += 1
    # This return will never be reached as empty array is always distinct
    return ops

# Example test cases
print(minOperations([1, 2, 3, 4, 2, 3, 3, 5, 7]))  # Expected output: 2
print(minOperations([4, 5, 6, 4, 4]))              # Expected output: 2
print(minOperations([6, 7, 8, 9]))                 # Expected output: 0
← Back to All Questions