# Decrease Elements To Make Array Zigzag
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/decrease-elements-to-make-array-zigzag)
Canonical: https://scaleengineer.com/dsa/problems/decrease-elements-to-make-array-zigzag
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## Problem
Given an array `nums` of integers, a _move_ consists of choosing any element and **decreasing it by 1**.

An array `A` is a _zigzag array_ if either:

* Every even-indexed element is greater than adjacent elements, ie. `A[0] > A[1] < A[2] > A[3] < A[4] > ...`
* OR, every odd-indexed element is greater than adjacent elements, ie. `A[0] < A[1] > A[2] < A[3] > A[4] < ...`

Return the minimum number of moves to transform the given array `nums` into a zigzag array.

**Example 1:**

**Input:** nums = [1,2,3]
**Output:** 2
**Explanation:** We can decrease 2 to 0 or 3 to 1.

**Example 2:**

**Input:** nums = [9,6,1,6,2]
**Output:** 4

**Constraints:**

* `1 <= nums.length <= 1000`
* `1 <= nums[i] <= 1000`

# Approaches
## Simulation with Auxiliary Arrays
This approach calculates the minimum moves for the two possible zigzag patterns separately. For each pattern, it works on a copy of the input array to calculate the total moves required. The final answer is the minimum of the costs for the two patterns. This method is straightforward but uses extra memory.
**Time:** O(N), where N is the length of the input array. We perform two separate passes, one for each pattern, and each pass iterates through roughly N/2 elements. · **Space:** O(N), where N is the length of the input array. We create two copies of the array, each of size N.
**Pros:** The logic is clear as it completely separates the computation for the two patterns.; Guaranteed to be correct as it explores both required outcomes.
**Cons:** Uses O(N) extra space to store copies of the array, which is unnecessary.
### Explanation
The problem asks for the minimum moves to make an array zigzag. A zigzag array can follow one of two patterns:
1.  `A[0] < A[1] > A[2] < A[3] > ...` (odd-indexed elements are peaks)
2.  `A[0] > A[1] < A[2] > A[3] < ...` (even-indexed elements are peaks)

Since we can only decrease elements, to make an element `A[i]` a 'peak', we must decrease its neighbors. To make `A[i]` a 'valley', we must decrease `A[i]` itself. This implies that for each pattern, the elements being modified are independent. For pattern 1, we only modify even-indexed elements. For pattern 2, we only modify odd-indexed elements.

This approach computes the cost for each pattern independently and then compares them. To ensure the calculations for one pattern do not interfere with the other, we use copies of the original array.

**For Pattern 1 (`< > < ...`):**
We iterate through the even-indexed elements (`nums[0], nums[2], ...`) on a copy of the array. For each such element `nums[i]`, it must be smaller than its neighbors. If `nums[i]` is greater than or equal to `min(left_neighbor, right_neighbor)`, we must decrease it. The number of moves is `nums[i] - (min(left_neighbor, right_neighbor) - 1)`. We sum these moves.

**For Pattern 2 (`> < > ...`):**
Similarly, we iterate through the odd-indexed elements (`nums[1], nums[3], ...`) on a second copy. For each `nums[i]`, we calculate the moves needed to make it smaller than its neighbors and sum them up.

Finally, we return the minimum of the two calculated costs.

```java
import java.util.Arrays;

class Solution {
    public int movesToMakeZigzag(int[] nums) {
        // Case 1: Make odd-indexed elements peaks (< > < ...)
        // This means we might need to decrease even-indexed elements.
        int[] nums1 = Arrays.copyOf(nums, nums.length);
        int moves1 = 0;
        for (int i = 0; i < nums1.length; i += 2) {
            int left = (i > 0) ? nums1[i - 1] : Integer.MAX_VALUE;
            int right = (i < nums1.length - 1) ? nums1[i + 1] : Integer.MAX_VALUE;
            int minNeighbor = Math.min(left, right);
            if (nums1[i] >= minNeighbor) {
                moves1 += nums1[i] - minNeighbor + 1;
            }
        }

        // Case 2: Make even-indexed elements peaks (> < > ...)
        // This means we might need to decrease odd-indexed elements.
        int[] nums2 = Arrays.copyOf(nums, nums.length);
        int moves2 = 0;
        for (int i = 1; i < nums2.length; i += 2) {
            int left = (i > 0) ? nums2[i - 1] : Integer.MAX_VALUE;
            int right = (i < nums2.length - 1) ? nums2[i + 1] : Integer.MAX_VALUE;
            int minNeighbor = Math.min(left, right);
            if (nums2[i] >= minNeighbor) {
                moves2 += nums2[i] - minNeighbor + 1;
            }
        }

        return Math.min(moves1, moves2);
    }
}
```
### Algorithm
- Create two copies of the input array, `nums1` and `nums2`.
- **Calculate moves for the first zigzag pattern (`< > < ...`):**
  - Initialize `moves1 = 0`.
  - Iterate through `nums1` at even indices (`i = 0, 2, 4, ...`).
  - For each `nums1[i]`, find the minimum of its neighbors. Use a very large number if a neighbor is out of bounds.
  - If `nums1[i]` is not smaller than its minimum neighbor, calculate the necessary moves (`nums1[i] - minNeighbor + 1`) and add to `moves1`.
