Scale Engineer

Transform Array to All Equal Elements

Med
#3184Time: 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).
Patterns
Greedy
Data structures
Array

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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

Walkthrough

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.

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;    }}

Complexity

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

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem