Maximum Equal Adjacent Pairs After at Most One Replacement solution and explanation
3 more videos on this problem
Leetcode 4066 | Maximum Equal Adjacent Pairs After at Most One Replacement | weekly contest 521CodeWithMeGuys · 9:01 · 386 views
4066. Maximum Equal Adjacent Pairs After at Most One Replacement (Leetcode Medium)Programming Live with Larry · 10:23 · 163 views
Maximum Equal Adjacent Pairs After at Most One Replacement | Pair frequency | Leetcode 4066Manjeet Dhayal · 5:41 · 156 views
Maximum Equal Adjacent Pairs After at Most One Replacement | Leetcode 4066 | Weekly Contest 521Vijay Algorithms · 21:29 · 83 views
The problem
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
xinnumswithy.
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 = 3andy = 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 = 1andy = 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 <= 1051 <= nums[i] <= 109
Approach overview
Problem Overview: You get an array and may change at most one element to any value. Your goal is to maximize the number of adjacent index pairs whose values are equal.
Approach 1: Brute Force Recount (O(n^2) time, O(1) space)
Try every index i as the replacement point. For each index, test the candidate values that could help, which are the values of its left and right neighbors, plus the option of making no change. Recount all equal adjacent pairs after each trial. This is correct because a replacement only helps when the new value matches a neighbor, so any other value adds nothing. The cost is a full O(n) scan for each of the O(n) positions, which is too slow for large inputs. Use it to confirm your logic on small cases before optimizing.
Approach 2: Hash Map Counting with Local Delta (O(n) time, O(n) space)
Start by counting the current equal adjacent pairs in one pass. Then, for each index i, compute how the total changes if you set nums[i] to a new value x. Changing nums[i] breaks up to two existing pairs, one with nums[i-1] and one with nums[i+1]. It creates up to two new pairs if x equals those neighbors. The gain for each candidate x depends only on the neighbors, so you never need to recount the array. Store value frequencies in a hash map so you can compare candidate values quickly and track the best total. The best answer is the base count plus the largest net gain over all positions. Prefer this approach in every setting, since it handles arrays with millions of elements in linear time.
Recommended for interviews: Interviewers expect the O(n) approach. Starting with the brute force shows you understand how a single replacement affects only its neighboring pairs. Moving to the local delta with a hash map shows you can turn that observation into a linear solution. Explain why only neighbor values matter as candidates before writing code.
Related topics: array, hash table, counting.
Solution
Thinking
ncan be10^5and values can be10^9. Trying every distinct pairx,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 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
$
key=(x\ll 30)\mid y.
Since x,y\le 10^9, the key fits in a 64-bit integer. cnt[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, mx. Skipping the operation leaves mx=0. The answer is ans+mx.
The time complexity is O(n) and the space complexity is O(n)$.
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 ansclass 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;
}
}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;
}
};function maxEqualAdjacentPairs(nums: number[]): number {
const cnt = new Map<number, 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 = x * 2 ** 30 + y;
cnt.set(key, (cnt.get(key) || 0) + 1);
mx = Math.max(mx, cnt.get(key)!);
}
}
ans += mx;
return ans;
}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
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recount | O(n^2) | O(1) | Small inputs or verifying correctness |
| Hash Map Local Delta | O(n) | O(n) | General case and interviews |
Frequently asked questions
Is Maximum Equal Adjacent Pairs After at Most One Replacement easy or hard?
It is rated Medium with a 49.8% acceptance rate. The difficulty comes from realizing that a replacement only affects its two neighboring pairs. Once you see that, the linear solution follows directly.
Maximum Equal Adjacent Pairs After at Most One Replacement Python solution?
In Python, count the initial equal pairs with a single loop over adjacent elements. Then loop over indices and compute the gain for each neighbor value using direct comparisons. Use a dictionary or Counter when you need frequency lookups. The full solution is available in Python, Java, and C++ on FleetCode.
How to solve Maximum Equal Adjacent Pairs After at Most One Replacement in O(n)?
Count the existing equal adjacent pairs first. For each index, subtract the pairs broken by removing that element and add the pairs created by setting it to a left or right neighbor's value. Track the maximum net gain and add it to the base count.
What is the best approach for Maximum Equal Adjacent Pairs After at Most One Replacement?
The best approach counts the current equal adjacent pairs, then computes the net gain of changing each index to a neighbor's value. It runs in O(n) time with a hash map for frequency tracking. Only neighbor values need checking as replacement candidates.
What data structure is used in Maximum Equal Adjacent Pairs After at Most One Replacement?
The solution uses a hash map to store value frequencies, which allows constant-time lookups when comparing candidate values. It also relies on simple array indexing to access neighbors. No advanced data structures are required.
What is the time complexity of Maximum Equal Adjacent Pairs After at Most One Replacement?
The optimal solution runs in O(n) time because it makes one pass to count pairs and one pass to evaluate each index's local gain. The brute force recount runs in O(n^2) time. The optimal solution uses O(n) space for the hash map.
Is Maximum Equal Adjacent Pairs After at Most One Replacement asked at Google, Amazon, or Meta?
FleetCode tags this problem with Array, Hash Table, and Counting, but it does not list specific companies here. Check the company-tagged question lists on your preferred platform for current interview frequency. The underlying pattern of local updates after a single change appears often in interviews.