- **Calculate moves for the second zigzag pattern (`> < > ...`):**
  - Initialize `moves2 = 0`.
  - Iterate through `nums2` at odd indices (`i = 1, 3, 5, ...`).
  - For each `nums2[i]`, find the minimum of its neighbors.
  - If `nums2[i]` is not smaller than its minimum neighbor, calculate the necessary moves and add to `moves2`.
- Return the minimum of `moves1` and `moves2`.

## Single Pass Calculation with Constant Space
This optimal approach calculates the costs for both zigzag patterns in-place, without creating any copies of the array. It iterates through the array twice, once for each pattern, calculating the required moves based on the original values of the elements. This achieves the same result as the previous approach but with constant space complexity.
**Time:** O(N), where N is the number of elements in the array. We perform two passes over the array, each taking linear time. · **Space:** O(1). We only use a few integer variables to store the running costs, which does not depend on the size of the input array.
**Pros:** Achieves optimal O(1) space complexity.; Highly efficient with a time complexity of O(N).; The logic is self-contained and does not require helper functions or complex data structures.
**Cons:** The code combines two loops which might look slightly less modular than a helper function approach, but it's a minor style point.
### Explanation
This approach is based on the same core logic: the problem can be solved by finding the minimum cost to satisfy either of the two zigzag patterns. The key improvement is realizing that the calculations for each element are independent and can be performed on the original, unmodified array, thus avoiding the need for extra space.

We use two variables, `moves1` and `moves2`, to accumulate the costs for each pattern.

**To calculate `moves1` (for pattern `< > < > ...`):**
We iterate through the even indices of the `nums` array (`i = 0, 2, 4, ...`). At each `i`, `nums[i]` needs to be a 'valley'. We look at its neighbors, `nums[i-1]` and `nums[i+1]`. If `nums[i]` is not smaller than `min(nums[i-1], nums[i+1])`, we calculate the number of moves to make it so and add it to `moves1`. The calculation for `nums[i+2]` will use the original `nums[i+1]`, which is correct because the 'peak' elements are never modified in this scenario.

**To calculate `moves2` (for pattern `> < > < ...`):**
We do the same for the odd indices (`i = 1, 3, 5, ...`), accumulating the cost in `moves2`.

Finally, the minimum of `moves1` and `moves2` is the answer. This method is efficient in both time and space.

```java
class Solution {
    public int movesToMakeZigzag(int[] nums) {
        int n = nums.length;
        int moves1 = 0; // Cost for pattern: < > < > ... (decrease even indices)
        int moves2 = 0; // Cost for pattern: > < > < ... (decrease odd indices)

        // Temporary array to not modify the original during calculation for the second case
        int[] temp = nums.clone();

        // Calculate moves for pattern < > < > ... (decrease even indices)
        for (int i = 0; i < n; i += 2) {
            int left = (i > 0) ? temp[i - 1] : Integer.MAX_VALUE;
            int right = (i < n - 1) ? temp[i + 1] : Integer.MAX_VALUE;
            int minNeighbor = Math.min(left, right);
            if (temp[i] >= minNeighbor) {
                moves1 += temp[i] - minNeighbor + 1;
            }
        }

        // Calculate moves for pattern > < > < ... (decrease odd indices)
        for (int i = 1; i < n; i += 2) {
            int left = (i > 0) ? nums[i - 1] : Integer.MAX_VALUE;
            int right = (i < n - 1) ? nums[i + 1] : Integer.MAX_VALUE;
            int minNeighbor = Math.min(left, right);
            if (nums[i] >= minNeighbor) {
                moves2 += nums[i] - minNeighbor + 1;
            }
        }

        return Math.min(moves1, moves2);
    }
}
```
*Correction*: A more optimized version would not even need the `temp` array. The calculations can be done on the original `nums` array for both loops since the loops are independent and don't modify the array.

