#3576

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Transform Array to All Equal Elements

Transform Array to All Equal Elements requires careful greedy choices and validating invariants to achieve uniformity efficiently in limited operations.

array greedy

Problem Statement

Given an integer array nums containing only 1 and -1, and an integer k, determine if it is possible to make all elements equal using at most k operations. Each operation allows selecting an index i and changing nums[i] to either 1 or -1. You may choose the same index multiple times.

Your task is to decide whether all elements can be transformed to the same value while respecting the maximum number of operations k. Consider edge cases where repeated selections or alternating patterns affect the greedy choice and invariant validation.

Examples

Example 1

Input: nums = [1,-1,1,-1,1], k = 3

Output: true

We can make all elements in the array equal in 2 operations as follows:

Example 2

Input: nums = [-1,-1,-1,1,1,1], k = 5

Output: false

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

Solution Approach

Convert to Target Value

Choose 1 as the target and iterate through the array. For each -1, count the number of operations needed to change it to 1, ensuring the total does not exceed k. Repeat the same logic for -1 as the target.

Greedy Sliding Window Check

Apply a greedy window to group elements that need transformation. Flip contiguous segments optimally, tracking remaining allowed operations. This ensures the invariant that no segment requires more than k flips is preserved.

Verify Feasibility

After counting operations for both target values, check if either count is less than or equal to k. Return true if possible, otherwise return false. This final step validates the greedy choices against the operation constraint.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for a single pass counting operations towards each target. Space complexity is O(1) using counters without additional structures, both dependent on linear array length.

What Interviewers Usually Probe

Asks for operation minimization strategy using greedy plus invariant reasoning.
Checks if you handle repeated index selections correctly and do not overcount operations.
Evaluates understanding of edge cases with alternating patterns or already uniform segments.

Common Pitfalls or Variants

Common pitfalls

Ignoring the possibility of choosing the same index multiple times, leading to incorrect operation count.
Failing to consider both targets separately, missing a valid solution path.
Assuming contiguous flips always reduce operations, violating the invariant constraint in some arrangements.

Follow-up variants

Transform array with values from {1, -1, 0} to a single target with limited k operations.
Minimize operations to equalize array elements when allowed operation can flip up to m contiguous elements.
Determine maximum length prefix that can be made uniform within k operations using the same greedy invariant pattern.

FAQ

What is the key strategy for Transform Array to All Equal Elements?

Use a greedy approach by converting all elements to 1 and separately to -1, counting operations, and validating invariants against k.

Can the same index be chosen multiple times?

Yes, repeated selections are allowed and must be considered when counting the total operations needed.

What is the time complexity of the solution?

The solution iterates over the array once for each target, yielding O(n) time complexity with O(1) extra space.

How do I handle alternating patterns in nums?

Use a greedy window to flip contiguous segments while ensuring no segment requires more than k operations, maintaining the invariant.

Are there variants of this problem?

Yes, including arrays with more values, flipping multiple elements at once, or finding maximum uniform prefixes within k operations.

terminal

Solution

Solution 1: Traversal and Counting

According to the problem description, to make all elements in the array equal, all elements must be either $\textit{nums}[0]$ or $-\textit{nums}[0]$. Therefore, we design a function $\textit{check}$ to determine whether the array can be transformed into all elements equal to $\textit{target}$ with at most $k$ operations.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def canMakeEqual(self, nums: List[int], k: int) -> bool:
        def check(target: int, k: int) -> bool:
            cnt, sign = 0, 1
            for i in range(len(nums) - 1):
                x = nums[i] * sign
                if x == target:
                    sign = 1
                else:
                    sign = -1
                    cnt += 1
            return cnt <= k and nums[-1] * sign == target

        return check(nums[0], k) or check(-nums[0], k)

Continue Practicing

#3572 maximize ysum by picking a triplet of distinct xvalues #3587 minimum adjacent swaps to alternate parity #3588 find maximum area of a triangle