Abstract / Summary

Given an array and a target value, count how many pairs of elements add up to the target value.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 62% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Design
• Hash Table

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The class implements a data structure that maintains two integer collections, nums1 and nums2, and supports two operations: updating an element of nums2 and counting the number of pairs whose sum equals a target value. The constructor prepares the internal state, the add method mutates nums2 while keeping a frequency map up-to-date, and the count method iterates over the sorted nums1 to accumulate matching pairs efficiently.

Initialization

During object creation the first list is sorted, which enables early termination when scanning for sums. The second list is stored unchanged, and a frequency dictionary is built to track how many times each value appears in nums2.

def __init__(self, nums1: List[int], nums2: List[int]):
    self.nums1 = sorted(nums1)
    self.nums2 = nums2

    self.n2 = defaultdict(int)
    for n in nums2:
        self.n2[n] += 1

Sorting nums1 once avoids repeated ordering work later. The use of defaultdict(int) eliminates the need for explicit existence checks when incrementing counts.

Updating an Element in nums2

The add method receives an index and a value to add to the element at that position. It first decrements the count of the old value in the frequency map, updates the element in the underlying list, and then increments the count for the new value.

def add(self, index: int, val: int) -> None:
    self.n2[self.nums2[index]] -= 1
    self.nums2[index] += val
    self.n2[self.nums2[index]] += 1

By adjusting the frequency map directly, the method preserves an accurate view of the multiset represented by nums2 without scanning the entire list.

Counting Pairs that Reach a Target

The count method computes how many pairs (a, b) with a from nums1 and b from nums2 satisfy a + b == tot. It iterates over the sorted nums1, stops as soon as the current element exceeds the target (since all subsequent elements will be larger), and looks up the complementary value in the frequency map.

def count(self, tot: int) -> int:
    result = 0
    for one in self.nums1:
        if one > tot:
            break
        two = tot - one
        if two in self.n2:
            result += self.n2[two]
    return result

The early break prevents unnecessary iterations once the remaining elements cannot contribute to the sum. The direct dictionary lookup for the complement yields constant-time access to the number of matching elements in nums2.

Edge Cases Handled

When the target is smaller than the smallest element of nums1, the loop terminates immediately, returning zero without performing any lookups. The frequency map naturally accommodates duplicate values in nums2; each occurrence contributes to the count through the stored multiplicity. Updating an element to a value that previously did not exist in nums2 adds a new entry to the map, while reducing a count to zero leaves the key present with a zero value, which does not affect subsequent lookups because the conditional checks for key existence, not positive count. Negative numbers are treated identically to positive ones, as the arithmetic and dictionary operations are agnostic to sign.

Performance Optimizations

Sorting nums1 once at construction enables the early-exit condition in the counting loop, reducing the number of iterations for large targets. Maintaining a frequency dictionary for nums2 provides O(1) access to the count of any needed complement, eliminating the need for a linear scan of nums2 on each count call. The add method updates the frequency map in constant time, ensuring that mutations do not degrade the performance of later queries. Together, these choices keep both update and query operations efficient even as the underlying arrays grow.

Imagine having two buckets full of colorful toy blocks. The first bucket has some blocks that stay exactly where they are, while the second bucket is special because you can change the numbers written on the blocks inside it.

When the setup starts, the blocks in the first bucket are put in order from smallest to largest so they are easy to look at. Then, every block in the second bucket is counted and put into a separate list to keep track of how many of each number exists.

The add part is like a game where you pick a block from the second bucket and change its number. First, the old number is taken away from the counted list. Then, the block gets a new value added to it. Finally, that new value is put into the counted list so it is ready to be used again.

The count part is where the goal is to find pairs of blocks that add up to a secret target number. You look at each block from the first bucket one by one. You figure out what number you need from the second bucket to hit the target. If that needed number exists in the second bucket, you add up all the times that specific number appears. Once you have checked all the blocks in the first bucket, you know exactly how many matching pairs can be made.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java				TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++	JS	Python	Java	C#	Go	Rust	TS
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality