1144 Decrease Elements To Make Array Zigzag – Solution [Brute-Force to Best]

Here’s the question link on LeetCode 1144 Decrease Elements To Make Array Zigzag:

https://leetcode.com/problems/decrease-elements-to-make-array-zigzag/description

Brute Force – O(n × max(nums))

We have two choices:

Choice 1: Make even indices smaller than their neighbors.

[1, 4, 2, 5, 1]

Choice 2: Make odd indices smaller than their neighbors.

[4, 1, 5, 2, 6]

Let’s try both!

For every index that needs to be smaller, keep decreasing it until it’s smaller than both its neighbors.

For example:

[3, 2, 4]

If we want the middle element to be smaller:

[3, 2, 4]
[3, 1, 4]

Just one move!

We do this for both patterns and return whichever requires fewer moves.

class Solution {
public:
    int simulate(vector<int> nums, int parity) {
        int moves = 0;
        int n = nums.size();

        for(int i = parity; i < n; i += 2) {

            while((i > 0 && nums[i] >= nums[i-1]) ||
                  (i < n-1 && nums[i] >= nums[i+1])) {

                nums[i]--;
                moves++;
            }
        }

        return moves;
    }

    int movesToMakeZigzag(vector<int>& nums) {
        return min(simulate(nums, 0), simulate(nums, 1));
    }
};
1144 Decrease Elements To Make Array Zigzag Brute Force Solution

Code explained

  • simulate(nums, 0) tries making even indices smaller.
  • simulate(nums, 1) tries making odd indices smaller.
  • Keep decreasing the selected element until it’s smaller than both neighbors.
  • Count the moves and return the minimum of both attempts.

Optimal – O(n)

Wait, why are we decreasing elements one by one?

We can directly calculate how many times we need to decrease an element!

Let’s say:

[3, 5, 4]

We want the middle element to be smaller than both neighbors.

Currently, it’s 5.

The smaller neighbor is 3.

So the middle element must become 2.

[3, 2, 4]

That’s exactly 5 - 3 + 1 = 3 moves!

The formula:

max(0, nums[i] - min(left, right) + 1)

Why +1? Because we need the element to be strictly smaller than its neighbors.

Now we just calculate this cost for every even index and every odd index separately.

class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        int n = nums.size();

        int even = 0, odd = 0;

        for(int i = 0; i < n; i++) {

            int left = (i > 0) ? nums[i-1] : INT_MAX;
            int right = (i < n-1) ? nums[i+1] : INT_MAX;

            int cost = max(0, nums[i] - min(left, right) + 1);

            if(i % 2 == 0)
                even += cost;
            else
                odd += cost;
        }

        return min(even, odd);
    }
};
1144 Decrease Elements To Make Array Zigzag Optimal Solution

Code explained

  • even stores the moves needed if even indices must be smaller.
  • odd stores the moves needed if odd indices must be smaller.
  • Find the smaller of the two neighbors.
  • Calculate how many decrements are needed to become smaller than that neighbor.
  • Add the cost to either even or odd.
  • Return whichever pattern costs less.

We use INT_MAX for a missing neighbor because boundary elements only have one neighbor.

1144 Decrease Elements To Make Array Zigzag 1144 Decrease Elements To Make Array Zigzag 1144 Decrease Elements To Make Array Zigzag 1144 Decrease Elements To Make Array Zigzag 1144 Decrease Elements To Make Array Zigzag

Leave a Reply