Transform Array to All Equal Elements
Transform Array to All Equal Elements is a medium arrays & hashing problem solved with the greedy pattern.
The best approach, optimal (greedy left to right for each target), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every set of operations) up.
Problem
You are given an array nums whose elements are all 1 or -1, and an integer k.
In one operation you pick an index i with 0 <= i < n - 1 and multiply both nums[i] and nums[i + 1] by -1. The same index may be picked more than once.
Return true if you can make every element of the array equal using at most k operations, and false otherwise.
Examples
Example 1
- Input
nums = [1, -1, -1, 1, -1], k = 3- Output
true- Why
- Making everything 1 is impossible (the last element stays -1), but operations at indices 0, 1 and 2 turn the array into all -1 using exactly 3 operations.
Example 2
- Input
nums = [-1, 1, 1, -1, 1, 1], k = 1- Output
false- Why
- The cheapest way is two operations (at indices 1 and 4, giving all -1); all 1 would need three. One operation is not enough.
Example 3
- Input
nums = [1, -1, 1, 1], k = 4- Output
false- Why
- Each operation changes the number of -1s by an even amount, so an odd count of -1s in an even-length array can never become all 1 or all -1.
Constraints
1 <= nums.length <= 10^5nums[i]is either1or-1.1 <= k <= nums.length
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every set of operations) | O(2^n · n) | O(n) |
| Optimal (greedy left to right for each target) | O(n) | O(n) |
1Brute force (try every set of operations)
O(2^n · n)There are 2^(n-1) subsets and each is applied and checked in O(n).O(n)One copy of the array.Because applying an operation twice undoes it and operations commute, any result can be reached by applying each index i (0 ≤ i < n - 1) at most once. Enumerate every subset of indices with at most k elements, apply it to a copy, and check whether all elements are equal.
- For every bitmask over the n - 1 operation positions with at most k set bits:
- Copy
nums; for each set biti, negate positionsiandi + 1. - If all values in the copy are equal, return true.
- Return false after all masks.
class Solution {
public boolean canMakeEqual(int[] nums, int k) {
int n = nums.length;
for (int mask = 0; mask < (1 << (n - 1)); mask++) {
if (Integer.bitCount(mask) > k) continue;
int[] a = nums.clone();
for (int i = 0; i < n - 1; i++) {
if ((mask >> i & 1) == 1) { a[i] = -a[i]; a[i + 1] = -a[i + 1]; }
}
boolean same = true;
for (int x : a) if (x != a[0]) { same = false; break; }
if (same) return true;
}
return false;
}
}class Solution:
def canMakeEqual(self, nums: List[int], k: int) -> bool:
n = len(nums)
for mask in range(1 << (n - 1)):
if bin(mask).count("1") > k:
continue
a = nums[:]
for i in range(n - 1):
if mask >> i & 1:
a[i] = -a[i]
a[i + 1] = -a[i + 1]
if all(x == a[0] for x in a):
return True
return Falseclass Solution {
public:
bool canMakeEqual(vector<int>& nums, int k) {
int n = nums.size();
for (int mask = 0; mask < (1 << (n - 1)); mask++) {
if (__builtin_popcount(mask) > k) continue;
vector<int> a = nums;
for (int i = 0; i < n - 1; i++) {
if (mask >> i & 1) { a[i] = -a[i]; a[i + 1] = -a[i + 1]; }
}
bool same = true;
for (int x : a) if (x != a[0]) { same = false; break; }
if (same) return true;
}
return false;
}
};function canMakeEqual(nums, k) {
const n = nums.length;
for (let mask = 0; mask < (1 << (n - 1)); mask++) {
let bits = 0;
for (let m = mask; m; m &= m - 1) bits++;
if (bits > k) continue;
const a = nums.slice();
for (let i = 0; i < n - 1; i++) {
if ((mask >> i) & 1) { a[i] = -a[i]; a[i + 1] = -a[i + 1]; }
}
if (a.every((x) => x === a[0])) return true;
}
return false;
}2Optimal (greedy left to right for each target)
O(n)Two linear scans, one per target.O(n)A working copy of the array (a single carried sign would make it O(1)).Fix a target t. Walking left to right, once indices before i are correct, a wrong nums[i] can only be fixed by the operation at index i (the one at i - 1 would break index i - 1). So the flips are forced: flip whenever the current value differs from t, carry the effect to the next index, and at the end check the last element. Do this for t = 1 and t = -1 and see if either needs at most k operations.
- For each target
tin {1, -1}: copy the array,ops = 0. - For
ifrom 0 to n - 2: ifa[i] != t, negatea[i]anda[i + 1]and incrementops. - If
a[n - 1] == tandops <= k, return true. - Return false if neither target works.
class Solution {
public boolean canMakeEqual(int[] nums, int k) {
for (int target : new int[] { 1, -1 }) {
int[] a = nums.clone();
int ops = 0;
for (int i = 0; i + 1 < a.length; i++) {
if (a[i] != target) {
a[i] = -a[i];
a[i + 1] = -a[i + 1];
ops++;
}
}
if (a[a.length - 1] == target && ops <= k) return true;
}
return false;
}
}class Solution:
def canMakeEqual(self, nums: List[int], k: int) -> bool:
for target in (1, -1):
a = nums[:]
ops = 0
for i in range(len(a) - 1):
if a[i] != target:
a[i] = -a[i]
a[i + 1] = -a[i + 1]
ops += 1
if a[-1] == target and ops <= k:
return True
return Falseclass Solution {
public:
bool canMakeEqual(vector<int>& nums, int k) {
for (int target : {1, -1}) {
vector<int> a = nums;
int ops = 0;
for (int i = 0; i + 1 < (int)a.size(); i++) {
if (a[i] != target) {
a[i] = -a[i];
a[i + 1] = -a[i + 1];
ops++;
}
}
if (a.back() == target && ops <= k) return true;
}
return false;
}
};function canMakeEqual(nums, k) {
for (const target of [1, -1]) {
const a = nums.slice();
let ops = 0;
for (let i = 0; i + 1 < a.length; i++) {
if (a[i] !== target) {
a[i] = -a[i];
a[i + 1] = -a[i + 1];
ops++;
}
}
if (a[a.length - 1] === target && ops <= k) return true;
}
return false;
}Edge cases to test
- A single element (already all equal)
- Already all equal: zero operations are needed
- Only one of the two targets is reachable (the other leaves a mismatched last element)
- Both targets are reachable but only the cheaper one fits within k
- k exactly equal to the minimum number of operations
Hints
Hint 1
Applying the same operation twice cancels out, and the order of operations does not matter. So the question is only which indices get flipped once.
Hint 2
Fix the target value (1 or -1). Scanning left to right, the first wrong element can only be fixed by the operation at its own index.
Hint 3
Greedily flip whenever nums[i] is wrong, count the flips, and check that the last element ends up correct. Try both targets and compare the smaller count with k.
FAQ
What is the best time complexity for Transform Array to All Equal Elements?
Optimal (greedy left to right for each target) runs in O(n) time and O(n) extra space. Two linear scans, one per target.
Which pattern does Transform Array to All Equal Elements use?
It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.
Is there a brute force solution for Transform Array to All Equal Elements?
Yes. Brute force (try every set of operations) takes O(2^n · n) time and O(n) space. Because applying an operation twice undoes it and operations commute, any result can be reached by applying each index i (0 ≤ i < n - 1) at most once.
Which edge cases should I test for Transform Array to All Equal Elements?
A single element (already all equal); Already all equal: zero operations are needed; Only one of the two targets is reachable (the other leaves a mismatched last element); Both targets are reachable but only the cheaper one fits within k; k exactly equal to the minimum number of operations.