Python 0961.py
class Solution:
def repeatedNTimes(self, nums: List[int]) -> int:
have = set()
for n in nums:
if n in have:
return n # don't check if it's n+1 times
# just return the first number that occurs multiple times
have.add(n)
8 lines
|
312 bytes
|
submitted December 4, 2023
|
GitHub
28% comment ratio
|
tab size 4
|
low complexity
Difficulty
This problem is ranked as
and has an acceptance rate of about 77% (300k+ submissions).
Typical patterns to solve this problem:
easy
medium
hard
and has an acceptance rate of about 77% (300k+ submissions).
Typical patterns to solve this problem:
- Array
- Hash Table
I solved 663 easy, 1250 medium and 309 hard problems
AI Disclaimer
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.
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.
Code Walkthrough
Overview
The provided implementation solves the problem of finding an element that appears more than once in an integer array where exactly one value is repeated N times and the rest appear once. The algorithm walks through the array once, keeping track of values that have already been seen. As soon as a value is encountered that is already in the tracking structure, it is returned immediately. This approach guarantees that the first repeated value is identified without scanning the remainder of the input.
Key Steps
Initialization of the tracking container
have = set()A hash-based set is created to store the distinct numbers that have been observed so far. The choice of a set provides constant-time membership checks and insertions on average, which is essential for achieving linear performance.
Iteration over the input list
for n in nums:The algorithm iterates over each element n in the input list nums. The loop processes the elements in their original order, preserving any early occurrence of the repeated value.
Detection of a previously seen value
if n in have:
return nDuring each iteration the current element n is checked against the set have. If n is already present, the function returns n immediately. This early-exit condition eliminates any further work once the required element is found.
Recording a newly encountered value
have.add(n)If the current element has not been seen before, it is added to the set. This step ensures that subsequent occurrences of the same value will be caught by the detection logic.
Edge Cases Handled
When the input list contains only two elements, the algorithm still works because the first element is added to the set and the second element triggers the duplicate check. If the repeated value appears at the very beginning of the list (e.g., [5, 5, 1, 2, 3]), the second occurrence is detected on the second iteration and returned instantly. Conversely, if the repeated value is positioned at the end of the list (e.g., [1, 2, 3, 4, 5, 5]), the set accumulates all preceding distinct values and the final element satisfies the duplicate condition. In the extreme case where every element is the same (the repeated value occupies the entire array), the second element causes the early return, demonstrating that the algorithm does not rely on any particular distribution of values.
Performance Optimizations
The primary optimization is the use of a hash set for constant-time membership testing. By avoiding nested loops or repeated scans, the algorithm maintains a single pass over the data. The early return on the first duplicate prevents unnecessary processing of the remaining elements, which can be significant when the repeated value appears early in a large array. Additionally, the set grows only as large as the number of distinct elements encountered before the duplicate, limiting memory usage to the minimal necessary amount. These choices together yield an efficient solution that scales well with input size.
written by openai gpt
ELI5 - Simplified Explanation
Imagine a giant toy box filled with lots of colorful building bricks. This code is like a little robot helper that looks through the box to find a special trick. The robot keeps a small, empty basket by its side. As it picks up each brick one by one, it checks the basket to see if it has already seen a twin for that color. If the robot finds a brick that matches one already inside the basket, it stops searching right away because it knows it found the mystery number. If the basket is still empty for that specific color, the robot puts the brick inside the basket and moves on to the next one. This way, the robot keeps track of every toy it sees until it spots the pair.
written by google gemini
Code Quality
Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27
|
median = 8
|
μ = 7.70
|
σ = 1.05
Complexity Analysis
Time: linear
As a rule of thumb, the maximum input size for one second execution time is
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
generated automatically
Other Solutions
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)
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++ | Java | Python | TS | |||||
| WalkCCC | C++ | Java | Python | |||||||
| leetcode.ca | C++ | Java | Python | JS | Go | TS | ||||
| LeetcodeHelp | C++ | Java | Python | |||||||
| Progiez | C++ | Java | Python | |||||||
| github | BigEggStudy | C# | ||||||||
| black-shadows | C++ | |||||||||
| charles-wangkai | Java | |||||||||
| DimitrisJim | C | |||||||||
| everthis | JS | |||||||||
| fartem | Ruby | |||||||||
| fsq | C++ | |||||||||
| halfrost | Go | |||||||||
| haoel | C++ | |||||||||
| JoshCrozier | JS | |||||||||
| keineahnung2345 | C++ | |||||||||
| Krazune | C++ | |||||||||
| lkwq007 | Python | |||||||||
| lzl124631x | C++ | |||||||||
| muhammadfarhankt | Go | |||||||||
| qiyuangong | Java | |||||||||
| suxrobGM | C# | |||||||||
| varunu28 | Java | |||||||||
| withaarzoo | C++ | |||||||||
| YuriSpiridonov | Python | |||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||
| WalkCCC | C++, Python, Java | |||||||||
| leetcode.ca | C++, Go, Java, JavaScript, Python, TypeScript | |||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||
| Progiez | C++, Java, Python | |||||||||
| BigEggStudy | C# | |||||||||
| black-shadows | C++, C++ | |||||||||
| charles-wangkai | Java | |||||||||
| DimitrisJim | C | |||||||||
| everthis | JavaScript | |||||||||
| fartem | Ruby | |||||||||
| fsq | C++ | |||||||||
| halfrost | Go | |||||||||
| haoel | C++ | |||||||||
| JoshCrozier | JavaScript | |||||||||
| keineahnung2345 | C++ | |||||||||
| Krazune | C++ | |||||||||
| lkwq007 | Python | |||||||||
| lzl124631x | C++ | |||||||||
| muhammadfarhankt | Go | |||||||||
| qiyuangong | Java | |||||||||
| suxrobGM | C# | |||||||||
| varunu28 | Java | |||||||||
| withaarzoo | C++ | |||||||||
| YuriSpiridonov | Python |
39 links
|
25 authors
|
9 languages
Videos
These are a few popular YouTube videos for this problem:
codestorywithMIK 25 mins
N-Repeated Element in Size 2N Array | Multiple Ways | Detailed For Beginners | Leetcode 961 | MIK
Leetcode Daily 8 mins
961. N-Repeated Element in Size 2N Array | Leetcode Daily - Python
litCode 21 mins
leetcode - 961 N-Repeated Element in Size 2N Array
Tim Huang 4 mins
N-Repeated Element in Size 2N Array - Leetcode 961 - Python
4 videos
did my crawler come up with invalid videos ? drop me a line.
Solved On The Same Day
6 easy
- problem 953: Verifying an Alien Dictionary
- problem 2264: Largest 3-Same-Digit Number in String
- problem 2682: Find the Losers of the Circular Game
- problem 2784: Check if Array is Good
- problem 2848: Points That Intersect With Cars
- problem 2869: Minimum Operations to Collect Elements
- problem 890: Find and Replace Pattern
- problem 954: Array of Doubled Pairs
- problem 959: Regions Cut By Slashes
- problem 966: Vowel Spellchecker
- problem 1202: Smallest String With Swaps
12 solutions
December 4, 2023
Extra
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