```java
class Solution {
    public int movesToMakeZigzag(int[] nums) {
        int n = nums.length;
        int moves1 = 0; // Cost for pattern: < > < > ...
        int moves2 = 0; // Cost for pattern: > < > < ...

        // Calculate moves for pattern where even indices are valleys
        for (int i = 0; i < n; i += 2) {
            int left = (i > 0) ? nums[i - 1] : Integer.MAX_VALUE;
            int right = (i < n - 1) ? nums[i + 1] : Integer.MAX_VALUE;
            int minNeighbor = Math.min(left, right);
            if (nums[i] >= minNeighbor) {
                moves1 += nums[i] - minNeighbor + 1;
            }
        }

        // Calculate moves for pattern where odd indices are valleys
        for (int i = 1; i < n; i += 2) {
            int left = nums[i - 1]; // i is always > 0 here
            int right = (i < n - 1) ? nums[i + 1] : Integer.MAX_VALUE;
            int minNeighbor = Math.min(left, right);
            if (nums[i] >= minNeighbor) {
                moves2 += nums[i] - minNeighbor + 1;
            }
        }

        return Math.min(moves1, moves2);
    }
}
```
### Algorithm
- Initialize two variables, `moves1` and `moves2`, to 0. These will store the costs for the two zigzag patterns.
- **Calculate cost for the first pattern (`< > < ...`):**
  - Iterate through the original array `nums` at even indices (`i = 0, 2, 4, ...`).
  - For each `nums[i]`, determine its left and right neighbors from the original array. Use a large value if a neighbor is out of bounds.
  - Calculate the minimum of the two neighbors, `minNeighbor`.
  - If `nums[i] >= minNeighbor`, calculate the required moves (`nums[i] - minNeighbor + 1`) and add it to `moves1`.
- **Calculate cost for the second pattern (`> < > ...`):**
  - Iterate through the original array `nums` at odd indices (`i = 1, 3, 5, ...`).
  - Repeat the process: find `minNeighbor` for `nums[i]` and calculate the moves needed, adding them to `moves2`.
- Return the minimum of `moves1` and `moves2`.

# Solutions
### CSharp

```csharp
public class Solution { public int MovesToMakeZigzag ( int [] nums ) { int [] ans = new int [ 2 ]; int n = nums . Length ; for ( int i = 0 ; i < 2 ; ++ i ) { for ( int j = i ; j < n ; j += 2 ) { int d = 0 ; if ( j > 0 ) { d = Math . Max ( d , nums [ j ] - nums [ j - 1 ] + 1 ); } if ( j < n - 1 ) { d = Math . Max ( d , nums [ j ] - nums [ j + 1 ] + 1 ); } ans [ i ] += d ; } } return Math . Min ( ans [ 0 ], ans [ 1 ]); } }
```

### Java

```java
class Solution {
public
  int movesToMakeZigzag(int[] nums) {
    int[] ans = new int[2];
    int n = nums.length;
    for (int i = 0; i < 2; ++i) {
      for (int j = i; j < n; j += 2) {
        int d = 0;
        if (j > 0) {
          d = Math.max(d, nums[j] - nums[j - 1] + 1);
        }
        if (j < n - 1) {
          d = Math.max(d, nums[j] - nums[j + 1] + 1);
        }
        ans[i] += d;
      }
    }
    return Math.min(ans[0], ans[1]);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int movesToMakeZigzag(vector<int> &nums) {
    vector<int> ans(2);
    int n = nums.size();
    for (int i = 0; i < 2; ++i) {
      for (int j = i; j < n; j += 2) {
        int d = 0;
        if (j)
          d = max(d, nums[j] - nums[j - 1] + 1);
        if (j < n - 1)
          d = max(d, nums[j] - nums[j + 1] + 1);
        ans[i] += d;
      }
    }
    return min(ans[0], ans[1]);
  }
};

```

### Python

```python
class Solution:
    def movesToMakeZigzag(self, nums: List[int]) -> int: ans = [0, 0] n = len(nums) for i in range(2): for j in range(i, n, 2): d = 0 if j: d = max(d, nums[j] - nums[j - 1] + 1) if j < n - 1: d = max(d, nums[j] - nums[j + 1] + 1) ans[i] += d return min(ans)

```