Problem Description

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.

Intuition

Because every operation flips two adjacent elements, the pattern of changes we make spreads through the array. To make all elements equal, all elements must end up as either 1 or -1. Since each operation flips a pair, we can think in terms of transforming the array step-by-step to one of these uniform arrays.

If we start from the left, whenever an element does not match our target value, we can perform an operation at that position to flip it (and its neighbor). This way, each operation "fixes" mismatches as we go. We just need to count how many operations are required to achieve all equal elements and check if the total is within the allowed number k. We consider both possible targets (nums[0] and -nums[0]) to see if either is reachable within k moves. This greedy process guarantees that if the goal is possible, we'll find a way by always "fixing" elements as soon as they don't match our target.

Solution Approach

The main idea is to check whether we can convert the entire array into either all 1s or all -1s in at most k moves. To do this, we define a function check(target, k) that simulates transforming the array so that every value matches target.

Here's how the process works:

• Initialize a counter cnt to track how many operations we've made, and a variable sign to simulate the current state of flipping (starting with 1).
• Loop through the array from left to right, except the last element:
  • For each i, calculate the current value as nums[i] * sign. This reflects the effect of all previous flips.
  • If this value is already equal to the target, do nothing for this element and set sign to 1.
  • Otherwise, we need to flip at this position. Increment cnt and set sign to -1, which flips the state for subsequent elements.
• After the loop, check if the number of required operations does not exceed k and the final element (after considering all flips) matches the target.

Finally, check both possibilities: making all elements equal to nums[0], or to -nums[0].

In summary:

• This approach uses a single pass (O(n)) and requires only counters and basic variables (no complex data structures).
• The greedy pattern of fixing mismatches from left to right ensures minimum operations.

Pseudocode for reference:

def check(target, k):
    cnt = 0
    sign = 1
    for i from 0 to n-2:
        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)

Example Walkthrough

Consider nums = [1, -1, 1, -1] and k = 2.

We want to see if we can make all elements the same (either all 1s or all -1s) in at most 2 operations, where each operation flips two adjacent values.

First, try making all elements 1 (target = 1):

Initial array: [1, -1, 1, -1] Let cnt = 0 (operation count), sign = 1 (current flip state)

• At index 0: nums[0] * sign = 1 * 1 = 1 (matches target 1), do nothing, sign stays 1.
• At index 1: nums[1] * sign = -1 * 1 = -1 (doesn't match target), flip at index 1:
  • Increment cnt to 1.
  • Set sign = -1 (flip for future elements).
• At index 2: nums[2] * sign = 1 * -1 = -1 (doesn't match target), flip at index 2:
  • Increment cnt to 2.
  • Set sign = -1 (flip for future elements).

After loop: nums[3] * sign = -1 * -1 = 1 (matches target) Total operations: 2, which is within k.

So, it's possible to make all elements 1 with 2 flips.

For completeness, try making all elements -1 (target = -1):

Reset cnt = 0, sign = 1.

• At index 0: nums[0] * sign = 1 * 1 = 1 (doesn't match -1), flip at index 0:
  • cnt = 1, sign = -1
• At index 1: nums[1] * sign = -1 * -1 = 1 (doesn't match -1), flip at index 1:
  • cnt = 2, sign = -1
• At index 2: nums[2] * sign = 1 * -1 = -1 (matches target), sign = 1

After loop: nums[3] * sign = -1 * 1 = -1 (matches target) Total operations: 2, still within k.

Conclusion

Both transformations are possible with 2 operations. Result: true

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the input array nums. This is because the function check iterates through the array once for each of its two calls.

The space complexity is O(1) since only a constant amount of extra space is used for variables regardless of the input size.