algoadvance

Leetcode 3038. Maximum Number of Operations With the Same Score I

Problem Statement

You are given an array nums of integers. You can perform the following operation any number of times:

  1. Select two indices i and j such that nums[i] = nums[j] and i != j.
  2. Remove nums[i] and nums[j] from the array.

Your task is to determine the maximum number of operations you can perform.

Clarifying Questions

  1. Can the operations be performed on any two identical numbers repeatedly as long as they exist in the array?
    • Yes, as long as there are pairs of identical numbers, the operations can be performed.
  2. What should be done if there are no pairs of identical numbers in the array?
    • If there are no pairs, the answer is 0.
  3. Are the numbers in the array always positive or can they be negative as well?
    • The numbers can be both positive and negative.
  4. How large can the array be?
    • The array can contain up to (10^5) elements.

Strategy

The strategy revolves around counting the frequency of each element in the array. For any element, the number of pairs that can be formed is equal to the integer division of its frequency by 2.

Here are the steps:

  1. Use a HashMap to count the frequency of each number in the array.
  2. For each unique number, determine how many pairs can be formed by dividing the count by 2.
  3. Sum the results to get the total number of operations.

Code

Let’s implement this in Java:

import java.util.HashMap;

public class MaximumOperations {
    public int maxOperations(int[] nums) {
        HashMap<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        
        int maxOperations = 0;
        for (int frequency : frequencyMap.values()) {
            maxOperations += frequency / 2;
        }
        
        return maxOperations;
    }

    public static void main(String[] args) {
        MaximumOperations solution = new MaximumOperations();
        int[] nums = {1, 2, 3, 4, 4, 3, 2, 1};
        System.out.println(solution.maxOperations(nums));  // Output: 4
    }
}

Time Complexity

Overall, the time complexity is ( O(n) ). The space complexity is also ( O(n) ) due to the HashMap storing the frequency counts.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI