Decrease Elements To Make Array Zigzag - Video Solutions

Problem Overview: You’re given an integer array and can only decrease values. The goal is to transform the array into a zigzag pattern with the minimum number of decrement operations. A zigzag array means either nums[0] < nums[1] > nums[2] < nums[3]... or nums[0] > nums[1] < nums[2] > nums[3].... The task is to compute the minimum total decrements required to achieve either pattern.

Approach 1: Brute Force Neighbor Adjustment (O(n), O(1))

Check both valid zigzag configurations separately. For one pass, enforce that even indices are valleys (nums[i] < nums[i-1] and nums[i] < nums[i+1]), and for the other pass enforce the same rule for odd indices. For each index, compare the value with its neighbors and calculate how much it must be decreased to become strictly smaller than the minimum neighbor. Accumulate the required decrements without modifying the original array. This works because decreasing one element never breaks the constraint for other indices when evaluated independently.

Approach 2: Pattern-Based Greedy Adjustment (O(n), O(1))

This is the optimal greedy strategy. Instead of modifying the array, compute the cost of making each index the "valley" of the zigzag pattern. For index i, find the smallest neighbor among nums[i-1] and nums[i+1]. If nums[i] is not already smaller, calculate the decrements required to make it minNeighbor - 1. Sum these costs for all indices of the same parity (even or odd). Since a valid zigzag can start with either a peak or valley, run this calculation twice: once assuming even indices are valleys and once assuming odd indices are valleys. Return the smaller cost. The algorithm scans the array once per pattern and uses only constant extra memory, making it efficient for large inputs.

The core insight: only the valley positions need adjustment. Peaks automatically satisfy the constraint if their neighboring valleys are smaller. By computing the minimal decrement needed relative to neighbors, the algorithm avoids unnecessary changes and keeps the solution linear.

This problem is a good exercise in recognizing local constraints in array problems and applying a simple greedy decision at each index.

Recommended for interviews: The pattern-based greedy approach is what interviewers expect. It shows you can reason about local constraints and reduce the problem to two deterministic passes. Explaining both zigzag patterns first demonstrates complete understanding, then implementing the O(n) greedy calculation shows practical problem-solving skill.