Skip to main content
Talentd

Minimum Operations to Reach Target Array - Solution & Explanation

MediumArrayHash TableGreedy6 min read
Practice this problem

Problem Statement

You are given two integer arrays nums and target, each of length n, where nums[i] is the current value at index i and target[i] is the desired value at index i.

You may perform the following operation any number of times (including zero):

  • Choose an integer value x
  • Find all maximal contiguous segments where nums[i] == x (a segment is maximal if it cannot be extended to the left or right while keeping all values equal to x)
  • For each such segment [l, r], update simultaneously:
    • nums[l] = target[l], nums[l + 1] = target[l + 1], ..., nums[r] = target[r]

Return the minimum number of operations required to make nums equal to target.

 

Example 1:

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

Output: 2

Explanation:ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹

  • Choose x = 1: maximal segment [0, 0] updated -> nums becomes [2, 2, 3]
  • Choose x = 2: maximal segment [0, 1] updated (nums[0] stays 2, nums[1] becomes 1) -> nums becomes [2, 1, 3]
  • Thus, 2 operations are required to convert nums to target.ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹

Example 2:

Input: nums = [4,1,4], target = [5,1,4]

Output: 1

Explanation:

  • Choose x = 4: maximal segments [0, 0] and [2, 2] updated (nums[2] stays 4) -> nums becomes [5, 1, 4]
  • Thus, 1 operation is required to convert nums to target.

Example 3:

Input: nums = [7,3,7], target = [5,5,9]

Output: 2

Explanation:

  • Choose x = 7: maximal segments [0, 0] and [2, 2] updated -> nums becomes [5, 3, 9]
  • Choose x = 3: maximal segment [1, 1] updated -> nums becomes [5, 5, 9]
  • Thus, 2 operations are required to convert nums to target.

 

Constraints:

  • 1 <= n == nums.length == target.length <= 105
  • 1 <= nums[i], target[i] <= 105

Approach Overview

Problem Overview: You are given an array and a target array. The task is to compute the minimum number of operations required to transform the current array so it matches the target configuration. The key observation is that operations only matter for elements that do not already contribute to the correct multiset of values in the target.

Approach 1: Frequency Comparison (Hash Table) (Time: O(n), Space: O(n))

Use a hash table to track how many times each value should appear in the target array. First iterate through target and store frequencies in a dictionary or map. Then scan the original array and decrement the count when a matching value exists in the map. If a value is not needed or its frequency is already satisfied, it represents an element that must be changed. Each unmatched element contributes to the total number of required operations. This works because the optimal strategy is greedy: keep every value that already helps satisfy the target distribution and only modify the surplus elements.

The hash lookup ensures each check runs in constant time. Instead of simulating transformations directly, the algorithm reduces the problem to counting deficits and surpluses between two arrays. This is a common pattern when working with hash tables and arrays: represent the target state as frequencies, then greedily match what already exists.

After processing the entire array, any remaining positive counts in the map correspond to missing values, while unmatched elements from the original array represent surplus elements. The number of operations equals the number of mismatches required to rebalance these counts. Because each element is processed exactly once and each map operation is constant time on average, the overall complexity remains linear.

This greedy counting technique avoids expensive comparisons or repeated scans. Instead of reordering or repeatedly modifying elements, you directly compute how far the current configuration is from the desired one using frequency bookkeeping.

Recommended for interviews: The hash table greedy approach is the expected solution. Interviewers want to see that you recognize the problem as a frequency matching task rather than a simulation problem. A brute-force simulation demonstrates understanding but leads to unnecessary repeated operations. The greedy counting method shows stronger algorithmic judgment and achieves optimal O(n) time.

Solution

According to the problem description, we only need to count the number of distinct nums[i] where nums[i] \ne target[i]. Therefore, we can use a hash table to store these distinct nums[i] and finally return the size of the hash table.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(nĀ²)O(1)For conceptual understanding or very small arrays
Sorting + ComparisonO(n log n)O(1) or O(n)When order does not matter and sorting is acceptable
Hash Table GreedyO(n)O(n)General case and interview-preferred optimal solution

Video Solution

Minimum Operations to Reach Target Array | LeetCode 3810 | Set ā€¢ codeTips ā€¢ 240 views views

Watch 5 more video solutions ā†’

Frequently Asked Questions

Is Minimum Operations to Reach Target Array easy or hard?
Minimum Operations to Reach Target Array is typically categorized as a Medium difficulty problem. The implementation is straightforward once you recognize that the problem reduces to frequency differences between two arrays using a hash table.
Minimum Operations to Reach Target Array Python/Java solution
In Python, use a dictionary or collections.Counter to store target frequencies and update counts while scanning the array. In Java, use a HashMap<Integer, Integer> for the same purpose. Both implementations follow the same O(n) greedy counting logic.
How to solve Minimum Operations to Reach Target Array in O(n)?
Build a frequency map of the target array using a hash table. Iterate through the current array and decrement the frequency when a matching value is still needed. If no frequency remains for that value, it represents an element that must be changed. Counting these mismatches yields the minimum number of operations in linear time.
What is the best approach for Minimum Operations to Reach Target Array?
The optimal solution uses a hash table with a greedy matching strategy. Store frequencies of the target array, then iterate through the original array and match elements that are still needed. Any extra or missing elements correspond to required operations. This approach runs in O(n) time with O(n) space.
Is Minimum Operations to Reach Target Array asked at Google/Amazon/Meta?
Problems based on array frequency matching and hash table counting frequently appear in interviews at companies like Amazon, Google, and Meta. The pattern of using a frequency map to detect surplus and missing elements is a common interview technique.
What data structure is used in Minimum Operations to Reach Target Array?
A hash table (such as a dictionary or unordered_map) is the primary data structure. It stores the frequency of each value in the target array and allows constant-time checks to see whether elements from the current array can satisfy those counts.
What is the time complexity of Minimum Operations to Reach Target Array?
The optimal hash table approach runs in O(n) time because each element of the arrays is processed once and hash lookups are O(1) on average. The space complexity is O(n) for storing the frequency map of the target values.

Ready to solve this problem?

Practice Minimum Operations to Reach Target Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays