You are given an integer array nums of size n containing only 1 and -1, and an integer k.
You can perform the following operation at most k times:
Choose an index i (0 <= i < n - 1), and multiply both nums[i] and nums[i + 1] by -1.
Note that you can choose the same index i more than once in different operations.
Return true if it is possible to make all elements of the array equal after at most k operations, and false otherwise.
Example 1:
Input: nums = [1,-1,1,-1,1], k = 3
Output: true
Explanation:
We can make all elements in the array equal in 2 operations as follows:
i = 1, and multiply both nums[1] and nums[2] by -1. Now nums = [1,1,-1,-1,1].i = 2, and multiply both nums[2] and nums[3] by -1. Now nums = [1,1,1,1,1].Example 2:
Input: nums = [-1,-1,-1,1,1,1], k = 5
Output: false
Explanation:
It is not possible to make all array elements equal in at most 5 operations.
Constraints:
1 <= n == nums.length <= 105nums[i] is either -1 or 1.1 <= k <= nProblem Overview: You are given an array of integers and need to transform it so every element becomes the same value. The goal is to minimize the number of changes. The key question becomes: which value should the entire array be converted to so the number of operations is smallest?
Approach 1: Brute Force Target Simulation (O(n^2) time, O(1) space)
Try every unique value in the array as the final target value. For each candidate, iterate through the array and count how many elements differ from that value. That count equals the number of operations required if you transform every mismatched element. Track the minimum across all candidates. This approach is straightforward but inefficient because the array is scanned repeatedly for each possible target.
Approach 2: Traversal and Frequency Counting (Greedy) (O(n) time, O(n) space)
The optimal strategy is to keep the value that already appears the most. Every other element must change to match it. Traverse the array once and store frequencies using a hash map or counter. The value with the highest frequency represents the best target because it minimizes the number of modifications. The minimum operations required becomes n - max_frequency. This greedy observation eliminates the need to simulate every transformation explicitly.
This approach relies on simple array traversal and counting rather than complex transformations. The insight is that converting fewer elements is always optimal, so preserving the most common value yields the minimal number of operations. Hash lookups remain constant time, which keeps the overall runtime linear.
Problems like this often appear in interviews when discussing array traversal patterns and simple greedy optimization. Recognizing that the best global decision is determined by frequency is a common trick used in counting-based greedy solutions.
Recommended for interviews: The traversal and counting approach is what interviewers expect. It shows you can reduce the problem to a frequency analysis and derive the greedy insight that preserving the most frequent value minimizes operations. Mentioning the brute force approach first demonstrates understanding of the search space, while the optimized counting solution proves you can reach the linear-time improvement.
According to the problem description, to make all elements in the array equal, all elements must be either nums[0] or -nums[0]. Therefore, we design a function check to determine whether the array can be transformed into all elements equal to target with at most k operations.
The idea of this function is to traverse the array and count the number of operations needed. Each element is either modified once or not at all. If the current element is equal to the target value, no modification is needed and we continue to the next element. If the current element is not equal to the target value, an operation is needed, increment the counter, and flip the sign, indicating that subsequent elements need the opposite operation.
After the traversal, if the counter is less than or equal to k and the sign of the last element matches the target value, return true; otherwise, return false.
The final answer is the result of check(nums[0], k) or check(-nums[0], k).
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Target Simulation | O(n^2) | O(1) | Useful for understanding the baseline idea by testing every possible target value |
| Traversal and Frequency Counting (Greedy) | O(n) | O(n) | Best general solution when the goal is minimizing replacements across the entire array |
3576. Transform Array to All Equal Elements | Array | Greedy | Leetcode • Rapid Syntax • 960 views views
Watch 6 more video solutions →Practice Transform Array to All Equal Elements with our built-in code editor and test cases.
Practice on FleetCode