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 ati
is greater than its adjacent elements (nums[i] > nums[i - 1]
andnums[i] > nums[i + 1]
), likeA[0] > A[1] < A[2] > A[3] < A[4] > ...
. -
Odd-index Zigzag: For every odd index
i
, the element ati
is greater than its adjacent elements (nums[i] > nums[i - 1]
andnums[i] > nums[i + 1]
), likeA[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 ifnums[i]
is already greater than its adjacent elements. If not, we calculate the difference by how muchnums[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 arraynums
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 turningnums
into an even-index zigzag array (first element ofans
) and an odd-index zigzag array (second element ofans
), 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 andi+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 elementnums[j]
to make it lower than both of its neighbors if they exist. This is done with twoif
conditions:-
If
j
is not the first element (j > 0
), we calculate the required decrease to ensurenums[j]
is greater thannums[j - 1]
, which isnums[j] - nums[j - 1] + 1
. -
If
j
is not the last element (j < n - 1
), we calculate the required decrease to ensurenums[j]
is greater thannums[j + 1]
, which isnums[j] - nums[j + 1] + 1
.
-
-
The amount
d
is the maximum of the decreases required for both sides (left and right) of the current elementnums[j]
. Only one side is considered ifj
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 thenums
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 convertnums
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 EvaluatorExample Walkthrough
Let's consider a small example array nums
:
1nums = [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]
is4
. Since there is no element at-1
, we only need to compare it tonums[1]
. No moves are required here because4 > 3
. - At index
2
,nums[2]
is7
. It is already greater than both its neighborsnums[1]
andnums[3]
. No moves required. - At index
4
,nums[4]
is2
. Since there is no element at index5
, we only compare withnums[3]
. We need to decreasenums[3]
(6
) to at least1
for it to be smaller thannums[4]
. Therefore,6 - 2 + 1
is5
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]
is3
. We need to reduce it to3
to less thannums[0]
(4
). Hence no moves required as4 > 3
. - At index
3
,nums[3]
is6
. It should be greater thannums[2]
(7
) but it's not. So, we need to decreasenums[2]
to5
(nums[3] - nums[2] + 1
), which is6 - 7 + 1 = 0
moves. Additionally,nums[3]
should also be greater thannums[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.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first