You are given an array nums consisting of positive integers.
You can perform the following operation on the array any number of times:
nums = [1,2,3,1], you can apply one operation to make it [1,5,1].Return the minimum number of operations needed to turn the array into a palindrome.
Example 1:
Input: nums = [4,3,2,1,2,3,1] Output: 2 Explanation: We can turn the array into a palindrome in 2 operations as follows: - Apply the operation on the fourth and fifth element of the array, nums becomes equal to [4,3,2,3,3,1]. - Apply the operation on the fifth and sixth element of the array, nums becomes equal to [4,3,2,3,4]. The array [4,3,2,3,4] is a palindrome. It can be shown that 2 is the minimum number of operations needed.
Example 2:
Input: nums = [1,2,3,4] Output: 3 Explanation: We do the operation 3 times in any position, we obtain the array [10] at the end which is a palindrome.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 106Define two pointers i and j, pointing to the beginning and end of the array respectively, use variables a and b to represent the values of the first and last elements, and variable ans to represent the number of operations.
If a < b, we move the pointer i one step to the right, i.e., i \leftarrow i + 1, then add the value of the element pointed to by i to a, i.e., a \leftarrow a + nums[i], and increment the operation count by one, i.e., ans \leftarrow ans + 1.
If a > b, we move the pointer j one step to the left, i.e., j \leftarrow j - 1, then add the value of the element pointed to by j to b, i.e., b \leftarrow b + nums[j], and increment the operation count by one, i.e., ans \leftarrow ans + 1.
Otherwise, it means a = b, at this time we move the pointer i one step to the right, i.e., i \leftarrow i + 1, move the pointer j one step to the left, i.e., j \leftarrow j - 1, and update the values of a and b, i.e., a \leftarrow nums[i] and b \leftarrow nums[j].
Repeat the above process until i \ge j, return the operation count ans.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Java
C++
Go
Valid Palindrome - Leetcode 125 - Python • NeetCode • 318,354 views views
Watch 9 more video solutions →Practice Merge Operations to Turn Array Into a Palindrome with our built-in code editor and test cases.
Practice on FleetCode