Skip to content

2170. Minimum Operations to Make the Array Alternating

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct T {
  unordered_map<int, int> count;
  int mx = 0;
  int secondMax = 0;
  int maxFreq = 0;
  int secondMaxFreq = 0;
};

class Solution {
 public:
  int minimumOperations(vector<int>& nums) {
    // 0 := odd indices, 1 := even indices
    vector<T> ts(2);

    for (int i = 0; i < nums.size(); ++i) {
      T& t = ts[i % 2];
      const int freq = ++t.count[nums[i]];
      if (freq > t.maxFreq) {
        t.maxFreq = freq;
        t.mx = nums[i];
      } else if (freq > t.secondMaxFreq) {
        t.secondMaxFreq = freq;
        t.secondMax = nums[i];
      }
    }

    if (ts[0].mx == ts[1].mx)
      return nums.size() - max(ts[0].maxFreq + ts[1].secondMaxFreq,
                               ts[1].maxFreq + ts[0].secondMaxFreq);
    return nums.size() - (ts[0].maxFreq + ts[1].maxFreq);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class T {
  public Map<Integer, Integer> count = new HashMap<>();
  public int mx = 0;
  public int secondMax = 0;
  public int maxFreq = 0;
  public int secondMaxFreq = 0;
}

class Solution {
  public int minimumOperations(int[] nums) {
    T[] ts = new T[2];
    ts[0] = new T();
    ts[1] = new T();

    for (int i = 0; i < nums.length; ++i) {
      T t = ts[i % 2];
      t.count.merge(nums[i], 1, Integer::sum);
      final int freq = t.count.get(nums[i]);
      if (freq > t.maxFreq) {
        t.maxFreq = freq;
        t.mx = nums[i];
      } else if (freq > t.secondMaxFreq) {
        t.secondMaxFreq = freq;
        t.secondMax = nums[i];
      }
    }

    if (ts[0].mx == ts[1].mx)
      return nums.length -
          Math.max(ts[0].maxFreq + ts[1].secondMaxFreq, ts[1].maxFreq + ts[0].secondMaxFreq);
    return nums.length - (ts[0].maxFreq + ts[1].maxFreq);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class T:
  def __init__(self):
    self.count = collections.Counter()
    self.mx = 0
    self.secondMax = 0
    self.maxFreq = 0
    self.secondMaxFreq = 0


class Solution:
  def minimumOperations(self, nums: list[int]) -> int:
    # 0 := odd indices, 1 := even indices
    ts = [T() for _ in range(2)]

    for i, num in enumerate(nums):
      t = ts[i % 2]
      t.count[num] += 1
      freq = t.count[num]
      if freq > t.maxFreq:
        t.maxFreq = freq
        t.mx = num
      elif freq > t.secondMaxFreq:
        t.secondMaxFreq = freq
        t.secondMax = num

    if ts[0].mx == ts[1].mx:
      return len(nums) - max(ts[0].maxFreq + ts[1].secondMaxFreq,
                             ts[1].maxFreq + ts[0].secondMaxFreq)
    return len(nums) - (ts[0].maxFreq + ts[1].maxFreq)