↓Skip to main content
  1. LeetCode/

LeetCode 561: Array Partition

·1 min· ·
LeetCode Easy Array Greedy Sorting Counting-Sort
Wei Yi Chung
Author
Wei Yi Chung
Working at the contributing of open source, distributed systems, and data engineering.
Table of Contents

Meta Data
#

Difficulty: easy First Attempt: 2022-08-27

  • Submissions: Accepted ×3 → Internal Error → Accepted ×3

Approach
#

Each pair contributes its smaller value, so large values should pair with other large values to avoid waste (Greedy Template 1). After sorting, pair neighbors; the answer is the sum of sorted(nums)[::2]. The value range is small (-10^4..10^4), so counting sort also works.

My Attempts
#

It passed on the first try; resubmitting the same code later hit a LeetCode Internal Error.

Solution
#

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        return sum(sorted(nums)[::2])

Complexity
#

Time O(n log n), space O(n).

Mistakes to Avoid
#

  • Take the elements at even indices after sorting.

Interview Explanation
#

Each pair contributes its smaller value, so large values should pair together; after sorting I pair neighbors and sum the first of each pair, the even-index elements. Time O(n log n).

Related

LeetCode 455: Assign Cookies
·2 mins
LeetCode Easy Array Two-Pointers Greedy Sorting
LeetCode 455 note: sort children and cookies, satisfying the least greedy child with the smallest cookie that suffices; each pointer walks once
LeetCode 414: Third Maximum Number
·1 min
LeetCode Easy Array Sorting
LeetCode 414 note: track the three largest distinct values, skipping repeats, and return the maximum if fewer than three distinct values exist
LeetCode 217: Contains Duplicate
·1 min
LeetCode Easy Array Hash-Table Sorting
LeetCode 217 note: if converting to a set shortens the array, there is a duplicate
LeetCode 169: Majority Element
·2 mins
LeetCode Easy Array Hash-Table Divide-and-Conquer Sorting
LeetCode 169 note: Boyer-Moore voting, where different values cancel in pairs and the survivor is the one appearing more than half the time
LeetCode 506: Relative Ranks
·1 min
LeetCode Easy Array Sorting Heap-Priority-Queue
LeetCode 506 note: sort indices by score descending, give medals to the top three and rank strings to the rest, writing back into the original positions
LeetCode 566: Reshape the Matrix
·2 mins
LeetCode Easy Array Matrix Simulation
LeetCode 566 note: return the original if the element counts differ; otherwise element k goes to (k // c, k % c)