# Transform Array to All Equal Elements
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/transform-array-to-all-equal-elements)
Canonical: https://scaleengineer.com/dsa/problems/transform-array-to-all-equal-elements
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## Problem
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:

* Choose index `i = 1`, and multiply both `nums[1]` and `nums[2]` by -1\. Now `nums = [1,1,-1,-1,1]`.
* Choose index `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 <= 105`
* `nums[i]` is either -1 or 1.
* `1 <= k <= n`

# Approaches
## Greedy Simulation with Auxiliary Array
This approach is based on a greedy strategy. To make all elements equal to a target value (either 1 or -1), we can iterate through the array and fix each element one by one. For instance, to make all elements `1`, we iterate from left to right. If we encounter a `-1` at index `i`, we must perform the operation at index `i` to flip it to `1`. This operation also flips the element at `i+1`. We continue this process until we reach the end of the array. This strategy is optimal because the choice at each step `i` is forced if we want to fix `nums[i]` without disturbing the already fixed elements `nums[0...i-1]`.

We apply this greedy strategy for two separate goals: making all elements `1`, and making all elements `-1`. If either goal can be achieved in `k` or fewer operations, the answer is `true`.
**Time:** O(n), where n is the number of elements in the array. We perform at most two passes over the array, each taking O(n) time. Thus, the total time complexity is O(n) + O(n) = O(n). · **Space:** O(n), where n is the number of elements in the array. This is because we create a copy of the input array for each of the two scenarios (making all 1s and making all -1s).
**Pros:** The logic is straightforward and directly simulates the greedy process.; Easy to implement and understand.
**Cons:** Uses O(n) extra space for the auxiliary array, which can be inefficient for very large inputs.
### Explanation
We check two possibilities: making all elements `1`, and making all elements `-1`.

### To make all elements `1`:
We create a temporary copy of the `nums` array. We iterate from `i = 0` to `n-2`. If the current element `nums_copy[i]` is `-1`, we must flip it to `1`. The only way to do this without affecting elements before `i` is to apply the operation at index `i`. This increments our operation count and flips both `nums_copy[i]` and `nums_copy[i+1]`. After the loop, the first `n-1` elements are guaranteed to be `1`. We then check the last element, `nums_copy[n-1]`. If it is also `1`, we have successfully transformed the array. We then check if the number of operations used is less than or equal to `k`.

### To make all elements `-1`:
A similar process is followed. We iterate through a copy of the array, and if an element `nums_copy[i]` is `1`, we apply the operation at `i` to flip it to `-1`. We count the operations and check the final state of the array and the operation count against `k`.

If either of these scenarios yields a valid solution, we return `true`. Otherwise, it's impossible, so we return `false`.

```java
class Solution {
    public boolean canMakeEqual(int[] nums, int k) {
        // Check if we can make all elements 1
        if (check(nums, k, 1)) {
            return true;
        }
        // Check if we can make all elements -1
        if (check(nums, k, -1)) {
            return true;
        }
        return false;
    }

    private boolean check(int[] nums, int k, int target) {
        int n = nums.length;
        int[] tempNums = nums.clone();
        int ops = 0;

        for (int i = 0; i < n - 1; i++) {
            if (tempNums[i] != target) {
                ops++;
                tempNums[i] *= -1;
                tempNums[i + 1] *= -1;
            }
        }

        if (tempNums[n - 1] == target) {
            return ops <= k;
        }
        
        return false;
    }
}
```
### Algorithm
1. Define a helper function `check(target)` that calculates the minimum operations to make all elements equal to `target`.
2. Inside `check(target)`:
   a. Create a copy of the input `nums` array to avoid modifying the original.
   b. Initialize an operations counter, `ops`, to 0.
   c. Iterate through the copied array from `i = 0` to `n-2`.
   d. If `nums_copy[i]` is not equal to the `target` value:
      i. Increment `ops`.
      ii. Flip the signs of `nums_copy[i]` and `nums_copy[i+1]`.
   e. After the loop, check if the last element `nums_copy[n-1]` equals the `target`.
   f. If it does, and `ops <= k`, it's a possible solution. Return `true`.
   g. Otherwise, return `false`.
