Minimum Sorted Erasure Operations
Updated
Problem statement
An array is stored as a mutable list, and a pointer initially selects its first element. One operation may move the pointer to the previous element, move it to the next element, or erase the selected element. After an erasure, choose the previous or next surviving neighbor as the new pointer when one exists.
Erase every element so that the erased values form a non-decreasing sequence. Return the minimum total number of operations, counting both pointer moves and erasures.
Function
minimumEraseOperations(arr: int[]) → longExamples
Example 1
arr = [1]return = 1Erase the only element.
Example 2
arr = [1,2,3,4]return = 4Every current element is already the next required value, so four erasures are sufficient.
Example 3
arr = [2,1,3,3,2]return = 8Move to and erase 1, erase the two 2 values while crossing the larger values, then erase the two 3 values.
Constraints
1 <= arr.length <= 1000001 <= arr[i] <= 1000000000- The pointer does not wrap around either end of the list.
More Atlassian Online Assessment questions
- Planning ProductionOA · Seen Feb 2025
- K-Means ClusteringOA · Seen Feb 2025
- Count Analogous ArraysOA · Seen Mar 2024
- Get Maximum ScoreOA · Seen Mar 2024
- Better Compression 🦀OA · Seen Mar 2024
- Romanizer 🐡OA · Seen Mar 2024
- Flower Bouquets 💐OA · Seen Mar 2024
- Binary Search Tree IteratorOA · Seen Nov 2023
- Binary Tree Level Order TraversalOA · Seen Nov 2023
- Design HashMapOA · Seen Nov 2023
Similar questions at other companies
- Minimum Bridge TurnbacksBNSF Railway · OABNSF Railway interview questions
- Maximum Profit from an Increasing Price TripletOdoo · OAOdoo interview questions
- Longest Increasing Subsequence With Bounded Adjacent DifferenceGoogle · PHONE SCREENGoogle interview questions
- Longest Increasing Subsequence With Bounded Adjacent DifferenceAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Split Array to Minimize the Largest SumInfosys · OAInfosys interview questions
- Largest Consistent Visiting GroupAuxoAI · OA
- Delete K Subsets for Maximum ScoreRubrik · OARubrik interview questions
- Optimize Discount Selection Under a Point BudgetPalantir · OAPalantir interview questions
- Count Pairs with K Divisible Values in the IntervalChubb · OAChubb interview questions
- Range Maximum Subarray Sum QueriesInMobi · OAInMobi interview questions