Minimum Contiguous Replacements
Updated
Problem statement
You are given an array arr of integers. In one operation, choose two distinct values x and y that currently appear in the array, then replace every occurrence of x with y.
Return the minimum number of operations needed to make the array valid.
An array is valid if every distinct value forms exactly one contiguous block. Values do not all need to become the same.
For example, [1,1,2,2,3] is valid, while [1,2,1,3] is not valid because value 1 appears in two separated blocks.
Function
minOperations(arr: int[]) → int Complete minOperations.
int arr[n]: the array to transform
Returns int: the minimum number of replacement operations.
Examples
Example 1
arr = [1,2,1]return = 1Replace every occurrence of 2 with 1, producing [1,1,1].
Example 2
arr = [1,2,3,1,2,3]return = 2One valid sequence is to replace all 2s with 1, then replace all 3s with 1.
Example 3
arr = [1,2,1,2]return = 1Replacing every occurrence of either value with the other makes the array one contiguous block.
Constraints
- 1 <= arr.length <= 1000
- 1 <= arr[i] <= 1000
More Amazon Online Assessment questions
- Get Smallest Base SegmentOA · Seen Nov 2026
- Minimum Cost of Left and Right PropagationOA · Seen Nov 2026
- Minimum Grid InconvenienceOA · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
- Maximize Shipment Order by Sorting One WindowOA · Seen Nov 2026
- Maximum Equal-Bit Pairs in a SubsequenceOA · Seen Nov 2026
- First Non-Repeating CharacterOA · ONSITE INTERVIEW · Seen Nov 2026
- Two SumOA · PHONE SCREEN · Seen Nov 2026
- Minimum Merge ConflictsOA · Seen Nov 2026
- Shopping Cart BillingOA · Seen Nov 2026
Similar questions at other companies
- Longest Contiguous Houses After Each BuildZipRecruiter · OAZipRecruiter interview questions
- Neighboring House GroupsAtlassian · OAAtlassian interview questions
- Group Linked Merchant RecordsStripe · PHONE SCREENStripe interview questions
- Accounts MergeOracle · ONSITE INTERVIEWOracle interview questions
- Count Overlapping Square PairsRamp · OARamp interview questions
- Minimum Rounds to Complete All TasksInfosys · OAInfosys interview questions
- Count Servers With No Requests in a Time WindowIBM · OAIBM interview questions
- Find Valid SET Card TriplesSnowflake · OA · PHONE SCREENSnowflake interview questions
- Maximum Escape Game ScoreMicrosoft · OAMicrosoft interview questions
- Stacked Item and Category DiscountsPalantir · OAPalantir interview questions