2422. Merge Operations to Turn Array Into a Palindrome
Problem Description
You are given an array called nums
that contains only positive integers. Your task is to make this array a palindrome. A palindrome is a sequence that reads the same forward and backward. To do this, you are allowed to perform as many operations as you want. An operation consists of selecting any two adjacent elements in nums
and replacing them with their sum. The goal is to find the minimum number of such operations required to turn the array into a palindrome.
Intuition
The key to solving this problem lies in understanding how a palindrome is structured: the values on the left side of the array must be mirrored on the right side. The strategy is to iteratively make the sums of the values from both ends (left and right) of the array equal, so they form a palindrome.
To implement this strategy, two pointers approach is used, one starting at the left end (beginning of the array) and one at the right end (end of the array). We compare the sums of the elements at these pointers.
- If the left sum is less than the right sum, this means we need to increase the left sum by moving the left pointer to the right and adding the value at the new pointer position to the left sum, counting this action as one operation.
- Conversely, if the right sum is less than the left sum, we move the right pointer to the left, add the value at the new pointer to the right sum, and count it as an operation as well.
- When both sums are equal, we effectively have a palindrome within those boundaries. We move both pointers inward, skipping over the elements we just confirmed as part of the palindrome because they do not need any more operations.
- This process repeats until the pointers meet, which would mean the entire array has become a palindrome.
The trick here is that we donāt need to actually replace numbers or keep track of the modified array; instead, we just need to know the count of operations required, which is tallied every time we move either pointer to adjust the sums.
The solution's complexity is O(n), where n is the length of the array, because we possibly go through the array only once with our two pointers.
Learn more about Greedy and Two Pointers patterns.
Solution Approach
The solution uses a two-pointers algorithm to walk through the array from both ends towards the center. This approach helps in reducing the problem to smaller subproblems by considering the current sum at both ends. Here's a step-by-step walkthrough:
- Initialize two pointers,
i
at the start andj
at the end of the array. - Initialize two variables,
a
andb
, to keep track of the sum of the numbers pointed byi
andj
. Initially,a
is assignednums[i]
, andb
is assignednums[j]
. - Initialize a counter
ans
with the value 0 to keep track of the number of operations performed. - Enter a while loop, which will continue to execute as long as
i < j
(ensuring that we are not comparing the same element with itself or crossing over, which would mean the entire array is a palindrome):- Compare the values of
a
andb
. - If
a
<b
, we need to increasea
to eventually matchb
. We do so by incrementingi
(move the left pointer to the right), addingnums[i]
toa
, and incrementing the counterans
to represent an operation performed. - If
b
<a
, similarly, we need to increaseb
to matcha
. Decrementj
(move the right pointer to the left), addnums[j]
tob
, and increment the counterans
. - If
a
==b
, it means that the values fromnums[i]
tonums[j]
can be part of the palindrome. Therefore, we incrementi
, decrementj
, and updatea
andb
with the values at the new indicesnums[i]
andnums[j]
, respectively. No operation is counted in this case asa
andb
are already equal.
- Compare the values of
- Continue the loop until all elements have been accounted for in pairs that form the palindrome.
- The iterator
ans
is returned as it now contains the minimum number of operations needed to make the array a palindrome.
This simple yet elegant solution leverages the two-pointer technique, which is efficient when you need to compare or pair up elements from opposite ends of an array. It skillfully avoids the need for extra space to store interim arrays, mutating only counters and making the solution very space-efficient (O(1) space complexity).
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 an example to understand the solution approach:
Suppose we are given the following array nums
:
nums = [1, 3, 4, 2, 2]
To make nums
a palindrome using the fewest operations, we will follow the steps outlined:
- Initialize two pointers,
i
at the start (0) andj
at the end (4) of the array. - Initialize variables
a
withnums[i]
(which is 1) andb
withnums[j]
(which is 2). - Initialize the operation counter
ans
to 0.
So, the initial setting looks like:
i = 0 ā [1, 3, 4, 2, 2] ā j = 4 a = 1 b = 2 ans = 0
Now, we start iterating:
- Since
a
(1) <b
(2), we incrementi
to 1 and updatea
by addingnums[i]
, which makesa = 1 + 3 = 4
andans
becomes 1. - At this point,
a
(4) ==b
(2), but for the array to be palindrome,a
andb
must have the same sum. Thus, we decreasej
to 3 and updateb
by addingnums[j]
, nowb = 2 + 2 = 4
, andans
becomes 2. - Now
a
(4) ==b
(4), so we incrementi
to 2, and decrementj
to 2, effectively skipping over the elements we just confirmed to form the correct structure in our palindrome.
Finally, since i
now equals j
, we've considered the entire array, so we finish.
At the end of the process, ans
equals 2, indicating the minimum number of operations required to turn the array into a palindrome.
So, our example array nums
can be transformed into a palindrome with a minimum of 2 operations:
- Combine
nums[0]
andnums[1]
to form[4, 4, 2, 2]
- Combine
nums[2]
andnums[3]
to form[4, 6, 2]
- No further operations are needed, as
[4, 6, 2]
is already a palindrome.
Solution Implementation
1from typing import List
2
3class Solution:
4 def minimumOperations(self, nums: List[int]) -> int:
5 # Initialize two pointers for the start and end of the list
6 left_index, right_index = 0, len(nums) - 1
7
8 # Initialize the sums of elements from the start and from the end
9 left_sum, right_sum = nums[left_index], nums[right_index]
10
11 # Initialize a variable to count the number of operations performed
12 operations_count = 0
13
14 # Loop until the two pointers meet or cross each other
15 while left_index < right_index:
16
17 # If the sum on the left is less than the sum on the right,
18 # move the left pointer to the right and add the new element to left_sum
19 if left_sum < right_sum:
20 left_index += 1
21 left_sum += nums[left_index]
22 operations_count += 1
23 # If the sum on the right is less than the sum on the left,
24 # move the right pointer to the left and add the new element to right_sum
25 elif right_sum < left_sum:
26 right_index -= 1
27 right_sum += nums[right_index]
28 operations_count += 1
29 # If the sums are equal, move both pointers and update the sums
30 else:
31 left_index += 1
32 right_index -= 1
33 # Check if pointers are still within the array bounds
34 if left_index < right_index:
35 left_sum = nums[left_index]
36 right_sum = nums[right_index]
37
38 # Return the total number of operations to make segments equal
39 return operations_count
40
1class Solution {
2
3 /**
4 * Find minimum number of operations to make sum of elements on the left
5 * equal to the sum of elements on the right.
6 *
7 * @param nums Array of integers.
8 * @return The minimum number of operations required.
9 */
10 public int minimumOperations(int[] nums) {
11 // Initialize pointers for the left and right parts.
12 int leftIndex = 0;
13 int rightIndex = nums.length - 1;
14
15 // Initialize sums for the left and right parts.
16 long leftSum = nums[leftIndex];
17 long rightSum = nums[rightIndex];
18
19 // Variable to keep track of the number of operations performed.
20 int operationsCount = 0;
21
22 // Loop until the pointers meet.
23 while (leftIndex < rightIndex) {
24 // If the left sum is smaller, move the left pointer to the right and add the value to leftSum.
25 if (leftSum < rightSum) {
26 leftSum += nums[++leftIndex];
27 operationsCount++;
28 // If the right sum is smaller, move the right pointer to the left and add the value to rightSum.
29 } else if (rightSum < leftSum) {
30 rightSum += nums[--rightIndex];
31 operationsCount++;
32 // If both sums are equal, move both pointers and reset the sums.
33 } else {
34 // Ensure that we do not cross the pointers.
35 if (leftIndex + 1 < rightIndex - 1) {
36 leftSum = nums[++leftIndex];
37 rightSum = nums[--rightIndex];
38 } else {
39 // Pointers will cross after this step, hence we should break the loop.
40 break;
41 }
42 }
43 }
44
45 // Return the number of operations performed to make the sums equal.
46 return operationsCount;
47 }
48}
49
1class Solution {
2public:
3 int minimumOperations(vector<int>& nums) {
4 // Initialize two pointers from both ends of the array
5 int leftIndex = 0, rightIndex = nums.size() - 1;
6 // Initialize sum variables for the two pointers
7 long leftSum = nums[leftIndex], rightSum = nums[rightIndex];
8 // Initialize a variable to count the number of operations performed
9 int operationCount = 0;
10
11 // Loop until the two pointers meet
12 while (leftIndex < rightIndex) {
13 if (leftSum < rightSum) {
14 // If the left sum is smaller, move the left pointer to the right
15 // and add the next number to the left sum.
16 leftSum += nums[++leftIndex];
17 // Increment the number of operations
18 ++operationCount;
19 } else if (rightSum < leftSum) {
20 // If the right sum is smaller, move the right pointer to the left
21 // and add the next number to the right sum.
22 rightSum += nums[--rightIndex];
23 // Increment the number of operations
24 ++operationCount;
25 } else {
26 // If the sums are equal, move both pointers towards the centre
27 // and start the next comparisons with the next outermost numbers
28 leftSum = nums[++leftIndex];
29 rightSum = nums[--rightIndex];
30 }
31 }
32 // Return the number of operations performed to make sums equal
33 return operationCount;
34 }
35};
36
1/**
2 * Calculates the minimum number of operations to make the left sum
3 * and right sum equal by only moving elements from one end to the other.
4 * @param nums - The array of numbers.
5 * @return The number of operations needed to equate the two sums.
6 */
7function minimumOperations(nums: Array<number>): number {
8 // Initialize pointers for both ends of the array
9 let leftIndex: number = 0;
10 let rightIndex: number = nums.length - 1;
11
12 // Initialize sum variables for the pointers
13 let leftSum: number = nums[leftIndex];
14 let rightSum: number = nums[rightIndex];
15
16 // Initialize the count of operations
17 let operationCount: number = 0;
18
19 // Loop until the pointers meet or cross
20 while (leftIndex < rightIndex) {
21 if (leftSum < rightSum) {
22 // If left sum is smaller, include the next element into the left sum
23 leftSum += nums[++leftIndex];
24 operationCount++;
25 } else if (rightSum < leftSum) {
26 // If right sum is smaller, include the next element into the right sum
27 rightSum += nums[--rightIndex];
28 operationCount++;
29 } else {
30 // If sums are equal, move to the next elements
31 leftSum = nums[++leftIndex];
32 rightSum = nums[--rightIndex];
33 }
34 }
35
36 // Return the total number of operations performed
37 return operationCount;
38}
39
Time and Space Complexity
Time Complexity
The given code iterates through the nums
list using two pointers i
and j
that start at opposite ends of the list and move towards the center.
The main loop runs while i < j
, so in the worst case, it may iterate through all the elements once. Therefore, the worst-case time complexity is O(n)
, where n
is the number of elements in the nums
list.
In each iteration of the while loop, the code performs constant-time operationsācomparisons and basic arithmeticāso these do not affect the overall O(n)
time complexity.
Space Complexity
Since the algorithm operates in place and the amount of additional memory used does not depend on the input size (nums
list), the space complexity is O(1)
. Only a fixed number of variables i
, j
, a
, b
, and ans
are used, which occupies constant space irrespective of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Is the following code DFS or BFS?
void search(Node root) { if (!root) return; visit(root); root.visited = true; for (Node node in root.adjacent) { if (!node.visited) { search(node); } } }
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
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
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
Want a Structured Path to Master System Design Too? Donāt Miss This!