You are given an integer array nums.
You want to maximize the alternating sum of nums, which is defined as the value obtained by adding elements at even indices and subtracting elements at odd indices. That is, nums[0] - nums[1] + nums[2] - nums[3]...
You are also given a 2D integer array swaps where swaps[i] = [pi, qi]. For each pair [pi, qi] in swaps, you are allowed to swap the elements at indices pi and qi. These swaps can be performed any number of times and in any order.
Return the maximum possible alternating sum of nums.
Example 1:
Input: nums = [1,2,3], swaps = [[0,2],[1,2]]
Output: 4
Explanation:
The maximum alternating sum is achieved when nums is [2, 1, 3] or [3, 1, 2]. As an example, you can obtain nums = [2, 1, 3] as follows.
nums[0] and nums[2]. nums is now [3, 2, 1].nums[1] and nums[2]. nums is now [3, 1, 2].nums[0] and nums[2]. nums is now [2, 1, 3].Example 2:
Input: nums = [1,2,3], swaps = [[1,2]]
Output: 2
Explanation:
The maximum alternating sum is achieved by not performing any swaps.
Example 3:
Input: nums = [1,1000000000,1,1000000000,1,1000000000], swaps = []
Output: -2999999997
Explanation:
Since we cannot perform any swaps, the maximum alternating sum is achieved by not performing any swaps.
Constraints:
2 <= nums.length <= 1051 <= nums[i] <= 1090 <= swaps.length <= 105swaps[i] = [pi, qi]0 <= pi < qi <= nums.length - 1[pi, qi] != [pj, qj]Problem Overview: You are given an array where swaps are allowed between certain indices. After performing any number of valid swaps, compute the maximum possible alternating sum of the array, defined as a[0] - a[1] + a[2] - a[3] .... The challenge is that swaps are restricted, so you cannot arbitrarily reorder the entire array.
Approach 1: Brute Force Swap Exploration (Exponential time, O(n!) time, O(n) space)
A naive approach tries all permutations reachable through swaps and computes the alternating sum for each arrangement. For every configuration, iterate through the array and evaluate a[0] - a[1] + a[2] .... The maximum value across all reachable permutations is the answer. This approach becomes infeasible quickly because the number of possible permutations grows factorially. It only works for very small arrays and mainly demonstrates the core objective of maximizing positive positions and minimizing negative ones.
Approach 2: Union-Find + Greedy Assignment (Sorting Based) (O(n log n) time, O(n) space)
The key observation: if swaps are allowed between indices, those indices form connected components. Within each component, values can be freely rearranged. Use Union Find to group indices into components. For each component, collect its indices and the values currently stored there.
Next, determine how each index contributes to the alternating sum. Even indices contribute positively, odd indices contribute negatively. Inside a component, sort the values and greedily assign them: place the largest values at even indices (positive contribution) and the smallest values at odd indices (negative contribution). This local greedy strategy maximizes the contribution of each component independently. Sorting inside each component gives O(k log k) work per component, leading to O(n log n) overall.
This method combines greedy reasoning with connectivity grouping from union find. The array itself is only reorganized within components, and sorting ensures optimal assignment for alternating positions.
Recommended for interviews: The Union-Find + Greedy approach is the expected solution. Interviewers want to see that you model swap constraints as connected components, then reduce the problem to a local rearrangement problem. Mentioning the brute-force idea shows you understand the objective, but identifying components and greedily assigning values demonstrates strong algorithmic reasoning with sorting and connectivity structures.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutations | O(n!) | O(n) | Only for very small arrays or conceptual understanding |
| Union-Find + Greedy with Sorting | O(n log n) | O(n) | General optimal solution when swaps create connected components |
| Component Heap Assignment | O(n log n) | O(n) | Useful when streaming values or assigning greedily with priority queues |
Leetcode 3695 | Maximize Alternating Sum Using Swaps Detailed Solution | Biweekly 166Q4 | DSU • Samrat Bhardwaj • 453 views views
Watch 6 more video solutions →Practice Maximize Alternating Sum Using Swaps with our built-in code editor and test cases.
Practice on FleetCode