Transform Array to All Equal Elements

Medium Arrays & Hashing Greedy Original on LeetCode

Reported atFlipkart

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^5
  • nums[i] is either 1 or -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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(2^n · n)There are 2^(n-1) subsets and each is applied and checked in O(n).
SpaceO(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.

  1. For every bitmask over the n - 1 operation positions with at most k set bits:
  2. Copy nums; for each set bit i, negate positions i and i + 1.
  3. If all values in the copy are equal, return true.
  4. 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;
    }
}

2Optimal (greedy left to right for each target)

TimeO(n)Two linear scans, one per target.
SpaceO(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.

  1. For each target t in {1, -1}: copy the array, ops = 0.
  2. For i from 0 to n - 2: if a[i] != t, negate a[i] and a[i + 1] and increment ops.
  3. If a[n - 1] == t and ops <= k, return true.
  4. 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;
    }
}

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.