Minimum Length After Removing Arithmetic Triples
Updated
Problem statement
You are given an integer array a.
In one operation, pick 3 consecutive elements of the current array that form an arithmetic progression and remove them. After the removal, the left and right parts join, so elements that were not next to each other before can become adjacent.
Three values x, y, z, in this order, form an arithmetic progression when y - x == z - y. The common difference may be positive, zero, or negative, so [5, 6, 7], [4, 4, 4], and [9, 8, 7] can all be removed.
You may perform any number of operations, including none. Return the minimum possible length of the array.
Function
minFinalLength(a: int[]) → intExamples
Example 1
a = [1,5,6,7,4,7]return = 0Remove (5, 6, 7): [1, 5, 6, 7, 4, 7] becomes [1, 4, 7].
Now 1, 4, and 7 are adjacent, and 4 - 1 == 7 - 4. Remove (1, 4, 7) to get [], so the answer is 0.
Example 2
a = [2,7,8,9,8,7,9]return = 1Removing (7, 8, 9) at indices 1 to 3 first leaves [2, 8, 7, 9], which has no arithmetic triple, so that order ends with length 4.
Instead, remove the decreasing triple (9, 8, 7) at indices 3 to 5. The array becomes [2, 7, 8, 9]. Then remove (7, 8, 9) to get [2].
The length is 7, and each operation removes 3 elements, so the length can never reach 0. The answer is 1.
Example 3
a = [6,4,4,4,4,2]return = 0Remove three equal values (4, 4, 4), whose common difference is 0. The array becomes [6, 4, 2].
(6, 4, 2) has common difference -2, so remove it as well. The array is empty and the answer is 0.
Constraints
1 <= a.length <= 200-10^6 <= a[i] <= 10^6
Similar questions at other companies
- Maximum Profit in Job SchedulingAmazon · PHONE SCREEN
- Fewest Fountains to Water the GardenDocuSign · OADocuSign interview questions
- Split Array to Minimize the Largest SumNation with NaMo · PHONE SCREEN
- Trapping Rain WaterOracle · PHONE SCREENOracle interview questions
- Select Transactions with Child-Pays-for-Parent PackagesCoinbase · PHONE SCREENCoinbase interview questions
- Longest Consistent Activity StreakAtlassian · PHONE SCREENAtlassian interview questions
- Longest Increasing Path in a MatrixNew Relic · PHONE SCREEN · ONSITE INTERVIEW
- Longest Increasing Subsequence With Bounded Adjacent DifferenceGoogle · PHONE SCREENGoogle interview questions
- Maximum Profit with at Most K TransactionsTekion · PHONE SCREENTekion interview questions
- Lab and Consultation Appointment MatchingAssort Health · PHONE SCREENAssort Health interview questions