1144. Decrease Elements To Make Array Zigzag

Problem Description

In this problem, we're given an array of integers called nums. Our task is to make the array into a zigzag array with the least number of moves. A zigzag array is defined in one of the following two ways:

Even-index Zigzag: For every even index i, the element at i is greater than its adjacent elements (nums[i] > nums[i - 1] and nums[i] > nums[i + 1]), like A[0] > A[1] < A[2] > A[3] < A[4] > ....
Odd-index Zigzag: For every odd index i, the element at i is greater than its adjacent elements (nums[i] > nums[i - 1] and nums[i] > nums[i + 1]), like A[0] < A[1] > A[2] < A[3] > A[4] < ....

A move consists of choosing any element of the array and decreasing its value by 1. The goal is to find out the minimum number of such moves required to achieve a zigzag pattern.

Intuition

To solve this problem, we can approach it by considering the two possible patterns of zigzag separately (even-index zigzag and odd-index zigzag), then choose the one which requires the fewest moves.

We can iterate through every even index i and check if nums[i] is already greater than its adjacent elements. If not, we calculate the difference by how much nums[i] needs to be decreased to satisfy the zigzag condition. We add this difference to our total moves for even-index zigzag pattern.
Similarly, we iterate through every odd index i doing the same check and calculation for the moves required to transform array nums into an odd-index zigzag pattern.

An important point to note is that when checking for the zigzag condition, we only need to ensure that each chosen element (nums[i] for even or odd i) is greater than its adjacent elements if they exist. This implies that for the first and last elements, we only consider one adjacent element.

After calculating moves for both patterns, we return the minimum of the two totals as the answer. This way, we ensure that we find the zigzag array that requires the least amount of modification (moves).

Learn more about Greedy patterns.

Solution Approach

The solution approach for converting an array nums into a zigzag array is as follows:

We utilize a list ans with two elements initialized to 0. These two elements represent the minimum number of moves required for turning nums into an even-index zigzag array (first element of ans) and an odd-index zigzag array (second element of ans), respectively.
We iterate through the array twice, first starting at index 0 for even-index zigzag array, and then starting at index 1 for odd-index zigzag array. This aligns with the two possible zigzag patterns.
For each iteration (for even and odd patterns), we loop through the appropriate indices (i for even and i+1 for odd) with step 2, to only look at the elements that should be larger than their neighbors.
At each selected index j, we calculate the amount to decrease the current element nums[j] to make it lower than both of its neighbors if they exist. This is done with two if conditions:
- If j is not the first element (j > 0), we calculate the required decrease to ensure nums[j] is greater than nums[j - 1], which is nums[j] - nums[j - 1] + 1.
- If j is not the last element (j < n - 1), we calculate the required decrease to ensure nums[j] is greater than nums[j + 1], which is nums[j] - nums[j + 1] + 1.
The amount d is the maximum of the decreases required for both sides (left and right) of the current element nums[j]. Only one side is considered if j is at the boundary of the array.
We accumulate the total decreases in ans[i] for each iteration pattern (0 for even-indexed and 1 for odd-indexed zigzag).
After the loops, ans contains two numbers: the total moves to make the nums array a zigzag array by promoting even-indexed elements and the total moves to make it a zigzag array by promoting odd-indexed elements.
The final result is the minimum of the values in ans, which represents the minimum number of moves to convert nums into a zigzag array, regardless of whether we are following the even-indexed or odd-indexed pattern.

This approach efficiently computes the desired outcome using array manipulation and condition checking without the need for complex data structures or advanced algorithms. The simplicity of this solution lies in the clever use of iteration, conditionals, and element comparison to meet the zigzag pattern requirements with a minimal number of moves.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example array nums:

nums = [4, 3, 7, 6, 2]

We want to convert this array into either an even-index zigzag or an odd-index zigzag array in the least number of moves possible, following the solution approach described earlier.