3. In the main function, call `check(1)` to see if it's possible to make all elements `1`.
4. If `check(1)` returns `true`, then the answer is `true`.
5. Otherwise, call `check(-1)` to see if it's possible to make all elements `-1`.
6. Return the result of `check(-1)`.

## Space-Optimized Greedy Simulation
This approach uses the same greedy logic as the previous one but optimizes the space complexity to O(1). Instead of creating a full copy of the array to simulate the flips, we can determine the required operations in a single pass without modifying the input array. We achieve this by keeping track of the 'effective value' of the current element, i.e., what its value would be after considering the cascading effect of an operation at the previous index.
**Time:** O(n). Similar to the first approach, we perform at most two passes over the array, each taking O(n) time. The total time complexity remains O(n). · **Space:** O(1). We only use a few variables to keep track of the operations count and the current effective value, regardless of the input size.
**Pros:** Highly efficient in terms of memory usage.; Maintains the same optimal O(n) time complexity.
**Cons:** The logic can be slightly less intuitive to grasp compared to the direct simulation with an auxiliary array.
### Explanation
The core idea is to simulate the greedy process without an auxiliary array. We iterate through the array and maintain the state of the current element as we process it.

Let's say we are trying to make all elements `1`. We iterate from `i = 0` to `n-2`. For each `nums[i]`, its effective value depends on whether an operation was performed at `i-1`. We can track this by maintaining a single variable, `currentVal`, which holds the value that `nums[i]` would have after all operations up to `i-1` are performed.

- We initialize `currentVal` with `nums[0]`.
- In each step of the loop (from `i=0` to `n-2`), we check `currentVal` against our `target`.
- If `currentVal` is not equal to the `target`, it means we must perform an operation at index `i`. We increment our operation count. This operation fixes the element at `i` but flips the element at `i+1`. So, for the next iteration, the effective value of the element at `i+1` will be `-nums[i+1]`. We update `currentVal` to this new value.
- If `currentVal` is equal to the `target`, no operation is needed at `i`. The effective value for the next element is simply its original value, `nums[i+1]`. We update `currentVal` accordingly.

After the loop finishes, `currentVal` will hold the final effective value of `nums[n-1]`. If it matches the target and the total operations are within the limit `k`, we've found a solution. We perform this check for both target `1` and target `-1`.

```java
class Solution {
    public boolean canMakeEqual(int[] nums, int k) {
        // Check if we can make all elements 1
        if (check(nums, k, 1)) {
            return true;
        }
        // Check if we can make all elements -1
        if (check(nums, k, -1)) {
            return true;
        }
        return false;
    }

    private boolean check(int[] nums, int k, int target) {
        int n = nums.length;
        int ops = 0;
        int currentVal = nums[0];

        for (int i = 0; i < n - 1; i++) {
            if (currentVal != target) {
                ops++;
                // The operation at 'i' flips nums[i] and nums[i+1].
                // The next element's effective value is -nums[i+1].
                currentVal = -nums[i + 1];
            } else {
                // No operation at 'i'.
                // The next element's effective value is just nums[i+1].
                currentVal = nums[i + 1];
            }
        }

        if (currentVal == target) {
            return ops <= k;
        }
        
        return false;
    }
}
```
### Algorithm
1. Define a helper function `check(target)` that calculates the minimum operations to make all elements equal to `target` in O(1) space.
2. Inside `check(target)`:
   a. Initialize `ops = 0` and `currentVal = nums[0]`.
   b. Iterate from `i = 0` to `n-2`.
   c. The `currentVal` represents the effective value of the element at index `i` after considering flips from previous operations.
   d. If `currentVal != target`:
      i. We must perform an operation at `i`. Increment `ops`.
      ii. This operation flips `nums[i+1]`. So, for the next iteration, the effective value will be `-nums[i+1]`. Update `currentVal = -nums[i+1]`.
   e. Else (`currentVal == target`):
      i. No operation is needed at `i`.
      ii. The effective value for the next iteration is simply `nums[i+1]`. Update `currentVal = nums[i+1]`.
   f. After the loop, `currentVal` holds the final effective value of `nums[n-1]`. If `currentVal == target` and `ops <= k`, return `true`.
   g. Otherwise, return `false`.
3. In the main function, call `check(1)` and `check(-1)` and return `true` if either succeeds.