Watch 8 video solutions for Minimum Operations to Reach Target Array, a medium level problem involving Array, Hash Table, Greedy. This walkthrough by codeTips has 217 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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):
xnums[i] == x (a segment is maximal if it cannot be extended to the left or right while keeping all values equal to x)[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:āāāāāāā
x = 1: maximal segment [0, 0] updated -> nums becomes [2, 2, 3]x = 2: maximal segment [0, 1] updated (nums[0] stays 2, nums[1] becomes 1) -> nums becomes [2, 1, 3]nums to target.āāāāāāāāāāāāāāExample 2:
Input: nums = [4,1,4], target = [5,1,4]
Output: 1
Explanation:
x = 4: maximal segments [0, 0] and [2, 2] updated (nums[2] stays 4) -> nums becomes [5, 1, 4]nums to target.Example 3:
Input: nums = [7,3,7], target = [5,5,9]
Output: 2
Explanation:
x = 7: maximal segments [0, 0] and [2, 2] updated -> nums becomes [5, 3, 9]x = 3: maximal segment [1, 1] updated -> nums becomes [5, 5, 9]nums to target.
Constraints:
1 <= n == nums.length == target.length <= 1051 <= nums[i], target[i] <= 105Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(nĀ²) | O(1) | For conceptual understanding or very small arrays |
| Sorting + Comparison | O(n log n) | O(1) or O(n) | When order does not matter and sorting is acceptable |
| Hash Table Greedy | O(n) | O(n) | General case and interview-preferred optimal solution |