Skip to content

Volume ITechnology

4.0.16 — Frequency and Duplicates in an Array ​

Classic · Easy to Medium · LeetCode 442 (Find All Duplicates), LeetCode 645 (Set Mismatch)

The problem ​

  1. Count how many times each element appears.
  2. List every element that appears more than once.
  3. The list holds the numbers 1 to n, but one number is missing and another appears twice. Find both. For [1, 2, 2, 4], 2 repeats and 3 is missing.
  4. Do part 2 again with no extra memory, when the values are known to lie between 1 and n.

1. Count each element ​

This is the counter, Move 2 from 4.0.0.

python
from collections import Counter

def frequencies(nums: list[int]) -> dict[int, int]:
    freq = {}
    for x in nums:
        freq[x] = freq.get(x, 0) + 1
    return freq

nums = [4, 2, 4, 1, 2, 4]
print(frequencies(nums))          # → {4: 3, 2: 2, 1: 1}
print(Counter(nums).most_common(1))   # → [(4, 3)]

The keys come out in the order they first appeared, because Python dictionaries keep insertion order.

2. Every duplicate ​

python
def duplicates(nums: list[int]) -> list[int]:
    seen, dups = set(), set()
    for x in nums:
        if x in seen:
            dups.add(x)        # (1)
        else:
            seen.add(x)
    return sorted(dups)

print(duplicates([4, 2, 4, 1, 2, 4]))   # → [2, 4]

(1) Put duplicates in a set too. Then 4, which appears three times, is reported once and not twice.

The slow way checks every pair, which is O(n^2). Sorting first and comparing neighbours is O(n \log n) and needs no set. The set version is O(n) time but uses O(n) memory. Each choice trades time for memory.

3. One missing, one repeated ​

The list should hold 1 to n exactly once each. One number got replaced by a copy of another.

With a counter ​

Count everything, then look at 1 to n. The number with count 2 is the repeat. The number with count 0 is missing. O(n) time and O(n) memory.

With two equations and no extra memory ​

This is the classic trick. Call the repeated number R and the missing number M.

First equation, from the sum. The numbers 1 to n add up to \frac{n(n+1)}{2}. Our list has R in place of M, so its sum is off by exactly R - M.

\text{expected sum} - \text{actual sum} = M - R

Why is 1 + 2 + \dots + n = \frac{n(n+1)}{2}? Write the sum forwards and backwards, one above the other. Each column adds to n + 1: 1 + n, then 2 + (n - 1), and so on. There are n columns, so the two rows together make n(n + 1). One row is half of that. The story goes that Carl Friedrich Gauss did this as a schoolboy, adding 1 to 100 in seconds to get 5050.

One equation cannot pin down two unknowns. So we need a second one.

Second equation, from the sum of squares. Add up the squares instead. The difference is now M^2 - R^2.

\text{expected squares} - \text{actual squares} = M^2 - R^2 = (M - R)(M + R)

The last step is the school identity a^2 - b^2 = (a - b)(a + b). We already know M - R from the first equation. Divide by it, and we get M + R.

Now we know M - R and M + R. Add them and halve to get M. Subtract and halve to get R.

python
def missing_and_repeated(nums: list[int]) -> tuple[int, int]:
    n = len(nums)
    diff = n * (n + 1) // 2 - sum(nums)                          # (1) M - R
    sq_diff = n * (n + 1) * (2 * n + 1) // 6 - sum(x * x for x in nums)   # (2) M² - R²
    total = sq_diff // diff                                      # (3) M + R
    missing = (diff + total) // 2                                # (4)
    repeated = total - missing
    return repeated, missing

print(missing_and_repeated([1, 2, 2, 4]))       # → (2, 3)
print(missing_and_repeated([3, 1, 3]))          # → (3, 2)

(1) Expected sum minus actual sum gives M - R.

(2) The sum of squares from 1 to n is \frac{n(n+1)(2n+1)}{6}, a standard formula. Expected minus actual gives M^2 - R^2.

(3) Divide by M - R to get M + R. The division is exact. And M - R is never 0, because the missing and repeated numbers are different.

(4) \frac{(M - R) + (M + R)}{2} = M.

Trace on [1, 2, 2, 4], where n = 4:

  • Expected sum 10, actual sum 9. So M - R = 1.
  • Expected squares 1 + 4 + 9 + 16 = 30. Actual squares 1 + 4 + 4 + 16 = 25. So M^2 - R^2 = 5.
  • M + R = 5 / 1 = 5.
  • M = (1 + 5) / 2 = 3 and R = 5 - 3 = 2.

The catch. The sum of squares grows like n^3. In Python that is fine. In a language with 64-bit integers, it overflows once n is around 2 million. The XOR method used in 4.30.5 Missing Number avoids this. Mention it if the interviewer asks about very large inputs.

4. All duplicates with no extra memory ​

LeetCode 442. The values lie between 1 and n, and each appears once or twice. Find all that appear twice, using O(1) extra memory.

The idea: use the list itself as the "seen" table ​

Because every value is between 1 and n, every value can point to a position in the list: value v points to index v - 1. Instead of a set, we mark position v - 1 to record "I have seen v". The mark is making the number at that position negative. The number itself is not lost, because abs() still gives it back.

When we meet a value whose position is already negative, we have seen it before. It is a duplicate.

python
def find_duplicates(nums: list[int]) -> list[int]:
    out = []
    for x in nums:
        idx = abs(x) - 1              # (1)
        if nums[idx] < 0:             # (2)
            out.append(abs(x))
        else:
            nums[idx] = -nums[idx]    # (3)
    return out

print(find_duplicates([4, 3, 2, 7, 8, 2, 3, 1]))   # → [2, 3]

(1) Use abs(x), because x itself may already have been made negative by an earlier step. Its value is still abs(x).

(2) Already negative means already seen.

(3) First time seeing this value. Mark its position.

Trace on [4, 3, 2, 7, 8, 2, 3, 1], showing the list after each step:

xposition markedduplicate?list after
43no4 3 2 −7 8 2 3 1
32no4 3 −2 −7 8 2 3 1
−21no4 −3 −2 −7 8 2 3 1
−76no4 −3 −2 −7 8 2 −3 1
87no4 −3 −2 −7 8 2 −3 −1
21yes, 2unchanged
−32yes, 3unchanged
−10no−4 −3 −2 −7 8 2 −3 −1

The cost. This changes the caller's list. If that matters, restore it at the end with one more pass: nums[i] = abs(nums[i]). Say this out loud. Changing someone's input without telling them is a real bug in production code.

Complexity ​

TaskTimeExtra memory
Frequency countO(n)O(k) distinct values
All duplicates, setO(n)O(n)
Missing and repeated, equationsO(n)O(1)
All duplicates, sign markingO(n)O(1)

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"Find the duplicates without using extra memory." This only works when the values are between 1 and n. Use each value as a position. Make the number at that position negative to mark "seen". If it is already negative, the value is a duplicate. Say that this changes the input list.

"Find the missing number and the repeated number." Use two equations. The sum tells you missing minus repeated. The sum of squares tells you missing squared minus repeated squared. From these two, you can work out both numbers.

"Would the sum-of-squares method work for 10 million numbers in Java?" No. The sum of squares gets too big for a 64-bit integer. The XOR method, from 4.30.5, does not have this problem.

"Why do you write abs(x) and not x?" An earlier step may already have made this number negative as a mark. Its real value is still abs(x).

One thing to volunteer: "When the values fit inside the list's length, the list itself can be used as the 'seen' table."

Next: 4.0.17 Reverse and Rotate an Array. Rotating by k in place, with the reverse-three-times trick.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet