Skip to main content

Hashing

Minimum Seconds to Equalize a Circular Array Solution In C++/Java/Python/JS

Problem Description

There are two mice and n different types of cheese, each type of cheese should be eaten by exactly one mouse.
A point of the cheese with index i (0-indexed) is:

reward1[i] if the first mouse eats it.
reward2[i] if the second mouse eats it.

You are given a positive integer array reward1, a positive integer array reward2, and a non-negative integer k.

Return the maximum points the mice can achieve if the first mouse eats exactly k types of cheese.

Example

Input: reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2
Output: 15
Explanation: In this example, the first mouse eats the 2nd (0-indexed) and the 3rd types of cheese, and the second mouse eats the 0th and the 1st types of cheese.
The total points are 4 + 4 + 3 + 4 = 15.
It can be proven that 15 is the maximum total points that the mice can achieve.

Input: reward1 = [1,1], reward2 = [1,1], k = 2
Output: 2
Explanation: In this example, the first mouse eats the 0th (0-indexed) and 1st types of cheese, and the second mouse does not eat any cheese.
The total points are 1 + 1 = 2.
It can be proven that 2 is the maximum total points that the mice can achieve.

Constraints

  • 1 <= n == reward1.length == reward2.length <= 105
  • 1 <= reward1[i], reward2[i] <= 1000
  • 0 <= k <= n
💡
Try Solving "Minimum Seconds to Equalize a Circular Array" Yourself First !!
Figuring out "Minimum Seconds to Equalize a Circular Array solution" can be solved using different approaches. We will first figure out the most intuitive approach and move to the optimal approach if exists. Let's sit with a pen and paper and figure out the algorithm !!

Optimal Approach

Intuition

We have a circular array nums of n integers. Every second, we can update any element nums[i] to either remain the same, take the value of the previous element nums[(i - 1 + n) % n], or take the value of the next element nums[(i + 1) % n]. Our goal is to determine the minimum number of seconds required to make all elements in nums equal. How shoulf we approach this problem?

Since the array is circular, we need to ensure that any modifications wrap around correctly. A brute force approach could involve simulating these operations step by step and checking how many seconds it takes for all elements to become the same.

That's a good starting point! However, brute force might be too slow since n can be large. Instead, let's think about how values spread across the array.
Let's take and example and see how we gonna figure out the working algorithm.

Consider the example nums = [2, 1, 3, 1, 2]. If we could choose a number to spread to the rest of the array, which number should we choose?

Well, if we pick 1, it already appears twice in the array, so it might spread faster. Similarly, 2 appears twice, and 3 appears only once.

Exactly! The key observation is that we can always make the entire array equal to any one of its current values since we are allowed to propagate values in both directions. So, if we want to minimize the number of seconds, we should focus on a value that is already well-distributed. That makes sense. So, how do we measure how fast a value can spread?

We can track the indices where each unique value appears. If we analyze nums = [2, 1, 3, 1, 2], we can store: 2 appears at [0, 4] , 1 appears at [1, 3], 3 appears at [2]

Now, to determine how long it takes for a value to spread, we need to measure the largest gap between two consecutive occurrences of that value (considering the wrap-around case). The worst-case gap determines how long it will take for the value to spread fully.

Oh, so the further apart the same value appears in the array, the longer it takes for that value to spread! Exactly. The idea is to compute the maximum distance between any two consecutive occurrences of each unique value and use that to determine the time required for that value to take over the entire array.

That sounds like a greedy approach! We are making a locally optimal choice by picking the best value to spread, hoping it leads to a globally optimal solution.

Yes! Now, let’s outline the steps of our Algorithm

Minimum Seconds to Equalize a Circular Array Algorithm

  1. Group indices of identical elements in a dictionary.
  2. Find the largest gap between consecutive occurrences of each value (accounting for the wrap-around).
  3. Compute the minimum spread time, which is half of the largest gap (since we can spread the value from both ends).
  4. Return the minimum time among all values.

Fine !! Let's now see how to code the approach !!

Approach

Store Indices of Each Unique Number:

Create a HashMap (indicesMap) where:

  • The key is a unique number from nums[].
  • The value is a list of all indices where that number appears in nums[].

Iterate through nums[] and populate indicesMap accordingly.

Initialize Minimum Seconds Variable: Set minSeconds to a very high value (Integer.MAX_VALUE).

Process Each Unique Number:

  • For each list of indices in indicesMap:
    • Compute the total occurrences of the number (occurrenceCount).
    • Compute the maximum time gap between consecutive occurrences.
    • Since the list is circular, also check the time difference from the last occurrence back to the first occurrence.

Calculate the Maximum Gap:

  • Initialize maxTimeDiff as the difference between the first and last occurrence in a circular manner.
  • Iterate through the list of indices: Update maxTimeDiff to store the largest gap between consecutive indices.

Determine Minimum Seconds:

  • The minimum time required to equalize the list is maxTimeDiff / 2.
  • Update minSeconds if a smaller value is found.

Return the Final Computed Value: Print the minimum seconds required to make all elements equal.

Dry-Run

Input:

  • n = 7
  • nums = [1, 2, 1, 3, 2, 1, 3]

Step 1: Store Indices of Each Unique Number

We create a map (indicesMap) to store where each number appears in nums:

  • 1 → [0, 2, 5]
  • 2 → [1, 4]
  • 3 → [3, 6]

Step 2: Initialize minSeconds

Set minSeconds = Integer.MAX_VALUE to track the minimum required time.

Step 3: Process Each Unique Number

Processing Number 1 (Indices: [0, 2, 5])

  • Compute circular time gap:
    • maxTimeDiff = (first occurrence to last occurrence in circular manner) = 0 + 7 - 5 = 2
  • Compute max gap between consecutive occurrences:
    • max(2 - 0, 5 - 2) = max(2, 3) = 3
  • Compute time required:
    • maxTimeDiff / 2 = 3 / 2 = 1 (rounded down)
  • Update minSeconds:
    • minSeconds = min(Integer.MAX_VALUE, 1) = 1

Processing Number 2 (Indices: [1, 4])

  • Compute circular time gap:
    • maxTimeDiff = 1 + 7 - 4 = 4
  • Compute max gap between occurrences:
    • max(4 - 1) = 3
  • Compute time required:
    • maxTimeDiff / 2 = 3 / 2 = 1
  • Update minSeconds:
    • minSeconds = min(1, 1) = 1

Processing Number 3 (Indices: [3, 6])

  • Compute circular time gap:
    • maxTimeDiff = 3 + 7 - 6 = 4
  • Compute max gap between occurrences:
    • max(6 - 3) = 3
  • Compute time required:
    • maxTimeDiff / 2 = 3 / 2 = 1
  • Update minSeconds:
    • minSeconds = min(1, 1) = 1

Final Result: The minimum time required to equalize all elements is 1 second.

Minimum Seconds to Equalize a Circular Array Solution

Now lets checkout the "Minimum Seconds to Equalize a Circular Array code in C++ , Java, Python and JavaScript.

"Minimum Seconds to Equalize a Circular Array" Code in all Languages.
1. Minimum Seconds to Equalize a Circular Array solution in C++ Try on Compiler 
class Solution {
public:
    int minimumSeconds(vector<int>& nums) {
        // Create a map to store the indices for each unique number
        unordered_map<int, vector<int>> indicesMap;
        
        // Get the total number of elements in the list
        int totalElements = nums.size();

        // Populate the map with lists of indices for each number
        for (int i = 0; i < totalElements; i++) {
            indicesMap[nums[i]].push_back(i);
        }

        // Initialize the minimum seconds to a very high value
        int minSeconds = INT_MAX;

        // Iterate over each list of indices stored in the map
        for (auto& pair : indicesMap) {
            vector<int>& indices = pair.second;
            int occurrenceCount = indices.size();

            // Calculate the initial time difference (circular distance)
            int maxTimeDiff = indices[0] + totalElements - indices[occurrenceCount - 1];

            // Update the maximum gap between consecutive occurrences
            for (int i = 1; i < occurrenceCount; i++) {
                maxTimeDiff = max(maxTimeDiff, indices[i] - indices[i - 1]);
            }

            // Update the minimum time required
            minSeconds = min(minSeconds, maxTimeDiff / 2);
        }

        // Return the minimum seconds required
        return minSeconds;
    }
};

2. Minimum Seconds to Equalize a Circular Array Solution in Java Try on Compiler 
class Solution {
    public int minimumSeconds(List<Integer> nums) {
        // Create a map to store the indices for each unique number
        Map<Integer, List<Integer>> indicesMap = new HashMap<>();
        
        // Get the total number of elements in the list
        int totalElements = nums.size();

        // Populate the map with lists of indices for each number
        for (int i = 0; i < totalElements; i++) {
            indicesMap.computeIfAbsent(nums.get(i), k -> new ArrayList<>()).add(i);
        }

        // Initialize the minimum seconds to a very high value
        int minSeconds = Integer.MAX_VALUE;

        // Iterate over each list of indices stored in the map
        for (List<Integer> indices : indicesMap.values()) {
            // Get the total occurrences of the current number
            int occurrenceCount = indices.size();

            // Calculate the initial time difference (from first to last occurrence in circular manner)
            int maxTimeDiff = indices.get(0) + totalElements - indices.get(occurrenceCount - 1);

            // Update the maximum gap between consecutive occurrences
            for (int i = 1; i < occurrenceCount; i++) {
                maxTimeDiff = Math.max(maxTimeDiff, indices.get(i) - indices.get(i - 1));
            }

            // Update the minimum time required
            minSeconds = Math.min(minSeconds, maxTimeDiff / 2);
        }

        // Return the minimum seconds required
        return minSeconds;
    }
}