Transforming into Even-Index Zigzag

Starting with index 0 (even), the selected indices will be 0, 2, 4, hence we check and modify only these indices.

At index 0, nums[0] is 4. Since there is no element at -1, we only need to compare it to nums[1]. No moves are required here because 4 > 3.
At index 2, nums[2] is 7. It is already greater than both its neighbors nums[1] and nums[3]. No moves required.
At index 4, nums[4] is 2. Since there is no element at index 5, we only compare with nums[3]. We need to decrease nums[3] (6) to at least 1 for it to be smaller than nums[4]. Therefore, 6 - 2 + 1 is 5 moves required.

Total moves required for the even-index zigzag is 0 + 0 + 5 = 5.

Transforming into Odd-Index Zigzag

Now, starting with index 1 (odd), the selected indices to check will be 1, 3.

At index 1, nums[1] is 3. We need to reduce it to 3 to less than nums[0] (4). Hence no moves required as 4 > 3.
At index 3, nums[3] is 6. It should be greater than nums[2] (7) but it's not. So, we need to decrease nums[2] to 5 (nums[3] - nums[2] + 1), which is 6 - 7 + 1 = 0 moves. Additionally, nums[3] should also be greater than nums[4] (2), but it already is, so no further moves required.

Total moves required for the odd-index zigzag is 0 + 0 = 0.

Conclusion

Comparing both patterns, odd-index zigzag requires 0 moves and even-index zigzag requires 5 moves. Hence, the minimum number of moves required to make the given nums a zigzag array is 0.

Using the solution approach, we can thus determine that the original array is already an odd-index zigzag array and no moves are needed.

Solution Implementation

1class Solution:
2    def movesToMakeZigzag(self, nums: List[int]) -> int:
3        # Initialize a list to store the number of moves for two scenarios:
4        # 1. Making the first element higher than its neighbors (odd indexed after the first)
5        # 2. Making the second element higher than its neighbors (even indexed after the first)
6        moves_required = [0, 0]
7      
8        # Get the length of the input list
9        num_elements = len(nums)
10      
11        # Loop over the two scenarios: starting with the first and second elements
12        for index in range(2):
13            # Now, check the elements that need to be adjusted according to the scenario
14            for j in range(index, num_elements, 2):
15                # Initialize the variable to record the number of moves to make the
16                # current element lower than its neighbors
17                difference = 0
18              
19                # If not the first element, compare with the left neighbor
20                if j > 0:
21                    # Calculate the required moves to ensure nums[j] is less than nums[j - 1]
22                    difference = max(difference, nums[j] - nums[j - 1] + 1)
23              
24                # If not the last element, compare with the right neighbor
25                if j < num_elements - 1:
26                    # Adjust the number of moves to ensure nums[j] is less than nums[j + 1]
27                    difference = max(difference, nums[j] - nums[j + 1] + 1)
28              
29                # Add the calculated moves for this element to the total for this scenario
30                moves_required[index] += difference
31      
32        # Return the minimum number of moves required between the two scenarios
33        return min(moves_required)
34

