Skip to content

4066. Maximum Equal Adjacent Pairs After at Most One Replacement

DifficultyMedium

Description

You are given a 1-indexed integer array nums.

You can choose two distinct values x and y and perform the following operation at most once:

  • Replace every occurrence of x in nums with y.

Return the maximum possible number of pairs of adjacent elements that are equal after performing the operation.

 

Example 1:

Input: nums = [1,2,3,2]

Output: 2

Explanation:

  • One optimal solution is to choose x = 3 and y = 2.
  • The resulting array is [1, 2, 2, 2].
  • There are 2 pairs of adjacent elements that are equal: (nums[2], nums[3]) and (nums[3], nums[4]).
  • Therefore, the answer is 2.

Example 2:

Input: nums = [1,2,1,2,1]

Output: 4

Explanation:

  • One optimal solution is to choose x = 1 and y = 2.
  • The resulting array is [2, 2, 2, 2, 2].
  • There are 4 pairs of adjacent elements that are equal: (nums[1], nums[2]), (nums[2], nums[3]), (nums[3], nums[4]), and (nums[4], nums[5]).
  • Therefore, the answer is 4.

Example 3:

Input: nums = [1,1,1]

Output: 2

Explanation:

  • One optimal solution is to perform no operation.
  • Thus, the resulting array is [1, 1, 1].
  • There are 2 pairs of adjacent elements that are equal: (nums[1], nums[2]) and (nums[2], nums[3]).
  • Therefore, the answer is 2.

 

Constraints:

  • 2 <= nums.length <= 105
  • 1 <= nums[i] <= 109

Solutions

Solution 1: Hash Map

Thinking

\(n\) can be \(10^5\) and values can be \(10^9\). Trying every distinct pair \(x,y\), replacing, and recounting adjacent equals is too many candidates.

An adjacent pair that is already equal stays equal no matter which value is replaced by another. One replacement only equalizes adjacent positions whose values are exactly that pair \(x,y\). A different unordered pair is a different operation.

Count the adjacent positions that are already equal, then count unequal adjacent positions by unordered pair, and add the largest of those counts. Doing nothing corresponds to a maximum of \(0\).

Adjacent positions that are already equal stay equal after any replacement: if both hold \(x\), both become \(y\), and every other value is unchanged. Let \(\textit{ans}\) be the number of such pairs.

One operation picks two distinct values and replaces every occurrence of one with the other. An adjacent pair that newly becomes equal must already have been exactly those two values. For an unequal adjacent pair \(x,y\), place the smaller value first and encode

\[ \textit{key}=(x\ll 30)\mid y. \]

Since \(x,y\le 10^9\), the key fits in a \(64\)-bit integer. \(\textit{cnt}[\textit{key}]\) is how often that pair occurs in adjacent positions. Over every candidate operation, the number of newly equal adjacent pairs is the maximum of these counts, \(\textit{mx}\). Skipping the operation leaves \(\textit{mx}=0\). The answer is \(\textit{ans}+\textit{mx}\).

The time complexity is \(O(n)\) and the space complexity is \(O(n)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def maxEqualAdjacentPairs(self, nums: list[int]) -> int:
        cnt = defaultdict(int)
        ans = mx = 0
        for x, y in pairwise(nums):
            if x == y:
                ans += 1
            else:
                if x > y:
                    x, y = y, x
                key = x << 30 | y
                cnt[key] += 1
                mx = max(mx, cnt[key])
        ans += mx
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maxEqualAdjacentPairs(int[] nums) {
        Map<Long, Integer> cnt = new HashMap<>();
        int ans = 0, mx = 0;

        for (int i = 0; i + 1 < nums.length; i++) {
            int x = nums[i], y = nums[i + 1];
            if (x == y) {
                ans++;
            } else {
                if (x > y) {
                    int t = x;
                    x = y;
                    y = t;
                }
                long key = ((long) x << 30) | y;
                int v = cnt.merge(key, 1, Integer::sum);
                mx = Math.max(mx, v);
            }
        }
        ans += mx;
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxEqualAdjacentPairs(vector<int>& nums) {
        unordered_map<long long, int> cnt;
        int ans = 0, mx = 0;

        for (int i = 0; i + 1 < nums.size(); i++) {
            int x = nums[i], y = nums[i + 1];
            if (x == y) {
                ans++;
            } else {
                if (x > y) {
                    swap(x, y);
                }
                long long key = ((long long) x << 30) | y;
                mx = max(mx, ++cnt[key]);
            }
        }
        ans += mx;
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func maxEqualAdjacentPairs(nums []int) int {
    cnt := map[int64]int{}
    ans, mx := 0, 0

    for i := 0; i+1 < len(nums); i++ {
        x, y := nums[i], nums[i+1]
        if x == y {
            ans++
        } else {
            if x > y {
                x, y = y, x
            }
            key := int64(x)<<30 | int64(y)
            cnt[key]++
            if cnt[key] > mx {
                mx = cnt[key]
            }
        }
    }
    ans += mx
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function maxEqualAdjacentPairs(nums: number[]): number {
    const cnt = new Map<bigint, number>();
    let ans = 0;
    let mx = 0;

    for (let i = 0; i + 1 < nums.length; i++) {
        let x = nums[i];
        let y = nums[i + 1];
        if (x === y) {
            ans++;
        } else {
            if (x > y) {
                [x, y] = [y, x];
            }
            const key = (BigInt(x) << 30n) | BigInt(y);
            cnt.set(key, (cnt.get(key) || 0) + 1);
            mx = Math.max(mx, cnt.get(key)!);
        }
    }
    ans += mx;
    return ans;
}

Comments