FastPrepMinimum Paid Swaps to Group Ones and Twos
Problem · Array

Minimum Paid Swaps to Group Ones and Twos

Learn this problem
● Mediuminfosys logoinfosysNEW GRADOA

Problem statement

You are given an array values containing only 0, 1, and 2. You may swap adjacent elements.

A swap between 1 and 2 costs one. A swap involving 0 costs zero. Rearrange the array so that all ones form one block and all twos form another block; the ones block may come before or after the twos block.

For this exercise, assume zeros may be placed anywhere outside or between the two value blocks. Return the minimum total paid cost. Equivalently, after zeros are removed, the remaining sequence must be all ones followed by all twos, or all twos followed by all ones.

Function

minimumPaidSwaps(values: int[]) → long

Examples

Example 1

values = [1,2,1,2]return = 1

Swap the middle 2,1 pair once to obtain [1,1,2,2].

Example 2

values = [2,0,1,0,2,1]return = 1

Ignoring zeros gives [2,1,2,1]. One paid crossing suffices for the order twos before ones; zeros can move for free.

Example 3

values = [0,1,0,1,2,0,2]return = 0

The nonzero sequence already has all ones before all twos.

Constraints

  • 1 <= values.length <= 10^5.
  • Each value is 0, 1, or 2.
  • The answer fits in a signed 64-bit integer.

More infosys problems

drafts saved locally
public long minimumPaidSwaps(int[] values) {
    // Write your code here.
}
values[1,2,1,2]
expected1
checking account