1class Solution {
2    public int movesToMakeZigzag(int[] nums) {
3        int[] movesRequired = new int[2]; // This array will hold the moves required for the two cases.
4        int n = nums.length; // The length of the input array.
5      
6        // Loop through the two different cases:
7        // Case 0: Making the even-indexed elements lower ('Zig')
8        // Case 1: Making the odd-indexed elements lower ('Zag')
9        for (int caseIndex = 0; caseIndex < 2; ++caseIndex) {
10            // Inner loop to go through elements based on the current case:
11            // Either start from index 0 for even ('Zig'), or index 1 for odd ('Zag')
12            for (int currentIndex = caseIndex; currentIndex < n; currentIndex += 2) {
13                int decrement = 0; // This will store the required decrement for the current element.
14              
15                // If not the first element, check with the previous element
16                if (currentIndex > 0) {
17                    decrement = Math.max(decrement, nums[currentIndex] - nums[currentIndex - 1] + 1);
18                }
19              
20                // If not the last element, check with the next element
21                if (currentIndex < n - 1) {
22                    decrement = Math.max(decrement, nums[currentIndex] - nums[currentIndex + 1] + 1);
23                }
24              
25                // Increment the moves count for the current case by the decrement calculated
26                movesRequired[caseIndex] += decrement;
27            }
28        }
29      
30        // Return the minimum of the two cases as the result
31        return Math.min(movesRequired[0], movesRequired[1]);
32    }
33}
34

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to calculate the minimum moves to make the array 'nums' a zigzag sequence.
7    int movesToMakeZigzag(std::vector<int>& nums) {
8        // Initializing answer array for the two scenarios.
9        // ans[0] is for the scenario where the first element is less than the second.
10        // ans[1] is for the scenario where the first element is greater than the second.
11        std::vector<int> ans(2, 0);
12
13        // Size of the input array.
14        int n = nums.size();
15
16        // Outer loop for the two possible zigzag patterns (starting with lower or higher).
17        for (int pattern = 0; pattern < 2; ++pattern) {
18            // Inner loop to iterate over the array with step of 2 to maintain zigzag.
19            for (int i = pattern; i < n; i += 2) {
20                int decrement = 0;
21
22                // Check if there is a previous element, and if so, make 'nums[i]' less than 'nums[i - 1]'.
23                // Increment the decrement count appropriately.
24                if (i > 0) {
25                    decrement = std::max(decrement, nums[i] - nums[i - 1] + 1);
26                }
27
28                // Check if there is a next element, and if so, make 'nums[i]' less than 'nums[i + 1]'.
29                // Increment the decrement count appropriately.
30                if (i < n - 1) {
31                    decrement = std::max(decrement, nums[i] - nums[i + 1] + 1);
32                }
33
34                // Add the required decrement to maintain the zigzag pattern for this position to the answer.
35                ans[pattern] += decrement;
36            }
37        }
38
39        // Return the minimum of the two answers.
40        return std::min(ans[0], ans[1]);
41    }
42};
43

1// Function to calculate the minimum number of moves required to form a zigzag sequence
2function movesToMakeZigzag(nums: number[]): number {
3    // Initialize an array to store the minimum moves for both patterns
4    const minMoves: number[] = Array(2).fill(0);
5    // Get the length of the nums array
6    const length = nums.length;
7
8    // Loop for odd and even indices separately
9    for (let pattern = 0; pattern < 2; ++pattern) {
10        // Start from 0 or 1 index based on the pattern and increment by 2
11        for (let index = pattern; index < length; index += 2) {
12            let difference = 0; // Difference needed to make the current element smaller
13
14            // If there is a previous element and it is not less than the current one
15            if (index > 0) {
16                difference = Math.max(difference, nums[index] - nums[index - 1] + 1);
17            }
18            // If there is a next element and it is not less than the current one
19            if (index < length - 1) {
20                difference = Math.max(difference, nums[index] - nums[index + 1] + 1);
21            }
22            // Add the required difference to the moves count for the current pattern
23            minMoves[pattern] += difference;
24        }
25    }
26    // Return the minimum of the two patterns' moves counts
27    return Math.min(...minMoves);
28}
29

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(n), where n is the length of the input list nums. This is because the code contains two nested loops. The outer loop runs twice (once for each of the two possible zigzag configurations), and the inner loop iterates over every other element of the list. Since at most, each element is considered once per outer loop iteration, the total number of operations is proportional to the size of the input list, resulting in a linear time complexity.

Space Complexity

The space complexity is O(1), meaning it requires constant additional space regardless of the input size. The array ans stores only two elements corresponding to the two possible zigzag configurations, making its size fixed. The variables d and n also do not depend on the input size, so the memory usage does not grow with the size of nums.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know