3. Minimum Seconds to Equalize a Circular Array Solution in Python Try on Compiler 
class MinimumSecondsCalculator:
    def minimumSeconds(self, nums):
        # Create a dictionary to store the indices for each unique number
        indices_map = {}

        # Get the total number of elements in the list
        total_elements = len(nums)

        # Populate the dictionary with lists of indices for each number
        for i, num in enumerate(nums):
            if num not in indices_map:
                indices_map[num] = []
            indices_map[num].append(i)

        # Initialize the minimum seconds to a very high value
        min_seconds = float('inf')

        # Iterate over each list of indices stored in the dictionary
        for indices in indices_map.values():
            occurrence_count = len(indices)

            # Calculate the initial time difference (circular distance)
            max_time_diff = indices[0] + total_elements - indices[occurrence_count - 1]

            # Update the maximum gap between consecutive occurrences
            for i in range(1, occurrence_count):
                max_time_diff = max(max_time_diff, indices[i] - indices[i - 1])

            # Update the minimum time required
            min_seconds = min(min_seconds, max_time_diff // 2)

        # Return the minimum seconds required
        return min_seconds

4. Minimum Seconds to Equalize a Circular Array solution in JavaScript Try on Compiler 
class MinimumSecondsCalculator {
    minimumSeconds(nums) {
        // Create a map to store the indices for each unique number
        const indicesMap = new Map();
        const totalElements = nums.length;

        // Populate the map with lists of indices for each number
        nums.forEach((num, index) => {
            if (!indicesMap.has(num)) {
                indicesMap.set(num, []);
            }
            indicesMap.get(num).push(index);
        });

        // Initialize the minimum seconds to a very high value
        let minSeconds = Infinity;

        // Iterate over each list of indices stored in the map
        indicesMap.forEach(indices => {
            const occurrenceCount = indices.length;

            // Calculate the initial time difference (circular distance)
            let maxTimeDiff = indices[0] + totalElements - indices[occurrenceCount - 1];

            // Update the maximum gap between consecutive occurrences
            for (let i = 1; i < occurrenceCount; i++) {
                maxTimeDiff = Math.max(maxTimeDiff, indices[i] - indices[i - 1]);
            }

            // Update the minimum time required
            minSeconds = Math.min(minSeconds, Math.floor(maxTimeDiff / 2));
        });

        // Return the minimum seconds required
        return minSeconds;
    }
}

Minimum Seconds to Equalize a Circular Array Complexity Analysis

Time Complexity: O(n)

Building the indicesMap

  • We iterate through the list once (O(n)) to populate the map.
  • Each number is inserted into a list, which takes O(1) per operation.
  • Total time = O(n).

Processing the indicesMap

  • We iterate through each list of indices stored in the map.
  • In the worst case, all elements are unique, leading to O(n) iterations.
  • Within each list, we compute the maximum gap between consecutive indices, requiring another O(n) operations in the worst case.

Thus, the dominant steps involve O(n) + O(n) = O(n) operations.

Space Complexity: O(n)

Auxiliary Space Complexity
It refers to the extra space required by an algorithm other than the input space.

indicesMap Storage:

  • In the worst case, where all elements are unique, the indicesMap stores n entries, each with a list of size 1.
  • In the best case, where all elements are the same, it stores 1 entry with a list of size n.
  • Worst-case space complexity = O(n).

Thus, the auxiliary space complexity is: O(n)

Total Space Complexity

  • Input Storage: nums list → O(n).
  • Auxiliary Space: indicesMap → O(n).

Thus, the total space complexity is: O(n)

Similar Problems

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Rat in a Maze Problem - I

Consider a rat placed at position (0, 0) in an n x n square matrix mat. The rat's goal is to reach the destination at position (n-1, n-1). The rat can move in four possible directions: 'U'(up), 'D'(down), 'L' (left), 'R' (right).

The matrix contains only two possible values:

  • 0: A blocked cell through which the rat cannot travel.
  • 1: A free cell that the rat can pass through.